home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: SHell self-extracting ARchive
(archive/shar).
You can browse this item here: 3147
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Newsgroup Content (archive/news)
| magic
| Supported |
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| news or mail, ASCII text
| default
| |
| 100%
| TrID
| E-Mail message (Var. 2)
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| message/rfc822
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 3a 20 62 72 | 61 64 40 53 53 44 2e 43 |From: br|ad@SSD.C|
|00000010| 53 44 2e 48 41 52 52 49 | 53 2e 43 4f 4d 20 28 42 |SD.HARRI|S.COM (B|
|00000020| 72 61 64 20 41 70 70 6c | 65 74 6f 6e 29 0a 4e 65 |rad Appl|eton).Ne|
|00000030| 77 73 67 72 6f 75 70 73 | 3a 20 61 6c 74 2e 73 6f |wsgroups|: alt.so|
|00000040| 75 72 63 65 73 0a 53 75 | 62 6a 65 63 74 3a 20 41 |urces.Su|bject: A|
|00000050| 56 4c 20 74 72 65 65 20 | 6c 69 62 72 61 72 79 20 |VL tree |library |
|00000060| 28 70 61 72 74 20 31 20 | 6f 66 20 32 29 0a 4d 65 |(part 1 |of 2).Me|
|00000070| 73 73 61 67 65 2d 49 44 | 3a 20 3c 32 38 32 31 40 |ssage-ID|: <2821@|
|00000080| 74 72 61 76 69 73 2e 63 | 73 64 2e 68 61 72 72 69 |travis.c|sd.harri|
|00000090| 73 2e 63 6f 6d 3e 0a 44 | 61 74 65 3a 20 32 38 20 |s.com>.D|ate: 28 |
|000000a0| 4d 61 72 20 39 31 20 32 | 30 3a 33 38 3a 35 33 20 |Mar 91 2|0:38:53 |
|000000b0| 47 4d 54 0a 0a 54 68 69 | 73 20 69 73 20 61 20 42 |GMT..Thi|s is a B|
|000000c0| 65 74 61 20 72 65 6c 65 | 61 73 65 20 6f 66 20 70 |eta rele|ase of p|
|000000d0| 61 72 74 20 31 20 6f 66 | 20 61 6e 20 41 56 4c 20 |art 1 of| an AVL |
|000000e0| 74 72 65 65 20 6c 69 62 | 72 61 72 79 20 74 68 61 |tree lib|rary tha|
|000000f0| 74 20 49 20 68 61 76 65 | 20 62 65 65 6e 0a 75 73 |t I have| been.us|
|00000100| 69 6e 67 20 6f 6e 20 61 | 6e 64 20 6f 66 66 20 66 |ing on a|nd off f|
|00000110| 6f 72 20 61 20 66 65 77 | 20 79 65 61 72 73 2e 20 |or a few| years. |
|00000120| 50 6c 65 61 73 65 20 72 | 65 70 6f 72 74 20 61 6e |Please r|eport an|
|00000130| 79 20 62 75 67 73 20 41 | 53 41 50 20 74 6f 20 6d |y bugs A|SAP to m|
|00000140| 65 20 61 74 0a 62 72 61 | 64 40 73 73 64 2e 63 73 |e at.bra|d@ssd.cs|
|00000150| 64 2e 68 61 72 72 69 73 | 2e 63 6f 6d 0a 0a 23 21 |d.harris|.com..#!|
|00000160| 20 2f 62 69 6e 2f 73 68 | 0a 23 20 54 68 69 73 20 | /bin/sh|.# This |
|00000170| 69 73 20 61 20 73 68 65 | 6c 6c 20 61 72 63 68 69 |is a she|ll archi|
|00000180| 76 65 2e 20 20 52 65 6d | 6f 76 65 20 61 6e 79 74 |ve. Rem|ove anyt|
|00000190| 68 69 6e 67 20 62 65 66 | 6f 72 65 20 74 68 69 73 |hing bef|ore this|
|000001a0| 20 6c 69 6e 65 2c 20 74 | 68 65 6e 20 75 6e 70 61 | line, t|hen unpa|
|000001b0| 63 6b 0a 23 20 69 74 20 | 62 79 20 73 61 76 69 6e |ck.# it |by savin|
|000001c0| 67 20 69 74 20 69 6e 74 | 6f 20 61 20 66 69 6c 65 |g it int|o a file|
|000001d0| 20 61 6e 64 20 74 79 70 | 69 6e 67 20 22 73 68 20 | and typ|ing "sh |
|000001e0| 66 69 6c 65 22 2e 20 20 | 54 6f 20 6f 76 65 72 77 |file". |To overw|
|000001f0| 72 69 74 65 20 65 78 69 | 73 74 69 6e 67 0a 23 20 |rite exi|sting.# |
|00000200| 66 69 6c 65 73 2c 20 74 | 79 70 65 20 22 73 68 20 |files, t|ype "sh |
|00000210| 66 69 6c 65 20 2d 63 22 | 2e 20 20 59 6f 75 20 63 |file -c"|. You c|
|00000220| 61 6e 20 61 6c 73 6f 20 | 66 65 65 64 20 74 68 69 |an also |feed thi|
|00000230| 73 20 61 73 20 73 74 61 | 6e 64 61 72 64 20 69 6e |s as sta|ndard in|
|00000240| 70 75 74 20 76 69 61 0a | 23 20 75 6e 73 68 61 72 |put via.|# unshar|
|00000250| 2c 20 6f 72 20 62 79 20 | 74 79 70 69 6e 67 20 22 |, or by |typing "|
|00000260| 73 68 20 3c 66 69 6c 65 | 22 2c 20 65 2e 67 2e 2e |sh <file|", e.g..|
|00000270| 20 20 49 66 20 74 68 69 | 73 20 61 72 63 68 69 76 | If thi|s archiv|
|00000280| 65 20 69 73 20 63 6f 6d | 70 6c 65 74 65 2c 20 79 |e is com|plete, y|
|00000290| 6f 75 0a 23 20 77 69 6c | 6c 20 73 65 65 20 74 68 |ou.# wil|l see th|
|000002a0| 65 20 66 6f 6c 6c 6f 77 | 69 6e 67 20 6d 65 73 73 |e follow|ing mess|
|000002b0| 61 67 65 20 61 74 20 74 | 68 65 20 65 6e 64 3a 0a |age at t|he end:.|
|000002c0| 23 09 09 22 45 6e 64 20 | 6f 66 20 61 72 63 68 69 |#.."End |of archi|
|000002d0| 76 65 20 31 20 28 6f 66 | 20 32 29 2e 22 0a 23 20 |ve 1 (of| 2).".# |
|000002e0| 43 6f 6e 74 65 6e 74 73 | 3a 20 20 4d 41 4e 49 46 |Contents|: MANIF|
|000002f0| 45 53 54 20 4d 61 6b 65 | 66 69 6c 65 20 52 45 41 |EST Make|file REA|
|00000300| 44 4d 45 20 61 76 6c 2e | 68 20 61 76 6c 5f 74 65 |DME avl.|h avl_te|
|00000310| 73 74 2e 63 20 61 76 6c | 5f 74 79 70 73 2e 68 0a |st.c avl|_typs.h.|
|00000320| 23 20 20 20 6b 65 79 5f | 67 65 6e 2e 63 20 72 6f |# key_|gen.c ro|
|00000330| 74 61 74 65 2e 6f 6c 64 | 20 74 65 73 74 76 61 6c |tate.old| testval|
|00000340| 73 2e 68 0a 23 20 57 72 | 61 70 70 65 64 20 62 79 |s.h.# Wr|apped by|
|00000350| 20 62 72 61 64 40 68 63 | 78 32 20 6f 6e 20 54 68 | brad@hc|x2 on Th|
|00000360| 75 20 4d 61 72 20 32 38 | 20 31 35 3a 33 32 3a 35 |u Mar 28| 15:32:5|
|00000370| 34 20 31 39 39 31 0a 50 | 41 54 48 3d 2f 62 69 6e |4 1991.P|ATH=/bin|
|00000380| 3a 2f 75 73 72 2f 62 69 | 6e 3a 2f 75 73 72 2f 75 |:/usr/bi|n:/usr/u|
|00000390| 63 62 20 3b 20 65 78 70 | 6f 72 74 20 50 41 54 48 |cb ; exp|ort PATH|
|000003a0| 0a 69 66 20 74 65 73 74 | 20 2d 66 20 27 4d 41 4e |.if test| -f 'MAN|
|000003b0| 49 46 45 53 54 27 20 2d | 61 20 22 24 7b 31 7d 22 |IFEST' -|a "${1}"|
|000003c0| 20 21 3d 20 22 2d 63 22 | 20 3b 20 74 68 65 6e 20 | != "-c"| ; then |
|000003d0| 0a 20 20 65 63 68 6f 20 | 73 68 61 72 3a 20 57 69 |. echo |shar: Wi|
|000003e0| 6c 6c 20 6e 6f 74 20 63 | 6c 6f 62 62 65 72 20 65 |ll not c|lobber e|
|000003f0| 78 69 73 74 69 6e 67 20 | 66 69 6c 65 20 5c 22 27 |xisting |file \"'|
|00000400| 4d 41 4e 49 46 45 53 54 | 27 5c 22 0a 65 6c 73 65 |MANIFEST|'\".else|
|00000410| 0a 65 63 68 6f 20 73 68 | 61 72 3a 20 45 78 74 72 |.echo sh|ar: Extr|
|00000420| 61 63 74 69 6e 67 20 5c | 22 27 4d 41 4e 49 46 45 |acting \|"'MANIFE|
|00000430| 53 54 27 5c 22 20 5c 28 | 38 39 32 20 63 68 61 72 |ST'\" \(|892 char|
|00000440| 61 63 74 65 72 73 5c 29 | 0a 73 65 64 20 22 73 2f |acters\)|.sed "s/|
|00000450| 5e 58 2f 2f 22 20 3e 27 | 4d 41 4e 49 46 45 53 54 |^X//" >'|MANIFEST|
|00000460| 27 20 3c 3c 27 45 4e 44 | 5f 4f 46 5f 46 49 4c 45 |' <<'END|_OF_FILE|
|00000470| 27 0a 58 20 20 20 46 69 | 6c 65 20 4e 61 6d 65 09 |'.X Fi|le Name.|
|00000480| 09 41 72 63 68 69 76 65 | 20 23 09 44 65 73 63 72 |.Archive| #.Descr|
|00000490| 69 70 74 69 6f 6e 0a 58 | 2d 2d 2d 2d 2d 2d 2d 2d |iption.X|--------|
|000004a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004d0| 2d 2d 2d 0a 58 20 4c 49 | 43 45 4e 53 45 20 20 20 |---.X LI|CENSE |
|000004e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000004f0| 20 32 09 50 65 72 6d 69 | 73 73 69 6f 6e 20 74 6f | 2.Permi|ssion to|
|00000500| 20 75 73 65 2f 63 6f 70 | 79 20 74 68 69 73 20 70 | use/cop|y this p|
|00000510| 61 63 6b 61 67 65 0a 58 | 20 4d 41 4e 49 46 45 53 |ackage.X| MANIFES|
|00000520| 54 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |T | |
|00000530| 20 20 20 20 31 09 54 68 | 69 73 20 66 69 6c 65 0a | 1.Th|is file.|
|00000540| 58 20 4d 61 6b 65 66 69 | 6c 65 20 20 20 20 20 20 |X Makefi|le |
|00000550| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 31 09 4d | | 1.M|
|00000560| 61 6b 65 66 69 6c 65 20 | 66 6f 72 20 74 68 65 20 |akefile |for the |
|00000570| 6c 69 62 72 61 72 79 0a | 58 20 52 45 41 44 4d 45 |library.|X README|
|00000580| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000590| 20 20 20 20 20 31 09 44 | 69 73 63 75 73 73 69 6f | 1.D|iscussio|
|000005a0| 6e 20 6f 66 20 61 6c 67 | 6f 72 69 74 68 6d 28 73 |n of alg|orithm(s|
|000005b0| 29 20 66 6f 72 20 41 56 | 4c 20 74 72 65 65 73 0a |) for AV|L trees.|
|000005c0| 58 20 61 76 6c 2e 33 20 | 20 20 20 20 20 20 20 20 |X avl.3 | |
|000005d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 32 09 44 | | 2.D|
|000005e0| 6f 63 75 6d 65 6e 74 61 | 74 69 6f 6e 20 66 6f 72 |ocumenta|tion for|
|000005f0| 20 74 68 65 20 41 56 4c | 20 74 72 65 65 20 6c 69 | the AVL| tree li|
|00000600| 62 72 61 72 79 0a 58 20 | 61 76 6c 2e 63 20 20 20 |brary.X |avl.c |
|00000610| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000620| 20 20 20 32 09 53 6f 75 | 72 63 65 20 66 6f 72 20 | 2.Sou|rce for |
|00000630| 74 68 65 20 65 6e 74 69 | 72 65 20 41 56 4c 20 6c |the enti|re AVL l|
|00000640| 69 62 72 61 72 79 0a 58 | 20 61 76 6c 2e 68 20 20 |ibrary.X| avl.h |
|00000650| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000660| 20 20 20 20 31 09 49 6e | 63 6c 75 64 65 20 66 69 | 1.In|clude fi|
|00000670| 6c 65 20 66 6f 72 20 74 | 68 65 20 41 56 4c 20 74 |le for t|he AVL t|
|00000680| 72 65 65 20 6c 69 62 72 | 61 72 79 0a 58 20 61 76 |ree libr|ary.X av|
|00000690| 6c 5f 74 65 73 74 2e 63 | 20 20 20 20 20 20 20 20 |l_test.c| |
|000006a0| 20 20 20 20 20 20 20 20 | 20 31 09 54 68 65 20 74 | | 1.The t|
|000006b0| 65 73 74 20 70 72 6f 67 | 72 61 6d 0a 58 20 61 76 |est prog|ram.X av|
|000006c0| 6c 5f 74 79 70 73 2e 68 | 20 20 20 20 20 20 20 20 |l_typs.h| |
|000006d0| 20 20 20 20 20 20 20 20 | 20 31 09 49 6e 63 6c 75 | | 1.Inclu|
|000006e0| 64 65 20 66 69 6c 65 20 | 6e 65 65 64 65 64 20 62 |de file |needed b|
|000006f0| 79 20 74 68 65 20 41 56 | 4c 20 74 72 65 65 20 6c |y the AV|L tree l|
|00000700| 69 62 72 61 72 79 0a 58 | 20 6b 65 79 5f 67 65 6e |ibrary.X| key_gen|
|00000710| 2e 63 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.c | |
|00000720| 20 20 20 20 31 09 47 65 | 6e 65 72 61 74 65 73 20 | 1.Ge|nerates |
|00000730| 72 61 6e 64 6f 6d 20 74 | 65 73 74 20 76 61 6c 75 |random t|est valu|
|00000740| 65 73 0a 58 20 72 6f 74 | 61 74 65 2e 6f 6c 64 20 |es.X rot|ate.old |
|00000750| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000760| 31 09 4f 6c 64 20 63 6f | 64 65 20 66 6f 72 20 41 |1.Old co|de for A|
|00000770| 56 4c 20 72 6f 74 61 74 | 69 6f 6e 73 20 28 6e 6f |VL rotat|ions (no|
|00000780| 20 6c 6f 6e 67 65 72 20 | 75 73 65 64 29 0a 58 20 | longer |used).X |
|00000790| 74 65 73 74 76 61 6c 73 | 2e 68 20 20 20 20 20 20 |testvals|.h |
|000007a0| 20 20 20 20 20 20 20 20 | 20 20 20 31 09 54 65 73 | | 1.Tes|
|000007b0| 74 20 76 61 6c 75 65 73 | 20 66 6f 72 20 74 68 65 |t values| for the|
|000007c0| 20 74 65 73 74 20 70 72 | 6f 67 72 61 6d 0a 58 20 | test pr|ogram.X |
|000007d0| 74 65 73 74 76 61 6c 73 | 2e 6f 6c 64 20 20 20 20 |testvals|.old |
|000007e0| 20 20 20 20 20 20 20 20 | 20 20 20 32 09 4f 6c 64 | | 2.Old|
|000007f0| 20 74 65 73 74 20 76 61 | 6c 75 65 73 0a 45 4e 44 | test va|lues.END|
|00000800| 5f 4f 46 5f 46 49 4c 45 | 0a 69 66 20 74 65 73 74 |_OF_FILE|.if test|
|00000810| 20 38 39 32 20 2d 6e 65 | 20 60 77 63 20 2d 63 20 | 892 -ne| `wc -c |
|00000820| 3c 27 4d 41 4e 49 46 45 | 53 54 27 60 3b 20 74 68 |<'MANIFE|ST'`; th|
|00000830| 65 6e 0a 20 20 20 20 65 | 63 68 6f 20 73 68 61 72 |en. e|cho shar|
|00000840| 3a 20 5c 22 27 4d 41 4e | 49 46 45 53 54 27 5c 22 |: \"'MAN|IFEST'\"|
|00000850| 20 75 6e 70 61 63 6b 65 | 64 20 77 69 74 68 20 77 | unpacke|d with w|
|00000860| 72 6f 6e 67 20 73 69 7a | 65 21 0a 66 69 0a 23 20 |rong siz|e!.fi.# |
|00000870| 65 6e 64 20 6f 66 20 27 | 4d 41 4e 49 46 45 53 54 |end of '|MANIFEST|
|00000880| 27 0a 66 69 0a 69 66 20 | 74 65 73 74 20 2d 66 20 |'.fi.if |test -f |
|00000890| 27 4d 61 6b 65 66 69 6c | 65 27 20 2d 61 20 22 24 |'Makefil|e' -a "$|
|000008a0| 7b 31 7d 22 20 21 3d 20 | 22 2d 63 22 20 3b 20 74 |{1}" != |"-c" ; t|
|000008b0| 68 65 6e 20 0a 20 20 65 | 63 68 6f 20 73 68 61 72 |hen . e|cho shar|
|000008c0| 3a 20 57 69 6c 6c 20 6e | 6f 74 20 63 6c 6f 62 62 |: Will n|ot clobb|
|000008d0| 65 72 20 65 78 69 73 74 | 69 6e 67 20 66 69 6c 65 |er exist|ing file|
|000008e0| 20 5c 22 27 4d 61 6b 65 | 66 69 6c 65 27 5c 22 0a | \"'Make|file'\".|
|000008f0| 65 6c 73 65 0a 65 63 68 | 6f 20 73 68 61 72 3a 20 |else.ech|o shar: |
|00000900| 45 78 74 72 61 63 74 69 | 6e 67 20 5c 22 27 4d 61 |Extracti|ng \"'Ma|
|00000910| 6b 65 66 69 6c 65 27 5c | 22 20 5c 28 36 31 38 20 |kefile'\|" \(618 |
|00000920| 63 68 61 72 61 63 74 65 | 72 73 5c 29 0a 73 65 64 |characte|rs\).sed|
|00000930| 20 22 73 2f 5e 58 2f 2f | 22 20 3e 27 4d 61 6b 65 | "s/^X//|" >'Make|
|00000940| 66 69 6c 65 27 20 3c 3c | 27 45 4e 44 5f 4f 46 5f |file' <<|'END_OF_|
|00000950| 46 49 4c 45 27 0a 58 44 | 42 47 3d 09 2d 67 0a 58 |FILE'.XD|BG=.-g.X|
|00000960| 44 45 46 53 3d 09 0a 58 | 44 45 4c 3d 09 2f 62 69 |DEFS=..X|DEL=./bi|
|00000970| 6e 2f 72 6d 20 2d 66 0a | 58 48 44 52 53 3d 09 61 |n/rm -f.|XHDRS=.a|
|00000980| 76 6c 2e 68 20 20 20 61 | 76 6c 5f 74 79 70 73 2e |vl.h a|vl_typs.|
|00000990| 68 20 20 20 74 65 73 74 | 76 61 6c 73 2e 68 0a 58 |h test|vals.h.X|
|000009a0| 4c 49 42 52 41 52 59 3d | 09 6c 69 62 61 76 6c 2e |LIBRARY=|.libavl.|
|000009b0| 61 0a 58 4f 42 4a 53 3d | 09 61 76 6c 2e 6f 20 20 |a.XOBJS=|.avl.o |
|000009c0| 20 61 76 6c 5f 74 65 73 | 74 2e 6f 0a 58 23 4f 50 | avl_tes|t.o.X#OP|
|000009d0| 54 3d 09 2d 4f 0a 58 50 | 52 49 4e 54 3d 09 70 72 |T=.-O.XP|RINT=.pr|
|000009e0| 0a 58 53 52 43 53 3d 09 | 61 76 6c 2e 63 20 5c 0a |.XSRCS=.|avl.c \.|
|000009f0| 58 09 09 61 76 6c 5f 74 | 65 73 74 2e 63 0a 58 54 |X..avl_t|est.c.XT|
|00000a00| 45 53 54 3d 09 61 76 6c | 5f 74 65 73 74 0a 58 0a |EST=.avl|_test.X.|
|00000a10| 58 43 46 4c 41 47 53 3d | 20 24 28 44 42 47 29 20 |XCFLAGS=| $(DBG) |
|00000a20| 24 28 4f 50 54 29 20 24 | 28 44 45 46 53 29 0a 58 |$(OPT) $|(DEFS).X|
|00000a30| 0a 58 61 6c 6c 3a 20 6c | 69 62 72 61 72 79 20 74 |.Xall: l|ibrary t|
|00000a40| 65 73 74 0a 58 0a 58 6c | 69 62 72 61 72 79 3a 20 |est.X.Xl|ibrary: |
|00000a50| 24 28 4c 49 42 52 41 52 | 59 29 0a 58 0a 58 74 65 |$(LIBRAR|Y).X.Xte|
|00000a60| 73 74 3a 20 24 28 54 45 | 53 54 29 0a 58 0a 58 24 |st: $(TE|ST).X.X$|
|00000a70| 28 4c 49 42 52 41 52 59 | 29 3a 09 61 76 6c 2e 6f |(LIBRARY|):.avl.o|
|00000a80| 0a 58 09 61 72 20 63 72 | 75 20 24 28 4c 49 42 52 |.X.ar cr|u $(LIBR|
|00000a90| 41 52 59 29 20 61 76 6c | 2e 6f 0a 58 09 72 61 6e |ARY) avl|.o.X.ran|
|00000aa0| 6c 69 62 20 24 28 4c 49 | 42 52 41 52 59 29 0a 58 |lib $(LI|BRARY).X|
|00000ab0| 0a 58 24 28 54 45 53 54 | 29 3a 20 24 28 4f 42 4a |.X$(TEST|): $(OBJ|
|00000ac0| 53 29 0a 58 09 24 28 43 | 43 29 20 24 28 43 46 4c |S).X.$(C|C) $(CFL|
|00000ad0| 41 47 53 29 20 2d 6f 20 | 24 28 54 45 53 54 29 20 |AGS) -o |$(TEST) |
|00000ae0| 24 28 4f 42 4a 53 29 0a | 58 0a 58 63 6c 65 61 6e |$(OBJS).|X.Xclean|
|00000af0| 3a 0a 58 09 24 28 44 45 | 4c 29 20 24 28 4f 42 4a |:.X.$(DE|L) $(OBJ|
|00000b00| 53 29 0a 58 0a 58 63 6c | 6f 62 62 65 72 3a 20 63 |S).X.Xcl|obber: c|
|00000b10| 6c 65 61 6e 0a 58 09 24 | 28 44 45 4c 29 20 24 28 |lean.X.$|(DEL) $(|
|00000b20| 4c 49 42 52 41 52 59 29 | 20 24 28 54 45 53 54 29 |LIBRARY)| $(TEST)|
|00000b30| 0a 58 09 0a 58 69 6e 64 | 65 78 3a 0a 58 09 63 74 |.X..Xind|ex:.X.ct|
|00000b40| 61 67 73 20 2d 77 78 20 | 24 28 48 44 52 53 29 20 |ags -wx |$(HDRS) |
|00000b50| 24 28 53 52 43 53 29 0a | 58 0a 58 70 72 69 6e 74 |$(SRCS).|X.Xprint|
|00000b60| 3a 0a 58 09 24 28 50 52 | 49 4e 54 29 20 24 28 48 |:.X.$(PR|INT) $(H|
|00000b70| 44 52 53 29 20 24 28 53 | 52 43 53 29 0a 58 0a 58 |DRS) $(S|RCS).X.X|
|00000b80| 74 61 67 73 3a 20 24 28 | 48 44 52 53 29 20 24 28 |tags: $(|HDRS) $(|
|00000b90| 53 52 43 53 29 0a 58 09 | 20 63 74 61 67 73 20 24 |SRCS).X.| ctags $|
|00000ba0| 28 48 44 52 53 29 20 24 | 28 53 52 43 53 29 0a 58 |(HDRS) $|(SRCS).X|
|00000bb0| 0a 58 23 23 23 0a 58 61 | 76 6c 2e 6f 3a 20 61 76 |.X###.Xa|vl.o: av|
|00000bc0| 6c 2e 68 20 61 76 6c 5f | 74 79 70 73 2e 68 0a 58 |l.h avl_|typs.h.X|
|00000bd0| 61 76 6c 5f 74 65 73 74 | 2e 6f 3a 20 61 76 6c 2e |avl_test|.o: avl.|
|00000be0| 68 20 74 65 73 74 76 61 | 6c 73 2e 68 0a 45 4e 44 |h testva|ls.h.END|
|00000bf0| 5f 4f 46 5f 46 49 4c 45 | 0a 69 66 20 74 65 73 74 |_OF_FILE|.if test|
|00000c00| 20 36 31 38 20 2d 6e 65 | 20 60 77 63 20 2d 63 20 | 618 -ne| `wc -c |
|00000c10| 3c 27 4d 61 6b 65 66 69 | 6c 65 27 60 3b 20 74 68 |<'Makefi|le'`; th|
|00000c20| 65 6e 0a 20 20 20 20 65 | 63 68 6f 20 73 68 61 72 |en. e|cho shar|
|00000c30| 3a 20 5c 22 27 4d 61 6b | 65 66 69 6c 65 27 5c 22 |: \"'Mak|efile'\"|
|00000c40| 20 75 6e 70 61 63 6b 65 | 64 20 77 69 74 68 20 77 | unpacke|d with w|
|00000c50| 72 6f 6e 67 20 73 69 7a | 65 21 0a 66 69 0a 23 20 |rong siz|e!.fi.# |
|00000c60| 65 6e 64 20 6f 66 20 27 | 4d 61 6b 65 66 69 6c 65 |end of '|Makefile|
|00000c70| 27 0a 66 69 0a 69 66 20 | 74 65 73 74 20 2d 66 20 |'.fi.if |test -f |
|00000c80| 27 52 45 41 44 4d 45 27 | 20 2d 61 20 22 24 7b 31 |'README'| -a "${1|
|00000c90| 7d 22 20 21 3d 20 22 2d | 63 22 20 3b 20 74 68 65 |}" != "-|c" ; the|
|00000ca0| 6e 20 0a 20 20 65 63 68 | 6f 20 73 68 61 72 3a 20 |n . ech|o shar: |
|00000cb0| 57 69 6c 6c 20 6e 6f 74 | 20 63 6c 6f 62 62 65 72 |Will not| clobber|
|00000cc0| 20 65 78 69 73 74 69 6e | 67 20 66 69 6c 65 20 5c | existin|g file \|
|00000cd0| 22 27 52 45 41 44 4d 45 | 27 5c 22 0a 65 6c 73 65 |"'README|'\".else|
|00000ce0| 0a 65 63 68 6f 20 73 68 | 61 72 3a 20 45 78 74 72 |.echo sh|ar: Extr|
|00000cf0| 61 63 74 69 6e 67 20 5c | 22 27 52 45 41 44 4d 45 |acting \|"'README|
|00000d00| 27 5c 22 20 5c 28 33 37 | 37 37 32 20 63 68 61 72 |'\" \(37|772 char|
|00000d10| 61 63 74 65 72 73 5c 29 | 0a 73 65 64 20 22 73 2f |acters\)|.sed "s/|
|00000d20| 5e 58 2f 2f 22 20 3e 27 | 52 45 41 44 4d 45 27 20 |^X//" >'|README' |
|00000d30| 3c 3c 27 45 4e 44 5f 4f | 46 5f 46 49 4c 45 27 0a |<<'END_O|F_FILE'.|
|00000d40| 58 54 6f 3a 20 6f 65 73 | 74 65 72 6c 65 40 77 70 |XTo: oes|terle@wp|
|00000d50| 69 2e 77 70 69 2e 65 64 | 75 0a 58 53 75 62 6a 65 |i.wpi.ed|u.XSubje|
|00000d60| 63 74 3a 20 52 65 3a 20 | 42 69 6e 61 72 79 20 54 |ct: Re: |Binary T|
|00000d70| 72 65 65 20 52 65 2d 62 | 61 6c 61 6e 63 69 6e 67 |ree Re-b|alancing|
|00000d80| 0a 58 4e 65 77 73 67 72 | 6f 75 70 73 3a 20 63 6f |.XNewsgr|oups: co|
|00000d90| 6d 70 2e 6c 61 6e 67 2e | 63 0a 58 49 6e 2d 52 65 |mp.lang.|c.XIn-Re|
|00000da0| 70 6c 79 2d 54 6f 3a 20 | 3c 31 30 34 30 33 40 77 |ply-To: |<10403@w|
|00000db0| 70 69 2e 77 70 69 2e 65 | 64 75 3e 0a 58 4f 72 67 |pi.wpi.e|du>.XOrg|
|00000dc0| 61 6e 69 7a 61 74 69 6f | 6e 3a 20 48 61 72 72 69 |anizatio|n: Harri|
|00000dd0| 73 20 43 6f 6d 70 75 74 | 65 72 20 53 79 73 74 65 |s Comput|er Syste|
|00000de0| 6d 73 2c 20 46 6f 72 74 | 20 4c 61 75 64 65 72 64 |ms, Fort| Lauderd|
|00000df0| 61 6c 65 2c 20 46 4c 0a | 58 43 63 3a 20 0a 58 42 |ale, FL.|XCc: .XB|
|00000e00| 63 63 3a 20 0a 58 0a 58 | 49 6e 20 61 72 74 69 63 |cc: .X.X|In artic|
|00000e10| 6c 65 20 3c 31 30 34 30 | 33 40 77 70 69 2e 77 70 |le <1040|3@wpi.wp|
|00000e20| 69 2e 65 64 75 3e 20 79 | 6f 75 20 77 72 69 74 65 |i.edu> y|ou write|
|00000e30| 3a 0a 58 3e 0a 58 3e 47 | 72 65 65 74 69 6e 67 73 |:.X>.X>G|reetings|
|00000e40| 21 0a 58 3e 0a 58 3e 20 | 20 20 20 20 49 20 77 6f |!.X>.X> | I wo|
|00000e50| 75 6c 64 20 6c 69 6b 65 | 20 74 6f 20 6d 61 6b 65 |uld like| to make|
|00000e60| 20 61 20 72 65 71 75 65 | 73 74 20 66 6f 72 20 73 | a reque|st for s|
|00000e70| 6f 6d 65 20 72 65 66 65 | 72 65 6e 63 65 73 20 6f |ome refe|rences o|
|00000e80| 72 20 43 20 63 6f 64 65 | 0a 58 3e 66 6f 72 20 62 |r C code|.X>for b|
|00000e90| 61 6c 61 6e 63 69 6e 67 | 20 62 69 6e 61 72 79 20 |alancing| binary |
|00000ea0| 74 72 65 65 73 20 61 66 | 74 65 72 20 69 6e 73 65 |trees af|ter inse|
|00000eb0| 72 74 69 6f 6e 2f 64 65 | 6c 65 74 69 6f 6e 2e 20 |rtion/de|letion. |
|00000ec0| 20 49 20 68 61 76 65 20 | 62 65 65 6e 0a 58 3e 6c | I have |been.X>l|
|00000ed0| 6f 6f 6b 69 6e 67 20 61 | 74 20 74 77 6f 20 62 6f |ooking a|t two bo|
|00000ee0| 6f 6b 73 20 28 5f 41 6c | 67 6f 72 69 74 68 6d 73 |oks (_Al|gorithms|
|00000ef0| 20 2b 20 44 61 74 61 20 | 53 74 72 75 63 74 75 72 | + Data |Structur|
|00000f00| 65 73 20 3d 20 50 72 6f | 67 72 61 6d 73 5f 2c 0a |es = Pro|grams_,.|
|00000f10| 58 3e 62 79 20 4e 69 63 | 6b 6c 61 75 73 20 57 69 |X>by Nic|klaus Wi|
|00000f20| 72 74 68 3b 20 61 6e 64 | 20 5f 41 6c 67 6f 72 69 |rth; and| _Algori|
|00000f30| 74 68 6d 73 3a 20 20 54 | 68 65 69 72 20 43 6f 6d |thms: T|heir Com|
|00000f40| 70 6c 65 78 69 74 79 20 | 61 6e 64 0a 58 3e 45 66 |plexity |and.X>Ef|
|00000f50| 66 69 63 69 65 6e 63 79 | 5f 20 62 79 20 4c 79 64 |ficiency|_ by Lyd|
|00000f60| 69 61 20 4b 72 6f 6e 73 | 6a 3a 6f 29 2e 20 20 42 |ia Krons|j:o). B|
|00000f70| 6f 74 68 20 74 68 65 20 | 62 6f 6f 6b 73 27 20 63 |oth the |books' c|
|00000f80| 6f 64 65 20 69 73 20 69 | 6e 0a 58 3e 50 41 53 43 |ode is i|n.X>PASC|
|00000f90| 41 4c 3b 20 49 20 77 6f | 75 6c 64 20 6d 6f 72 65 |AL; I wo|uld more|
|00000fa0| 20 6f 72 20 6c 65 73 73 | 20 77 61 6e 74 20 74 6f | or less| want to|
|00000fb0| 20 63 6f 6d 70 61 72 65 | 20 74 6f 20 73 65 65 20 | compare| to see |
|00000fc0| 69 66 20 49 20 61 6d 0a | 58 3e 69 6e 74 65 72 70 |if I am.|X>interp|
|00000fd0| 72 65 74 69 6e 67 20 74 | 68 65 20 63 6f 64 65 20 |reting t|he code |
|00000fe0| 63 6f 72 72 65 63 74 6c | 79 2c 20 73 69 6e 63 65 |correctl|y, since|
|00000ff0| 20 62 6f 74 68 20 62 6f | 6f 6b 73 20 69 6d 70 6c | both bo|oks impl|
|00001000| 65 6d 65 6e 74 20 74 68 | 65 0a 58 3e 62 61 6c 61 |ement th|e.X>bala|
|00001010| 6e 63 69 6e 67 20 64 69 | 66 66 65 72 65 6e 74 6c |ncing di|fferentl|
|00001020| 79 20 61 6e 64 20 49 20 | 73 74 69 6c 6c 20 77 61 |y and I |still wa|
|00001030| 6e 74 20 74 6f 20 69 6d | 70 6c 65 6d 65 6e 74 20 |nt to im|plement |
|00001040| 69 74 0a 58 3e 64 69 66 | 66 65 72 65 6e 74 6c 79 |it.X>dif|ferently|
|00001050| 20 74 68 61 6e 20 62 6f | 74 68 20 6f 66 20 74 68 | than bo|th of th|
|00001060| 65 20 62 6f 6f 6b 73 2e | 20 20 49 20 70 6c 61 6e |e books.| I plan|
|00001070| 20 74 6f 20 6b 65 65 70 | 20 74 68 65 20 62 61 6c | to keep| the bal|
|00001080| 61 6e 63 69 6e 67 0a 58 | 3e 69 6e 66 6f 72 6d 61 |ancing.X|>informa|
|00001090| 74 69 6f 6e 20 69 6e 20 | 73 74 72 75 63 74 75 72 |tion in |structur|
|000010a0| 65 73 20 66 6f 72 20 73 | 70 65 65 64 2e 20 20 53 |es for s|peed. S|
|000010b0| 69 6d 70 6c 69 63 69 74 | 79 20 69 73 20 6d 75 63 |implicit|y is muc|
|000010c0| 68 0a 58 3e 64 65 73 69 | 72 61 62 6c 65 2c 20 72 |h.X>desi|rable, r|
|000010d0| 65 63 75 72 73 69 76 65 | 20 69 73 20 67 72 65 61 |ecursive| is grea|
|000010e0| 74 2e 0a 58 3e 0a 58 49 | 20 68 61 76 65 20 73 70 |t..X>.XI| have sp|
|000010f0| 65 6e 74 20 61 20 63 6f | 75 70 6c 65 20 6f 66 20 |ent a co|uple of |
|00001100| 79 65 61 72 73 20 64 6f | 69 6e 67 20 65 78 61 63 |years do|ing exac|
|00001110| 74 6c 79 20 74 68 69 73 | 2e 20 49 20 68 61 76 65 |tly this|. I have|
|00001120| 20 69 6d 70 6c 65 6d 65 | 6e 74 65 64 20 0a 58 77 | impleme|nted .Xw|
|00001130| 68 61 74 20 49 20 66 65 | 65 6c 20 69 73 20 61 20 |hat I fe|el is a |
|00001140| 76 65 72 79 20 65 6c 65 | 67 61 6e 74 20 61 6e 64 |very ele|gant and|
|00001150| 20 65 61 73 79 20 74 6f | 20 75 6e 64 65 72 73 74 | easy to| underst|
|00001160| 61 6e 64 20 73 6f 6c 75 | 74 69 6f 6e 20 61 6e 64 |and solu|tion and|
|00001170| 20 74 68 65 20 0a 58 72 | 65 73 75 6c 74 20 69 73 | the .Xr|esult is|
|00001180| 20 61 20 43 20 6c 69 62 | 72 61 72 79 20 66 6f 72 | a C lib|rary for|
|00001190| 20 68 61 6e 64 6c 69 6e | 67 20 41 56 4c 20 74 72 | handlin|g AVL tr|
|000011a0| 65 65 73 20 61 73 20 61 | 6e 20 61 62 73 74 72 61 |ees as a|n abstra|
|000011b0| 63 74 20 74 79 70 65 2e | 20 49 66 20 0a 58 79 6f |ct type.| If .Xyo|
|000011c0| 75 20 77 61 6e 74 20 6d | 65 20 74 6f 20 6d 61 69 |u want m|e to mai|
|000011d0| 6c 20 6d 79 20 63 6f 64 | 65 2c 20 74 68 65 6e 20 |l my cod|e, then |
|000011e0| 6c 65 74 20 6d 65 20 6b | 6e 6f 77 21 20 49 20 77 |let me k|now! I w|
|000011f0| 69 6c 6c 20 67 69 76 65 | 20 61 20 62 69 74 20 6f |ill give| a bit o|
|00001200| 66 20 61 0a 58 64 69 73 | 63 75 73 73 69 6f 6e 20 |f a.Xdis|cussion |
|00001210| 74 68 6f 75 67 68 2e 0a | 58 0a 58 46 69 72 73 74 |though..|X.XFirst|
|00001220| 20 6f 66 20 61 6c 6c 2c | 20 49 20 75 73 65 20 61 | of all,| I use a|
|00001230| 20 62 61 6c 61 6e 63 65 | 20 66 61 63 74 6f 72 20 | balance| factor |
|00001240| 74 68 61 74 20 72 61 6e | 67 65 73 20 66 72 6f 6d |that ran|ges from|
|00001250| 20 2d 32 20 2e 2e 20 32 | 2c 20 0a 58 4d 61 6e 79 | -2 .. 2|, .XMany|
|00001260| 20 74 65 78 74 73 20 49 | 76 65 20 73 65 65 6e 20 | texts I|ve seen |
|00001270| 75 73 65 20 2d 31 20 2e | 2e 20 31 20 62 75 74 20 |use -1 .|. 1 but |
|00001280| 49 20 66 65 65 6c 20 2d | 32 20 2e 2e 20 32 20 69 |I feel -|2 .. 2 i|
|00001290| 73 20 65 61 73 69 65 72 | 20 74 6f 0a 58 75 6e 64 |s easier| to.Xund|
|000012a0| 65 72 73 74 61 6e 64 20 | 61 6e 64 20 70 72 6f 76 |erstand |and prov|
|000012b0| 69 64 65 73 20 66 6f 72 | 20 6d 6f 72 65 20 73 69 |ides for| more si|
|000012c0| 6d 70 6c 65 20 62 61 6c | 61 6e 63 65 20 75 70 64 |mple bal|ance upd|
|000012d0| 61 74 69 6e 67 2e 0a 58 | 49 74 20 69 73 20 61 6c |ating..X|It is al|
|000012e0| 73 6f 20 55 4e 4e 45 43 | 45 53 53 41 52 59 20 74 |so UNNEC|ESSARY t|
|000012f0| 6f 20 75 73 65 20 73 65 | 70 61 72 61 74 65 20 72 |o use se|parate r|
|00001300| 6f 75 74 69 6e 65 73 20 | 74 6f 20 64 6f 20 6c 65 |outines |to do le|
|00001310| 66 74 20 72 6f 74 61 74 | 69 6f 6e 73 2c 0a 58 61 |ft rotat|ions,.Xa|
|00001320| 6e 64 20 72 69 67 68 74 | 20 72 6f 74 61 74 69 6f |nd right| rotatio|
|00001330| 6e 73 2c 20 6f 6e 65 20 | 72 6f 75 74 69 6e 65 20 |ns, one |routine |
|00001340| 74 68 61 74 20 74 61 6b | 65 73 20 74 68 65 20 64 |that tak|es the d|
|00001350| 69 72 65 63 74 69 6f 6e | 20 61 73 20 61 6e 20 0a |irection| as an .|
|00001360| 58 65 78 74 72 61 20 70 | 61 72 61 6d 65 74 65 72 |Xextra p|arameter|
|00001370| 20 77 69 6c 6c 20 64 6f | 2e 0a 58 0a 58 43 41 4c | will do|..X.XCAL|
|00001380| 43 55 4c 41 54 49 4e 47 | 20 4e 45 57 20 42 41 4c |CULATING| NEW BAL|
|00001390| 41 4e 43 45 53 20 41 46 | 54 45 52 20 41 20 52 4f |ANCES AF|TER A RO|
|000013a0| 54 41 54 49 4f 4e 3a 0a | 58 3d 3d 3d 3d 3d 3d 3d |TATION:.|X=======|
|000013b0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000013c0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000013d0| 3d 3d 3d 0a 58 54 6f 20 | 63 61 6c 63 75 6c 61 74 |===.XTo |calculat|
|000013e0| 65 20 74 68 65 20 6e 65 | 77 20 62 61 6c 61 6e 63 |e the ne|w balanc|
|000013f0| 65 73 20 61 66 74 65 72 | 20 61 20 73 69 6e 67 6c |es after| a singl|
|00001400| 65 20 6c 65 66 74 20 72 | 6f 74 61 74 69 6f 6e 3b |e left r|otation;|
|00001410| 20 61 73 73 75 6d 65 20 | 77 65 20 68 61 76 65 0a | assume |we have.|
|00001420| 58 74 68 65 20 66 6f 6c | 6c 6f 77 69 6e 67 20 63 |Xthe fol|lowing c|
|00001430| 61 73 65 3a 0a 58 0a 58 | 20 20 20 20 20 20 20 20 |ase:.X.X| |
|00001440| 20 20 20 20 20 20 20 20 | 20 20 41 20 20 20 20 20 | | A |
|00001450| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001460| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001470| 42 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |B.X | |
|00001480| 20 20 20 20 2f 20 5c 20 | 20 20 20 20 20 20 20 20 | / \ | |
|00001490| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014a0| 20 20 20 20 20 20 20 20 | 20 20 2f 20 5c 0a 58 20 | | / \.X |
|000014b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f | | /|
|000014c0| 20 20 20 5c 20 20 20 20 | 20 20 20 20 20 20 20 20 | \ | |
|000014d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014e0| 20 20 20 20 20 2f 20 20 | 20 5c 0a 58 20 20 20 20 | / | \.X |
|000014f0| 20 20 20 20 20 20 20 20 | 20 20 20 61 20 20 20 20 | | a |
|00001500| 20 42 20 20 20 20 20 20 | 20 20 20 20 20 3d 3d 3e | B | ==>|
|00001510| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001520| 20 41 20 20 20 20 20 63 | 0a 58 20 20 20 20 20 20 | A c|.X |
|00001530| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 20 | | / |
|00001540| 5c 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |\ | |
|00001550| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 20 | | / |
|00001560| 5c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |\.X | |
|00001570| 20 20 20 20 20 20 2f 20 | 20 20 5c 20 20 20 20 20 | / | \ |
|00001580| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001590| 20 20 20 20 20 20 2f 20 | 20 20 5c 0a 58 20 20 20 | / | \.X |
|000015a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 62 | | b|
|000015b0| 20 20 20 20 20 63 20 20 | 20 20 20 20 20 20 20 20 | c | |
|000015c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | | a|
|000015d0| 20 20 20 20 20 62 0a 58 | 0a 58 0a 58 54 68 65 20 | b.X|.X.XThe |
|000015e0| 6c 65 66 74 20 69 73 20 | 77 68 61 74 20 74 68 65 |left is |what the|
|000015f0| 20 74 72 65 65 20 6c 6f | 6f 6b 65 64 20 6c 69 6b | tree lo|oked lik|
|00001600| 65 20 42 45 46 4f 52 45 | 20 74 68 65 20 72 6f 74 |e BEFORE| the rot|
|00001610| 61 74 69 6f 6e 20 61 6e | 64 20 74 68 65 20 72 69 |ation an|d the ri|
|00001620| 67 68 74 0a 58 69 73 20 | 77 68 61 74 20 74 68 65 |ght.Xis |what the|
|00001630| 20 74 72 65 65 20 6c 6f | 6f 6b 73 20 6c 69 6b 65 | tree lo|oks like|
|00001640| 20 61 66 74 65 72 20 74 | 68 65 20 72 6f 74 61 74 | after t|he rotat|
|00001650| 69 6f 6e 2e 20 43 61 70 | 69 74 61 6c 20 6c 65 74 |ion. Cap|ital let|
|00001660| 74 65 72 73 20 61 72 65 | 20 75 73 65 64 0a 58 74 |ters are| used.Xt|
|00001670| 6f 20 64 65 6e 6f 74 65 | 20 73 69 6e 67 6c 65 20 |o denote| single |
|00001680| 6e 6f 64 65 73 20 61 6e | 64 20 6c 6f 77 65 72 63 |nodes an|d lowerc|
|00001690| 61 73 65 20 6c 65 74 74 | 65 72 73 20 61 72 65 20 |ase lett|ers are |
|000016a0| 75 73 65 64 20 74 6f 20 | 64 65 6e 6f 74 65 20 73 |used to |denote s|
|000016b0| 75 62 74 72 65 65 73 2e | 0a 58 0c 0a 58 54 68 65 |ubtrees.|.X..XThe|
|000016c0| 20 22 62 61 6c 61 6e 63 | 65 22 20 6f 66 20 61 20 | "balanc|e" of a |
|000016d0| 74 72 65 65 20 69 73 20 | 74 68 65 20 68 65 69 67 |tree is |the heig|
|000016e0| 68 74 20 6f 66 20 69 74 | 73 20 72 69 67 68 74 20 |ht of it|s right |
|000016f0| 73 75 62 74 72 65 65 20 | 6c 65 73 73 20 74 68 65 |subtree |less the|
|00001700| 0a 58 68 65 69 67 68 74 | 20 6f 66 20 69 74 73 20 |.Xheight| of its |
|00001710| 6c 65 66 74 20 73 75 62 | 74 72 65 65 2e 20 54 68 |left sub|tree. Th|
|00001720| 65 72 65 66 6f 72 65 2c | 20 77 65 20 63 61 6e 20 |erefore,| we can |
|00001730| 63 61 6c 63 75 6c 61 74 | 65 20 74 68 65 20 6e 65 |calculat|e the ne|
|00001740| 77 20 62 61 6c 61 6e 63 | 65 73 0a 58 6f 66 20 22 |w balanc|es.Xof "|
|00001750| 41 22 20 61 6e 64 20 22 | 42 22 20 61 73 20 66 6f |A" and "|B" as fo|
|00001760| 6c 6c 6f 77 73 20 28 68 | 74 20 69 73 20 74 68 65 |llows (h|t is the|
|00001770| 20 68 65 69 67 68 74 20 | 66 75 6e 63 74 69 6f 6e | height |function|
|00001780| 29 3a 0a 58 0a 58 20 20 | 20 20 20 20 20 20 4e 65 |):.X.X | Ne|
|00001790| 77 42 61 6c 28 41 29 20 | 3d 20 68 74 28 62 29 20 |wBal(A) |= ht(b) |
|000017a0| 2d 20 68 74 28 61 29 0a | 58 0a 58 20 20 20 20 20 |- ht(a).|X.X |
|000017b0| 20 20 20 4f 6c 64 42 61 | 6c 28 41 29 20 3d 20 68 | OldBa|l(A) = h|
|000017c0| 74 28 42 29 20 2d 20 68 | 74 28 61 29 0a 58 20 20 |t(B) - h|t(a).X |
|000017d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000017e0| 3d 20 28 20 31 20 2b 20 | 6d 61 78 20 28 68 74 28 |= ( 1 + |max (ht(|
|000017f0| 62 29 2c 20 68 74 28 63 | 29 29 20 29 20 2d 20 68 |b), ht(c|)) ) - h|
|00001800| 74 28 61 29 0a 58 0a 58 | 0a 58 73 75 62 74 72 61 |t(a).X.X|.Xsubtra|
|00001810| 63 74 69 6e 67 20 74 68 | 65 20 73 65 63 6f 6e 64 |cting th|e second|
|00001820| 20 65 71 75 61 74 69 6f | 6e 20 66 72 6f 6d 20 74 | equatio|n from t|
|00001830| 68 65 20 66 69 72 73 74 | 20 79 69 65 6c 64 73 3a |he first| yields:|
|00001840| 0a 58 0a 58 0a 58 20 20 | 20 20 20 20 20 20 4e 65 |.X.X.X | Ne|
|00001850| 77 42 61 6c 28 41 29 20 | 2d 20 4f 6c 64 42 61 6c |wBal(A) |- OldBal|
|00001860| 28 41 29 20 3d 20 68 74 | 28 62 29 20 2d 20 28 20 |(A) = ht|(b) - ( |
|00001870| 31 20 2b 20 6d 61 78 20 | 28 68 74 28 62 29 2c 20 |1 + max |(ht(b), |
|00001880| 68 74 28 63 29 29 20 29 | 0a 58 20 20 20 20 20 20 |ht(c)) )|.X |
|00001890| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018a0| 20 20 20 20 20 20 20 20 | 20 20 2b 20 68 74 28 61 | | + ht(a|
|000018b0| 29 20 2d 20 68 74 28 61 | 29 0a 58 0a 58 0a 58 63 |) - ht(a|).X.X.Xc|
|000018c0| 61 6e 63 65 6c 69 6e 67 | 20 6f 75 74 20 74 68 65 |anceling| out the|
|000018d0| 20 68 74 28 61 29 20 74 | 65 72 6d 73 20 61 6e 64 | ht(a) t|erms and|
|000018e0| 20 61 64 64 69 6e 67 20 | 4f 6c 64 42 61 6c 28 41 | adding |OldBal(A|
|000018f0| 29 20 74 6f 20 62 6f 74 | 68 20 73 69 64 65 73 20 |) to bot|h sides |
|00001900| 79 69 65 6c 64 73 3a 0a | 58 0a 58 0a 58 20 20 20 |yields:.|X.X.X |
|00001910| 20 20 20 20 20 4e 65 77 | 42 61 6c 28 41 29 20 3d | New|Bal(A) =|
|00001920| 20 4f 6c 64 42 61 6c 28 | 41 29 20 2d 20 31 20 2d | OldBal(|A) - 1 -|
|00001930| 20 28 6d 61 78 20 28 68 | 74 28 62 29 2c 20 68 74 | (max (h|t(b), ht|
|00001940| 28 63 29 29 20 2d 20 68 | 74 28 62 29 20 29 0a 58 |(c)) - h|t(b) ).X|
|00001950| 0a 58 0a 58 4e 6f 74 69 | 6e 67 20 74 68 61 74 20 |.X.XNoti|ng that |
|00001960| 20 20 6d 61 78 28 78 2c | 20 79 29 20 2d 20 7a 20 | max(x,| y) - z |
|00001970| 20 3d 20 20 6d 61 78 28 | 78 2d 7a 2c 20 79 2d 7a | = max(|x-z, y-z|
|00001980| 29 2c 20 77 65 20 67 65 | 74 3a 0a 58 0a 58 0a 58 |), we ge|t:.X.X.X|
|00001990| 20 20 20 20 20 20 20 20 | 4e 65 77 42 61 6c 28 41 | |NewBal(A|
|000019a0| 29 20 3d 20 4f 6c 64 42 | 61 6c 28 41 29 20 2d 20 |) = OldB|al(A) - |
|000019b0| 31 20 2d 20 28 6d 61 78 | 20 28 68 74 28 62 29 20 |1 - (max| (ht(b) |
|000019c0| 2d 20 68 74 28 62 29 2c | 20 68 74 28 63 29 20 2d |- ht(b),| ht(c) -|
|000019d0| 20 68 74 28 62 29 29 20 | 29 0a 58 0a 58 0a 58 42 | ht(b)) |).X.X.XB|
|000019e0| 75 74 20 20 20 68 74 28 | 63 29 20 2d 20 68 74 28 |ut ht(|c) - ht(|
|000019f0| 62 29 20 20 69 73 20 20 | 4f 6c 64 42 61 6c 28 42 |b) is |OldBal(B|
|00001a00| 29 20 20 73 6f 20 77 65 | 20 67 65 74 3a 0a 58 0a |) so we| get:.X.|
|00001a10| 58 0a 58 20 20 20 20 20 | 20 20 20 4e 65 77 42 61 |X.X | NewBa|
|00001a20| 6c 28 41 29 20 3d 20 4f | 6c 64 42 61 6c 28 41 29 |l(A) = O|ldBal(A)|
|00001a30| 20 2d 20 31 20 2d 20 28 | 6d 61 78 20 28 30 2c 20 | - 1 - (|max (0, |
|00001a40| 4f 6c 64 42 61 6c 28 42 | 29 29 20 29 0a 58 20 20 |OldBal(B|)) ).X |
|00001a50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001a60| 3d 20 4f 6c 64 42 61 6c | 28 41 29 20 2d 20 31 20 |= OldBal|(A) - 1 |
|00001a70| 2d 20 20 6d 61 78 20 28 | 30 2c 20 4f 6c 64 42 61 |- max (|0, OldBa|
|00001a80| 6c 28 42 29 29 0a 58 0a | 58 54 68 75 73 2c 20 66 |l(B)).X.|XThus, f|
|00001a90| 6f 72 20 41 2c 20 77 65 | 20 67 65 74 20 74 68 65 |or A, we| get the|
|00001aa0| 20 65 71 75 61 74 69 6f | 6e 3a 0a 58 0a 58 20 20 | equatio|n:.X.X |
|00001ab0| 20 20 20 20 20 20 4e 65 | 77 42 61 6c 28 41 29 20 | Ne|wBal(A) |
|00001ac0| 3d 20 4f 6c 64 42 61 6c | 28 41 29 20 2d 20 31 20 |= OldBal|(A) - 1 |
|00001ad0| 2d 20 6d 61 78 20 28 30 | 2c 20 4f 6c 64 42 61 6c |- max (0|, OldBal|
|00001ae0| 28 42 29 29 0a 58 0c 0a | 58 54 6f 20 63 61 6c 63 |(B)).X..|XTo calc|
|00001af0| 75 6c 61 74 65 20 74 68 | 65 20 42 61 6c 61 6e 63 |ulate th|e Balanc|
|00001b00| 65 20 66 6f 72 20 42 20 | 77 65 20 70 65 72 66 6f |e for B |we perfo|
|00001b10| 72 6d 20 61 20 73 69 6d | 69 6c 61 72 20 63 6f 6d |rm a sim|ilar com|
|00001b20| 70 75 74 61 74 69 6f 6e | 3a 0a 58 0a 58 20 20 20 |putation|:.X.X |
|00001b30| 20 20 20 20 20 4e 65 77 | 42 61 6c 28 42 29 20 3d | New|Bal(B) =|
|00001b40| 20 68 74 28 63 29 20 2d | 20 68 74 28 41 29 0a 58 | ht(c) -| ht(A).X|
|00001b50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001b60| 20 20 3d 20 68 74 28 63 | 29 20 2d 20 28 31 20 2b | = ht(c|) - (1 +|
|00001b70| 20 6d 61 78 28 68 74 28 | 61 29 2c 20 68 74 28 62 | max(ht(|a), ht(b|
|00001b80| 29 29 20 29 0a 58 0a 58 | 20 20 20 20 20 20 20 20 |)) ).X.X| |
|00001b90| 4f 6c 64 42 61 6c 28 42 | 29 20 3d 20 68 74 28 63 |OldBal(B|) = ht(c|
|00001ba0| 29 20 2d 20 68 74 28 62 | 29 0a 58 0a 58 0a 58 73 |) - ht(b|).X.X.Xs|
|00001bb0| 75 62 74 72 61 63 74 69 | 6e 67 20 74 68 65 20 73 |ubtracti|ng the s|
|00001bc0| 65 63 6f 6e 64 20 65 71 | 75 61 74 69 6f 6e 20 66 |econd eq|uation f|
|00001bd0| 72 6f 6d 20 74 68 65 20 | 66 69 72 73 74 20 79 69 |rom the |first yi|
|00001be0| 65 6c 64 73 3a 0a 58 0a | 58 0a 58 20 20 20 20 20 |elds:.X.|X.X |
|00001bf0| 20 20 20 4e 65 77 42 61 | 6c 28 42 29 20 2d 20 4f | NewBa|l(B) - O|
|00001c00| 6c 64 42 61 6c 28 42 29 | 20 3d 20 68 74 28 63 29 |ldBal(B)| = ht(c)|
|00001c10| 20 2d 20 68 74 28 63 29 | 0a 58 20 20 20 20 20 20 | - ht(c)|.X |
|00001c20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c30| 20 20 20 20 20 20 20 20 | 20 20 2b 20 68 74 28 62 | | + ht(b|
|00001c40| 29 20 2d 20 28 31 20 2b | 20 6d 61 78 28 68 74 28 |) - (1 +| max(ht(|
|00001c50| 61 29 2c 20 68 74 28 62 | 29 29 20 29 0a 58 0a 58 |a), ht(b|)) ).X.X|
|00001c60| 0a 58 63 61 6e 63 65 6c | 69 6e 67 2c 20 61 6e 64 |.Xcancel|ing, and|
|00001c70| 20 61 64 64 69 6e 67 20 | 4f 6c 64 42 61 6c 28 42 | adding |OldBal(B|
|00001c80| 29 20 74 6f 20 62 6f 74 | 68 20 73 69 64 65 73 20 |) to bot|h sides |
|00001c90| 67 69 76 65 73 3a 0a 58 | 0a 58 0a 58 20 20 20 20 |gives:.X|.X.X |
|00001ca0| 20 20 20 20 4e 65 77 42 | 61 6c 28 42 29 20 3d 20 | NewB|al(B) = |
|00001cb0| 4f 6c 64 42 61 6c 28 42 | 29 20 2d 20 31 20 2d 20 |OldBal(B|) - 1 - |
|00001cc0| 28 6d 61 78 28 68 74 28 | 61 29 2c 20 68 74 28 62 |(max(ht(|a), ht(b|
|00001cd0| 29 29 20 2d 20 68 74 28 | 62 29 29 0a 58 20 20 20 |)) - ht(|b)).X |
|00001ce0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 3d | | =|
|00001cf0| 20 4f 6c 64 42 61 6c 28 | 42 29 20 2d 20 31 20 2d | OldBal(|B) - 1 -|
|00001d00| 20 28 6d 61 78 28 68 74 | 28 61 29 20 2d 20 68 74 | (max(ht|(a) - ht|
|00001d10| 28 62 29 2c 20 68 74 28 | 62 29 20 2d 20 68 74 28 |(b), ht(|b) - ht(|
|00001d20| 62 29 29 0a 58 0a 58 0a | 58 42 75 74 20 20 68 74 |b)).X.X.|XBut ht|
|00001d30| 28 61 29 20 2d 20 68 74 | 28 62 29 20 20 69 73 20 |(a) - ht|(b) is |
|00001d40| 20 2d 20 28 68 74 28 62 | 29 20 2d 20 68 74 28 61 | - (ht(b|) - ht(a|
|00001d50| 29 29 20 20 3d 20 20 2d | 4e 65 77 42 61 6c 28 41 |)) = -|NewBal(A|
|00001d60| 29 2c 20 73 6f 20 2e 2e | 2e 0a 58 0a 58 0a 58 20 |), so ..|..X.X.X |
|00001d70| 20 20 20 20 20 20 20 4e | 65 77 42 61 6c 28 42 29 | N|ewBal(B)|
|00001d80| 20 3d 20 4f 6c 64 42 61 | 6c 28 42 29 20 2d 20 31 | = OldBa|l(B) - 1|
|00001d90| 20 2d 20 6d 61 78 28 20 | 2d 4e 65 77 42 61 6c 28 | - max( |-NewBal(|
|00001da0| 41 29 2c 20 30 29 0a 58 | 0a 58 0a 58 55 73 69 6e |A), 0).X|.X.XUsin|
|00001db0| 67 20 74 68 65 20 66 61 | 63 74 20 74 68 61 74 20 |g the fa|ct that |
|00001dc0| 20 6d 69 6e 28 78 2c 79 | 29 20 3d 20 2d 6d 61 78 | min(x,y|) = -max|
|00001dd0| 28 2d 78 2c 20 2d 79 29 | 20 77 65 20 67 65 74 3a |(-x, -y)| we get:|
|00001de0| 0a 58 0a 58 0a 58 20 20 | 20 20 20 20 20 20 4e 65 |.X.X.X | Ne|
|00001df0| 77 42 61 6c 28 42 29 20 | 3d 20 4f 6c 64 42 61 6c |wBal(B) |= OldBal|
|00001e00| 28 42 29 20 2d 20 31 20 | 2b 20 6d 69 6e 28 20 4e |(B) - 1 |+ min( N|
|00001e10| 65 77 42 61 6c 28 41 29 | 2c 20 30 29 0a 58 0a 58 |ewBal(A)|, 0).X.X|
|00001e20| 0a 58 53 6f 2c 20 66 6f | 72 20 61 20 73 69 6e 67 |.XSo, fo|r a sing|
|00001e30| 6c 65 20 6c 65 66 74 20 | 72 6f 74 61 74 69 6f 6e |le left |rotation|
|00001e40| 20 77 65 20 68 61 76 65 | 20 73 68 6f 77 6e 20 74 | we have| shown t|
|00001e50| 68 65 20 74 68 65 20 6e | 65 77 20 62 61 6c 61 6e |he the n|ew balan|
|00001e60| 63 65 73 0a 58 66 6f 72 | 20 74 68 65 20 6e 6f 64 |ces.Xfor| the nod|
|00001e70| 65 73 20 41 20 61 6e 64 | 20 42 20 61 72 65 20 67 |es A and| B are g|
|00001e80| 69 76 65 6e 20 62 79 20 | 74 68 65 20 66 6f 6c 6c |iven by |the foll|
|00001e90| 6f 77 69 6e 67 20 65 71 | 75 61 74 69 6f 6e 73 3a |owing eq|uations:|
|00001ea0| 0a 58 0a 58 20 20 20 20 | 20 20 20 20 4e 65 77 42 |.X.X | NewB|
|00001eb0| 61 6c 28 41 29 20 3d 20 | 4f 6c 64 42 61 6c 28 41 |al(A) = |OldBal(A|
|00001ec0| 29 20 2d 20 31 20 2d 20 | 6d 61 78 28 4f 6c 64 42 |) - 1 - |max(OldB|
|00001ed0| 61 6c 28 42 29 2c 20 30 | 29 0a 58 20 20 20 20 20 |al(B), 0|).X |
|00001ee0| 20 20 20 4e 65 77 42 61 | 6c 28 42 29 20 3d 20 4f | NewBa|l(B) = O|
|00001ef0| 6c 64 42 61 6c 28 42 29 | 20 2d 20 31 20 2b 20 6d |ldBal(B)| - 1 + m|
|00001f00| 69 6e 28 4e 65 77 42 61 | 6c 28 41 29 2c 20 30 29 |in(NewBa|l(A), 0)|
|00001f10| 0a 58 0a 58 4e 6f 77 20 | 6c 65 74 20 75 73 20 6c |.X.XNow |let us l|
|00001f20| 6f 6f 6b 20 61 74 20 74 | 68 65 20 63 61 73 65 20 |ook at t|he case |
|00001f30| 6f 66 20 61 20 73 69 6e | 67 6c 65 20 72 69 67 68 |of a sin|gle righ|
|00001f40| 74 20 72 6f 74 61 74 69 | 6f 6e 2e 20 54 68 65 20 |t rotati|on. The |
|00001f50| 63 61 73 65 0a 58 77 65 | 20 77 69 6c 6c 20 75 73 |case.Xwe| will us|
|00001f60| 65 20 69 73 20 74 68 65 | 20 73 61 6d 65 20 6f 6e |e is the| same on|
|00001f70| 65 20 77 65 20 75 73 65 | 64 20 66 6f 72 20 74 68 |e we use|d for th|
|00001f80| 65 20 73 69 6e 67 6c 65 | 20 6c 65 66 74 20 72 6f |e single| left ro|
|00001f90| 74 61 74 69 6f 6e 0a 58 | 6f 6e 6c 79 20 77 69 74 |tation.X|only wit|
|00001fa0| 68 20 61 6c 6c 20 74 68 | 65 20 6c 65 66 74 20 61 |h all th|e left a|
|00001fb0| 6e 64 20 72 69 67 68 74 | 20 73 75 62 74 72 65 65 |nd right| subtree|
|00001fc0| 73 20 73 77 69 74 63 68 | 65 64 20 61 72 6f 75 6e |s switch|ed aroun|
|00001fd0| 64 20 73 6f 20 74 68 61 | 74 0a 58 77 65 20 68 61 |d so tha|t.Xwe ha|
|00001fe0| 76 65 20 74 68 65 20 6d | 69 72 72 6f 72 20 69 6d |ve the m|irror im|
|00001ff0| 61 67 65 20 6f 66 20 74 | 68 65 20 63 61 73 65 20 |age of t|he case |
|00002000| 77 65 20 75 73 65 64 20 | 66 6f 72 20 6f 75 72 20 |we used |for our |
|00002010| 6c 65 66 74 20 72 6f 74 | 61 74 69 6f 6e 2e 0a 58 |left rot|ation..X|
|00002020| 0a 58 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X.X | |
|00002030| 20 20 20 20 20 20 41 20 | 20 20 20 20 20 20 20 20 | A | |
|00002040| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002050| 20 20 20 20 20 20 20 20 | 20 20 20 20 42 0a 58 20 | | B.X |
|00002060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002070| 2f 20 5c 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |/ \ | |
|00002080| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002090| 20 20 20 20 20 20 2f 20 | 5c 0a 58 20 20 20 20 20 | / |\.X |
|000020a0| 20 20 20 20 20 20 20 20 | 20 20 20 2f 20 20 20 5c | | / \|
|000020b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000020c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000020d0| 20 2f 20 20 20 5c 0a 58 | 20 20 20 20 20 20 20 20 | / \.X| |
|000020e0| 20 20 20 20 20 20 20 42 | 20 20 20 20 20 61 20 20 | B| a |
|000020f0| 20 20 20 20 20 20 20 20 | 20 3d 3d 3e 20 20 20 20 | | ==> |
|00002100| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 63 20 20 | | c |
|00002110| 20 20 20 41 0a 58 20 20 | 20 20 20 20 20 20 20 20 | A.X | |
|00002120| 20 20 20 20 2f 20 5c 20 | 20 20 20 20 20 20 20 20 | / \ | |
|00002130| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002140| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002150| 2f 20 5c 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |/ \.X | |
|00002160| 20 20 2f 20 20 20 5c 20 | 20 20 20 20 20 20 20 20 | / \ | |
|00002170| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 20 | | / |
|00002190| 20 20 5c 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 | \.X | |
|000021a0| 20 63 20 20 20 20 20 62 | 20 20 20 20 20 20 20 20 | c b| |
|000021b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000021c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 62 20 20 | | b |
|000021d0| 20 20 20 61 0a 58 0a 58 | 0a 58 49 66 20 77 65 20 | a.X.X|.XIf we |
|000021e0| 70 65 72 66 6f 72 6d 20 | 74 68 65 20 73 61 6d 65 |perform |the same|
|000021f0| 20 63 61 6c 63 75 6c 61 | 74 69 6f 6e 73 20 74 68 | calcula|tions th|
|00002200| 61 74 20 77 65 20 6d 61 | 64 65 20 66 6f 72 20 74 |at we ma|de for t|
|00002210| 68 65 20 6c 65 66 74 20 | 72 6f 74 61 74 69 6f 6e |he left |rotation|
|00002220| 2c 0a 58 77 65 20 77 69 | 6c 6c 20 73 65 65 20 74 |,.Xwe wi|ll see t|
|00002230| 68 61 74 20 74 68 65 20 | 6e 65 77 20 62 61 6c 61 |hat the |new bala|
|00002240| 6e 63 65 73 20 66 6f 72 | 20 61 20 73 69 6e 67 6c |nces for| a singl|
|00002250| 65 20 72 69 67 68 74 20 | 72 6f 74 61 74 69 6f 6e |e right |rotation|
|00002260| 20 61 72 65 20 67 69 76 | 65 6e 20 0a 58 62 79 20 | are giv|en .Xby |
|00002270| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 65 71 |the foll|owing eq|
|00002280| 75 61 74 69 6f 6e 73 3a | 0a 58 0a 58 20 20 20 20 |uations:|.X.X |
|00002290| 20 20 20 20 4e 65 77 42 | 61 6c 28 41 29 20 3d 20 | NewB|al(A) = |
|000022a0| 4f 6c 64 42 61 6c 28 41 | 29 20 2b 20 31 20 2d 20 |OldBal(A|) + 1 - |
|000022b0| 6d 69 6e 28 4f 6c 64 42 | 61 6c 28 42 29 2c 20 30 |min(OldB|al(B), 0|
|000022c0| 29 0a 58 20 20 20 20 20 | 20 20 20 4e 65 77 42 61 |).X | NewBa|
|000022d0| 6c 28 42 29 20 3d 20 4f | 6c 64 42 61 6c 28 42 29 |l(B) = O|ldBal(B)|
|000022e0| 20 2b 20 31 20 2b 20 6d | 61 78 28 4e 65 77 42 61 | + 1 + m|ax(NewBa|
|000022f0| 6c 28 41 29 2c 20 30 29 | 0a 58 0c 0a 58 48 65 6e |l(A), 0)|.X..XHen|
|00002300| 63 65 2c 20 74 68 65 20 | 43 20 63 6f 64 65 20 66 |ce, the |C code f|
|00002310| 6f 72 20 73 69 6e 67 6c | 65 20 6c 65 66 74 20 61 |or singl|e left a|
|00002320| 6e 64 20 72 69 67 68 74 | 20 72 6f 74 61 74 69 6f |nd right| rotatio|
|00002330| 6e 73 20 77 6f 75 6c 64 | 20 62 65 3a 0a 58 0a 58 |ns would| be:.X.X|
|00002340| 20 20 20 20 20 20 20 20 | 23 64 65 66 69 6e 65 20 | |#define |
|00002350| 4c 45 46 54 20 20 30 0a | 58 20 20 20 20 20 20 20 |LEFT 0.|X |
|00002360| 20 23 64 65 66 69 6e 65 | 20 52 49 47 48 54 20 31 | #define| RIGHT 1|
|00002370| 0a 58 0a 58 20 20 20 20 | 20 20 20 20 23 64 65 66 |.X.X | #def|
|00002380| 69 6e 65 20 4d 41 58 28 | 61 2c 62 29 20 20 28 20 |ine MAX(|a,b) ( |
|00002390| 28 61 29 20 3e 20 28 62 | 29 20 3f 20 28 61 29 20 |(a) > (b|) ? (a) |
|000023a0| 3a 20 28 62 29 20 29 0a | 58 20 20 20 20 20 20 20 |: (b) ).|X |
|000023b0| 20 23 64 65 66 69 6e 65 | 20 4d 49 4e 28 61 2c 62 | #define| MIN(a,b|
|000023c0| 29 20 20 28 20 28 61 29 | 20 3c 20 28 62 29 20 3f |) ( (a)| < (b) ?|
|000023d0| 20 28 61 29 20 3a 20 28 | 62 29 20 29 0a 58 0a 58 | (a) : (|b) ).X.X|
|000023e0| 20 20 20 20 20 20 20 20 | 74 79 70 65 64 65 66 20 | |typedef |
|000023f0| 73 74 72 75 63 74 20 61 | 76 6c 5f 6e 6f 64 65 20 |struct a|vl_node |
|00002400| 20 7b 0a 58 20 20 20 20 | 20 20 20 20 20 20 44 41 | {.X | DA|
|00002410| 54 41 5f 54 59 50 45 20 | 20 20 20 20 20 20 20 20 |TA_TYPE | |
|00002420| 64 61 74 61 3b 0a 58 20 | 20 20 20 20 20 20 20 20 |data;.X | |
|00002430| 20 73 68 6f 72 74 20 20 | 20 20 20 20 20 20 20 20 | short | |
|00002440| 20 20 20 62 61 6c 3b 0a | 58 20 20 20 20 20 20 20 | bal;.|X |
|00002450| 20 20 20 73 74 72 75 63 | 74 20 61 76 6c 5f 6e 6f | struc|t avl_no|
|00002460| 64 65 20 20 2a 73 75 62 | 74 72 65 65 5b 32 5d 3b |de *sub|tree[2];|
|00002470| 0a 58 20 20 20 20 20 20 | 20 20 20 7d 20 41 56 4c |.X | } AVL|
|00002480| 5f 4e 4f 44 45 2c 20 2a | 41 56 4c 5f 54 52 45 45 |_NODE, *|AVL_TREE|
|00002490| 3b 20 2f 2a 20 61 76 6c | 5f 6e 6f 64 65 20 2a 2f |; /* avl|_node */|
|000024a0| 0a 58 0a 58 20 20 20 20 | 20 20 20 20 76 6f 69 64 |.X.X | void|
|000024b0| 20 72 6f 74 61 74 65 5f | 6c 65 66 74 20 28 74 72 | rotate_|left (tr|
|000024c0| 65 65 29 0a 58 20 20 20 | 20 20 20 20 20 20 20 41 |ee).X | A|
|000024d0| 56 4c 5f 54 52 45 45 20 | 20 74 72 65 65 3b 0a 58 |VL_TREE | tree;.X|
|000024e0| 20 20 20 20 20 20 20 20 | 7b 0a 58 20 20 20 20 20 | |{.X |
|000024f0| 20 20 20 20 20 41 56 4c | 5f 54 52 45 45 20 20 6f | AVL|_TREE o|
|00002500| 6c 64 5f 72 6f 6f 74 20 | 3d 20 74 72 65 65 3b 0a |ld_root |= tree;.|
|00002510| 58 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X.X | |
|00002520| 20 20 20 2f 2a 20 70 65 | 72 66 6f 72 6d 20 72 6f | /* pe|rform ro|
|00002530| 74 61 74 69 6f 6e 20 2a | 2f 0a 58 20 20 20 20 20 |tation *|/.X |
|00002540| 20 20 20 20 20 74 72 65 | 65 20 3d 20 74 72 65 65 | tre|e = tree|
|00002550| 2d 3e 73 75 62 74 72 65 | 65 5b 52 49 47 48 54 5d |->subtre|e[RIGHT]|
|00002560| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 6f 6c 64 |;.X | old|
|00002570| 5f 72 6f 6f 74 2d 3e 73 | 75 62 74 72 65 65 5b 52 |_root->s|ubtree[R|
|00002580| 49 47 48 54 5d 20 3d 20 | 74 72 65 65 2d 3e 73 75 |IGHT] = |tree->su|
|00002590| 62 74 72 65 65 5b 4c 45 | 46 54 5d 3b 20 0a 58 20 |btree[LE|FT]; .X |
|000025a0| 20 20 20 20 20 20 20 20 | 20 74 72 65 65 2d 3e 73 | | tree->s|
|000025b0| 75 62 74 72 65 65 5b 4c | 45 46 54 5d 20 3d 20 6f |ubtree[L|EFT] = o|
|000025c0| 6c 64 5f 72 6f 6f 74 3b | 0a 58 0a 58 20 20 20 20 |ld_root;|.X.X |
|000025d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 75 | | /* u|
|000025e0| 70 64 61 74 65 20 62 61 | 6c 61 6e 63 65 73 20 2a |pdate ba|lances *|
|000025f0| 2f 0a 58 20 20 20 20 20 | 20 20 20 20 20 6f 6c 64 |/.X | old|
|00002600| 5f 72 6f 6f 74 2d 3e 62 | 61 6c 20 2d 3d 20 20 28 |_root->b|al -= (|
|00002610| 20 31 20 2b 20 4d 41 58 | 28 74 72 65 65 2d 3e 62 | 1 + MAX|(tree->b|
|00002620| 61 6c 2c 20 30 29 20 29 | 3b 0a 58 20 20 20 20 20 |al, 0) )|;.X |
|00002630| 20 20 20 20 20 74 72 65 | 65 2d 3e 62 61 6c 20 20 | tre|e->bal |
|00002640| 20 20 20 2d 3d 20 20 28 | 20 31 20 2d 20 4d 49 4e | -= (| 1 - MIN|
|00002650| 28 6f 6c 64 5f 72 6f 6f | 74 2d 3e 62 61 6c 2c 20 |(old_roo|t->bal, |
|00002660| 30 29 20 29 3b 0a 58 20 | 20 20 20 20 20 20 20 7d |0) );.X | }|
|00002670| 2f 2a 20 72 6f 74 61 74 | 65 5f 6c 65 66 74 20 2a |/* rotat|e_left *|
|00002680| 2f 0a 58 0a 58 0a 58 20 | 20 20 20 20 20 20 20 76 |/.X.X.X | v|
|00002690| 6f 69 64 20 72 6f 74 61 | 74 65 5f 72 69 67 68 74 |oid rota|te_right|
|000026a0| 20 28 74 72 65 65 29 0a | 58 20 20 20 20 20 20 20 | (tree).|X |
|000026b0| 20 20 20 41 56 4c 5f 54 | 52 45 45 20 20 74 72 65 | AVL_T|REE tre|
|000026c0| 65 3b 0a 58 20 20 20 20 | 20 20 20 20 7b 0a 58 20 |e;.X | {.X |
|000026d0| 20 20 20 20 20 20 20 20 | 20 41 56 4c 5f 54 52 45 | | AVL_TRE|
|000026e0| 45 20 20 6f 6c 64 5f 72 | 6f 6f 74 20 3d 20 74 72 |E old_r|oot = tr|
|000026f0| 65 65 3b 0a 58 0a 58 20 | 20 20 20 20 20 20 20 20 |ee;.X.X | |
|00002700| 20 20 20 20 20 20 20 2f | 2a 20 70 65 72 66 6f 72 | /|* perfor|
|00002710| 6d 20 72 6f 74 61 74 69 | 6f 6e 20 2a 2f 0a 58 20 |m rotati|on */.X |
|00002720| 20 20 20 20 20 20 20 20 | 20 74 72 65 65 20 3d 20 | | tree = |
|00002730| 74 72 65 65 2d 3e 73 75 | 62 74 72 65 65 5b 4c 45 |tree->su|btree[LE|
|00002740| 46 54 5d 3b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |FT];.X | |
|00002750| 6f 6c 64 5f 72 6f 6f 74 | 2d 3e 73 75 62 74 72 65 |old_root|->subtre|
|00002760| 65 5b 4c 45 46 54 5d 20 | 3d 20 74 72 65 65 2d 3e |e[LEFT] |= tree->|
|00002770| 73 75 62 74 72 65 65 5b | 52 49 47 48 54 5d 3b 20 |subtree[|RIGHT]; |
|00002780| 0a 58 20 20 20 20 20 20 | 20 20 20 20 74 72 65 65 |.X | tree|
|00002790| 2d 3e 73 75 62 74 72 65 | 65 5b 52 49 47 48 54 5d |->subtre|e[RIGHT]|
|000027a0| 20 3d 20 6f 6c 64 5f 72 | 6f 6f 74 3b 0a 58 0a 58 | = old_r|oot;.X.X|
|000027b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000027c0| 2f 2a 20 75 70 64 61 74 | 65 20 62 61 6c 61 6e 63 |/* updat|e balanc|
|000027d0| 65 73 20 2a 2f 0a 58 20 | 20 20 20 20 20 20 20 20 |es */.X | |
|000027e0| 20 6f 6c 64 5f 72 6f 6f | 74 2d 3e 62 61 6c 20 2b | old_roo|t->bal +|
|000027f0| 3d 20 20 28 20 31 20 2d | 20 4d 49 4e 28 74 72 65 |= ( 1 -| MIN(tre|
|00002800| 65 2d 3e 62 61 6c 2c 20 | 30 29 20 29 3b 0a 58 20 |e->bal, |0) );.X |
|00002810| 20 20 20 20 20 20 20 20 | 20 74 72 65 65 2d 3e 62 | | tree->b|
|00002820| 61 6c 20 20 20 20 20 2b | 3d 20 20 28 20 31 20 2b |al +|= ( 1 +|
|00002830| 20 4d 41 58 28 6f 6c 64 | 5f 72 6f 6f 74 2d 3e 62 | MAX(old|_root->b|
|00002840| 61 6c 2c 20 30 29 20 29 | 3b 0a 58 20 20 20 20 20 |al, 0) )|;.X |
|00002850| 20 20 20 7d 2f 2a 20 72 | 6f 74 61 74 65 5f 72 69 | }/* r|otate_ri|
|00002860| 67 68 74 20 2a 2f 0a 58 | 0c 0a 58 57 65 20 63 61 |ght */.X|..XWe ca|
|00002870| 6e 20 6d 61 6b 65 20 74 | 68 69 73 20 63 6f 64 65 |n make t|his code|
|00002880| 20 6d 6f 72 65 20 63 6f | 6d 70 61 63 74 20 68 6f | more co|mpact ho|
|00002890| 77 65 76 65 72 20 62 79 | 20 75 73 69 6e 67 20 6f |wever by| using o|
|000028a0| 6e 6c 79 20 4f 4e 45 0a | 58 72 6f 74 61 74 65 20 |nly ONE.|Xrotate |
|000028b0| 72 6f 75 74 69 6e 65 20 | 77 68 69 63 68 20 74 61 |routine |which ta|
|000028c0| 6b 65 73 20 61 6e 20 61 | 64 64 69 74 69 6f 6e 61 |kes an a|dditiona|
|000028d0| 6c 20 70 61 72 61 6d 65 | 74 65 72 3a 20 74 68 65 |l parame|ter: the|
|000028e0| 20 64 69 72 65 63 74 69 | 6f 6e 0a 58 69 6e 20 77 | directi|on.Xin w|
|000028f0| 68 69 63 68 20 74 6f 20 | 72 6f 74 61 74 65 2e 20 |hich to |rotate. |
|00002900| 4e 6f 74 69 63 65 20 74 | 68 61 74 20 49 20 68 61 |Notice t|hat I ha|
|00002910| 76 65 20 64 65 66 69 6e | 65 64 20 4c 45 46 54 2c |ve defin|ed LEFT,|
|00002920| 20 61 6e 64 20 52 49 47 | 48 54 20 74 6f 0a 58 62 | and RIG|HT to.Xb|
|00002930| 65 20 6d 6e 65 6d 6f 6e | 69 63 20 63 6f 6e 73 74 |e mnemon|ic const|
|00002940| 61 6e 74 73 20 74 6f 20 | 69 6e 64 65 78 20 69 6e |ants to |index in|
|00002950| 74 6f 20 61 6e 20 61 72 | 72 61 79 20 6f 66 20 73 |to an ar|ray of s|
|00002960| 75 62 74 72 65 65 73 2e | 20 49 20 63 61 6e 0a 58 |ubtrees.| I can.X|
|00002970| 70 61 73 73 20 74 68 65 | 20 63 6f 6e 73 74 61 6e |pass the| constan|
|00002980| 74 20 4c 45 46 54 20 6f | 72 20 52 49 47 48 54 20 |t LEFT o|r RIGHT |
|00002990| 74 6f 20 74 68 65 20 72 | 6f 74 61 74 69 6f 6e 20 |to the r|otation |
|000029a0| 72 6f 75 74 69 6e 65 20 | 61 6e 64 20 69 74 20 63 |routine |and it c|
|000029b0| 61 6e 0a 58 63 61 6c 63 | 75 6c 61 74 65 20 74 68 |an.Xcalc|ulate th|
|000029c0| 65 20 64 69 72 65 63 74 | 69 6f 6e 20 6f 70 70 6f |e direct|ion oppo|
|000029d0| 73 69 74 65 20 74 68 65 | 20 67 69 76 65 6e 20 64 |site the| given d|
|000029e0| 69 72 65 63 74 69 6f 6e | 20 62 79 20 73 75 62 74 |irection| by subt|
|000029f0| 72 61 63 74 69 6e 67 0a | 58 74 68 65 20 67 69 76 |racting.|Xthe giv|
|00002a00| 65 6e 20 64 69 72 65 63 | 74 69 6f 6e 20 66 72 6f |en direc|tion fro|
|00002a10| 6d 20 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 6e 65 |m the nu|mber one|
|00002a20| 2e 0a 58 0a 58 49 74 20 | 64 6f 65 73 20 6e 6f 74 |..X.XIt |does not|
|00002a30| 20 6d 61 74 74 65 72 20 | 77 68 65 74 68 65 72 20 | matter |whether |
|00002a40| 4c 45 46 54 20 69 73 20 | 30 20 6f 72 20 52 49 47 |LEFT is |0 or RIG|
|00002a50| 48 54 20 69 73 20 30 20 | 61 73 20 6c 6f 6e 67 20 |HT is 0 |as long |
|00002a60| 61 73 20 6f 6e 65 0a 58 | 6f 66 20 74 68 65 6d 20 |as one.X|of them |
|00002a70| 69 73 20 30 20 61 6e 64 | 20 74 68 65 20 6f 74 68 |is 0 and| the oth|
|00002a80| 65 72 20 69 73 20 31 2e | 20 20 49 66 20 74 68 69 |er is 1.| If thi|
|00002a90| 73 20 69 73 20 74 68 65 | 20 63 61 73 65 2c 20 74 |s is the| case, t|
|00002aa0| 68 65 6e 3a 0a 58 0a 58 | 20 20 20 20 20 31 20 2d |hen:.X.X| 1 -|
|00002ab0| 20 4c 45 46 54 20 20 3d | 20 52 49 47 48 54 0a 58 | LEFT =| RIGHT.X|
|00002ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002ad0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002ae0| 20 20 20 61 6e 64 0a 58 | 20 20 20 20 20 31 20 2d | and.X| 1 -|
|00002af0| 20 52 49 47 48 54 20 3d | 20 4c 45 46 54 0a 58 0a | RIGHT =| LEFT.X.|
|00002b00| 58 55 73 69 6e 67 20 74 | 68 69 73 20 61 6e 64 20 |XUsing t|his and |
|00002b10| 74 68 65 20 73 61 6d 65 | 20 74 79 70 65 20 64 65 |the same| type de|
|00002b20| 66 69 6e 69 74 69 6f 6e | 73 20 61 73 20 62 65 66 |finition|s as bef|
|00002b30| 6f 72 65 20 28 61 6e 64 | 20 74 68 65 20 73 61 6d |ore (and| the sam|
|00002b40| 65 0a 58 6d 61 63 72 6f | 73 29 2c 20 74 68 65 20 |e.Xmacro|s), the |
|00002b50| 43 20 73 6f 75 72 63 65 | 20 66 6f 72 20 61 20 73 |C source| for a s|
|00002b60| 69 6e 67 6c 65 20 72 6f | 74 61 74 69 6f 6e 20 62 |ingle ro|tation b|
|00002b70| 65 63 6f 6d 65 73 3a 0a | 58 0a 58 20 20 20 20 20 |ecomes:.|X.X |
|00002b80| 20 20 20 23 64 65 66 69 | 6e 65 20 20 4f 54 48 45 | #defi|ne OTHE|
|00002b90| 52 5f 44 49 52 28 78 29 | 20 20 20 28 20 31 20 2d |R_DIR(x)| ( 1 -|
|00002ba0| 20 28 78 29 20 29 0a 58 | 0a 58 20 20 20 20 20 20 | (x) ).X|.X |
|00002bb0| 20 20 74 79 70 65 64 65 | 66 20 20 73 68 6f 72 74 | typede|f short|
|00002bc0| 20 20 44 49 52 45 43 54 | 49 4f 4e 0a 58 0a 58 20 | DIRECT|ION.X.X |
|00002bd0| 20 20 20 20 20 20 20 76 | 6f 69 64 20 20 72 6f 74 | v|oid rot|
|00002be0| 61 74 65 20 28 74 72 65 | 65 2c 20 64 69 72 29 0a |ate (tre|e, dir).|
|00002bf0| 58 20 20 20 20 20 20 20 | 20 20 20 41 56 4c 5f 54 |X | AVL_T|
|00002c00| 52 45 45 20 20 20 20 74 | 72 65 65 3b 0a 58 20 20 |REE t|ree;.X |
|00002c10| 20 20 20 20 20 20 20 20 | 44 49 52 45 43 54 49 4f | |DIRECTIO|
|00002c20| 4e 20 20 20 64 69 72 3b | 0a 58 20 20 20 20 20 20 |N dir;|.X |
|00002c30| 20 20 7b 0a 58 20 20 20 | 20 20 20 20 20 20 20 41 | {.X | A|
|00002c40| 56 4c 5f 54 52 45 45 20 | 20 20 20 6f 6c 64 5f 72 |VL_TREE | old_r|
|00002c50| 6f 6f 74 20 20 3d 20 74 | 72 65 65 3b 0a 58 20 20 |oot = t|ree;.X |
|00002c60| 20 20 20 20 20 20 20 20 | 44 49 52 45 43 54 49 4f | |DIRECTIO|
|00002c70| 4e 20 20 20 6f 74 68 65 | 72 5f 64 69 72 20 3d 20 |N othe|r_dir = |
|00002c80| 4f 54 48 45 52 5f 44 49 | 52 28 64 69 72 29 3b 0a |OTHER_DI|R(dir);.|
|00002c90| 58 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X.X | |
|00002ca0| 20 20 20 2f 2a 20 72 6f | 74 61 74 65 20 2a 2f 0a | /* ro|tate */.|
|00002cb0| 58 20 20 20 20 20 20 20 | 20 20 20 74 72 65 65 20 |X | tree |
|00002cc0| 3d 20 74 72 65 65 2d 3e | 73 75 62 74 72 65 65 5b |= tree->|subtree[|
|00002cd0| 6f 74 68 65 72 5f 64 69 | 72 5d 3b 0a 58 20 20 20 |other_di|r];.X |
|00002ce0| 20 20 20 20 20 20 20 6f | 6c 64 5f 72 6f 6f 74 2d | o|ld_root-|
|00002cf0| 3e 73 75 62 74 72 65 65 | 5b 6f 74 68 65 72 5f 64 |>subtree|[other_d|
|00002d00| 69 72 5d 20 3d 20 74 72 | 65 65 2d 3e 73 75 62 74 |ir] = tr|ee->subt|
|00002d10| 72 65 65 5b 64 69 72 5d | 3b 0a 58 20 20 20 20 20 |ree[dir]|;.X |
|00002d20| 20 20 20 20 20 74 72 65 | 65 2d 3e 73 75 62 74 72 | tre|e->subtr|
|00002d30| 65 65 5b 64 69 72 5d 20 | 3d 20 6f 6c 64 5f 72 6f |ee[dir] |= old_ro|
|00002d40| 6f 74 3b 0a 58 0a 58 20 | 20 20 20 20 20 20 20 20 |ot;.X.X | |
|00002d50| 20 20 20 20 20 20 20 2f | 2a 20 75 70 64 61 74 65 | /|* update|
|00002d60| 20 62 61 6c 61 6e 63 65 | 73 20 2a 2f 0a 58 20 20 | balance|s */.X |
|00002d70| 20 20 20 20 20 20 20 20 | 69 66 20 28 20 64 69 72 | |if ( dir|
|00002d80| 20 3d 3d 20 4c 45 46 54 | 20 29 20 20 7b 0a 58 20 | == LEFT| ) {.X |
|00002d90| 20 20 20 20 20 20 20 20 | 20 20 20 20 6f 6c 64 5f | | old_|
|00002da0| 72 6f 6f 74 2d 3e 62 61 | 6c 20 2d 3d 20 20 28 20 |root->ba|l -= ( |
|00002db0| 31 20 2b 20 4d 41 58 28 | 74 72 65 65 2d 3e 62 61 |1 + MAX(|tree->ba|
|00002dc0| 6c 2c 20 30 29 20 29 3b | 0a 58 20 20 20 20 20 20 |l, 0) );|.X |
|00002dd0| 20 20 20 20 20 20 20 74 | 72 65 65 2d 3e 62 61 6c | t|ree->bal|
|00002de0| 20 20 20 20 20 2d 3d 20 | 20 28 20 31 20 2d 20 4d | -= | ( 1 - M|
|00002df0| 49 4e 28 6f 6c 64 5f 72 | 6f 6f 74 2d 3e 62 61 6c |IN(old_r|oot->bal|
|00002e00| 2c 20 30 29 20 29 3b 0a | 58 20 20 20 20 20 20 20 |, 0) );.|X |
|00002e10| 20 20 20 20 7d 2f 2a 20 | 69 66 20 2a 2f 0a 58 0a | }/* |if */.X.|
|00002e20| 58 20 20 20 20 20 20 20 | 20 20 20 65 6c 73 65 20 |X | else |
|00002e30| 20 2f 2a 20 64 69 72 20 | 3d 3d 20 52 49 47 48 54 | /* dir |== RIGHT|
|00002e40| 20 2a 2f 20 20 7b 0a 58 | 20 20 20 20 20 20 20 20 | */ {.X| |
|00002e50| 20 20 20 20 20 6f 6c 64 | 5f 72 6f 6f 74 2d 3e 62 | old|_root->b|
|00002e60| 61 6c 20 2b 3d 20 20 28 | 20 31 20 2d 20 4d 49 4e |al += (| 1 - MIN|
|00002e70| 28 74 72 65 65 2d 3e 62 | 61 6c 2c 20 30 29 20 29 |(tree->b|al, 0) )|
|00002e80| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;.X | |
|00002e90| 74 72 65 65 2d 3e 62 61 | 6c 20 20 20 20 20 2b 3d |tree->ba|l +=|
|00002ea0| 20 20 28 20 31 20 2b 20 | 4d 41 58 28 6f 6c 64 5f | ( 1 + |MAX(old_|
|00002eb0| 72 6f 6f 74 2d 3e 62 61 | 6c 2c 20 30 29 20 29 3b |root->ba|l, 0) );|
|00002ec0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 7d 2f 2a |.X | }/*|
|00002ed0| 20 65 6c 73 65 20 2a 2f | 0a 58 0a 58 20 20 20 20 | else */|.X.X |
|00002ee0| 20 20 20 20 7d 2f 2a 20 | 72 6f 74 61 74 65 20 2a | }/* |rotate *|
|00002ef0| 2f 0a 58 0c 0a 58 57 65 | 20 63 61 6e 20 63 6f 6d |/.X..XWe| can com|
|00002f00| 70 61 63 74 20 74 68 69 | 73 20 63 6f 64 65 20 65 |pact thi|s code e|
|00002f10| 76 65 6e 20 66 75 72 74 | 68 65 72 20 69 66 20 77 |ven furt|her if w|
|00002f20| 65 20 70 6c 61 79 20 61 | 72 6f 75 6e 64 20 77 69 |e play a|round wi|
|00002f30| 74 68 20 74 68 65 0a 58 | 65 71 75 61 74 69 6f 6e |th the.X|equation|
|00002f40| 73 20 66 6f 72 20 75 70 | 64 61 74 69 6e 67 20 74 |s for up|dating t|
|00002f50| 68 65 20 62 61 6c 61 6e | 63 65 73 2e 20 4c 65 74 |he balan|ces. Let|
|00002f60| 20 75 73 20 75 73 65 20 | 74 68 65 20 66 61 63 74 | us use |the fact|
|00002f70| 20 74 68 61 74 0a 58 6d | 61 78 28 78 2c 79 29 20 | that.Xm|ax(x,y) |
|00002f80| 3d 20 2d 6d 69 6e 28 2d | 78 2c 2d 79 29 3a 0a 58 |= -min(-|x,-y):.X|
|00002f90| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X | |
|00002fa0| 20 20 20 20 20 20 20 20 | 66 6f 72 20 61 20 6c 65 | |for a le|
|00002fb0| 66 74 20 72 6f 74 61 74 | 69 6f 6e 0a 58 20 20 20 |ft rotat|ion.X |
|00002fc0| 20 20 20 20 20 20 20 20 | 20 20 2d 2d 2d 2d 2d 2d | | ------|
|00002fd0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002fe0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002ff0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0a 58 20 20 20 20 |--------|--.X |
|00003000| 20 20 20 20 20 20 20 20 | 20 6f 6c 64 5f 72 6f 6f | | old_roo|
|00003010| 74 2d 3e 62 61 6c 20 2d | 3d 20 20 28 20 31 20 2b |t->bal -|= ( 1 +|
|00003020| 20 4d 41 58 28 74 72 65 | 65 2d 3e 62 61 6c 2c 20 | MAX(tre|e->bal, |
|00003030| 30 29 20 29 3b 0a 58 20 | 20 20 20 20 20 20 20 20 |0) );.X | |
|00003040| 20 20 20 20 74 72 65 65 | 2d 3e 62 61 6c 20 20 20 | tree|->bal |
|00003050| 20 20 2d 3d 20 20 28 20 | 31 20 2d 20 4d 49 4e 28 | -= ( |1 - MIN(|
|00003060| 6f 6c 64 5f 72 6f 6f 74 | 2d 3e 62 61 6c 2c 20 30 |old_root|->bal, 0|
|00003070| 29 20 29 3b 0a 58 0a 58 | 0a 58 20 20 20 20 20 20 |) );.X.X|.X |
|00003080| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003090| 66 6f 72 20 61 20 72 69 | 67 68 74 20 72 6f 74 61 |for a ri|ght rota|
|000030a0| 74 69 6f 6e 0a 58 20 20 | 20 20 20 20 20 20 20 20 |tion.X | |
|000030b0| 20 20 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | -----|--------|
|000030c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000030d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000030e0| 2d 2d 2d 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |---.X | |
|000030f0| 20 20 6f 6c 64 5f 72 6f | 6f 74 2d 3e 62 61 6c 20 | old_ro|ot->bal |
|00003100| 2b 3d 20 20 28 20 31 20 | 2d 20 4d 49 4e 28 74 72 |+= ( 1 |- MIN(tr|
|00003110| 65 65 2d 3e 62 61 6c 2c | 20 30 29 20 29 3b 0a 58 |ee->bal,| 0) );.X|
|00003120| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 74 72 65 | | tre|
|00003130| 65 2d 3e 62 61 6c 20 20 | 20 20 20 2b 3d 20 20 28 |e->bal | += (|
|00003140| 20 31 20 2b 20 4d 41 58 | 28 6f 6c 64 5f 72 6f 6f | 1 + MAX|(old_roo|
|00003150| 74 2d 3e 62 61 6c 2c 20 | 30 29 20 29 3b 0a 58 0a |t->bal, |0) );.X.|
|00003160| 58 55 73 69 6e 67 20 74 | 68 65 20 61 62 6f 76 65 |XUsing t|he above|
|00003170| 20 72 75 6c 65 20 74 6f | 20 63 68 61 6e 67 65 20 | rule to| change |
|00003180| 61 6c 6c 20 6f 63 63 75 | 72 72 65 6e 63 65 73 20 |all occu|rrences |
|00003190| 6f 66 20 22 4d 49 4e 22 | 20 74 6f 20 22 4d 41 58 |of "MIN"| to "MAX|
|000031a0| 22 0a 58 74 68 65 73 65 | 20 65 71 75 61 74 69 6f |".Xthese| equatio|
|000031b0| 6e 73 20 62 65 63 6f 6d | 65 3a 0a 58 0a 58 20 20 |ns becom|e:.X.X |
|000031c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000031d0| 20 20 20 20 66 6f 72 20 | 61 20 6c 65 66 74 20 72 | for |a left r|
|000031e0| 6f 74 61 74 69 6f 6e 0a | 58 20 20 20 20 20 20 20 |otation.|X |
|000031f0| 20 20 20 20 20 20 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | --|--------|
|00003200| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003210| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003220| 2d 2d 2d 2d 2d 2d 0a 58 | 20 20 20 20 20 20 20 20 |------.X| |
|00003230| 20 20 20 20 20 6f 6c 64 | 5f 72 6f 6f 74 2d 3e 62 | old|_root->b|
|00003240| 61 6c 20 2d 3d 20 20 28 | 20 31 20 2b 20 4d 41 58 |al -= (| 1 + MAX|
|00003250| 28 20 2b 28 74 72 65 65 | 2d 3e 62 61 6c 29 2c 20 |( +(tree|->bal), |
|00003260| 30 29 20 29 3b 0a 58 20 | 20 20 20 20 20 20 20 20 |0) );.X | |
|00003270| 20 20 20 20 74 72 65 65 | 2d 3e 62 61 6c 20 20 20 | tree|->bal |
|00003280| 20 20 2d 3d 20 20 28 20 | 31 20 2b 20 4d 41 58 28 | -= ( |1 + MAX(|
|00003290| 20 2d 28 6f 6c 64 5f 72 | 6f 6f 74 2d 3e 62 61 6c | -(old_r|oot->bal|
|000032a0| 29 2c 20 30 29 20 29 3b | 0a 58 0a 58 0a 58 20 20 |), 0) );|.X.X.X |
|000032b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000032c0| 20 20 20 20 66 6f 72 20 | 61 20 72 69 67 68 74 20 | for |a right |
|000032d0| 72 6f 74 61 74 69 6f 6e | 0a 58 20 20 20 20 20 20 |rotation|.X |
|000032e0| 20 20 20 20 20 20 20 2d | 2d 2d 2d 2d 2d 2d 2d 2d | -|--------|
|000032f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003300| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003310| 2d 2d 2d 2d 2d 2d 2d 0a | 58 20 20 20 20 20 20 20 |-------.|X |
|00003320| 20 20 20 20 20 20 6f 6c | 64 5f 72 6f 6f 74 2d 3e | ol|d_root->|
|00003330| 62 61 6c 20 2b 3d 20 20 | 28 20 31 20 2b 20 4d 41 |bal += |( 1 + MA|
|00003340| 58 28 20 2d 28 74 72 65 | 65 2d 3e 62 61 6c 29 2c |X( -(tre|e->bal),|
|00003350| 20 30 29 20 29 3b 0a 58 | 20 20 20 20 20 20 20 20 | 0) );.X| |
|00003360| 20 20 20 20 20 74 72 65 | 65 2d 3e 62 61 6c 20 20 | tre|e->bal |
|00003370| 20 20 20 2b 3d 20 20 28 | 20 31 20 2b 20 4d 41 58 | += (| 1 + MAX|
|00003380| 28 20 2b 28 6f 6c 64 5f | 72 6f 6f 74 2d 3e 62 61 |( +(old_|root->ba|
|00003390| 6c 29 2c 20 30 29 20 29 | 3b 0a 58 0a 58 0a 58 4e |l), 0) )|;.X.X.XN|
|000033a0| 6f 74 65 20 74 68 61 74 | 20 74 68 65 20 64 69 66 |ote that| the dif|
|000033b0| 66 65 72 65 6e 63 65 20 | 62 65 74 77 65 65 6e 20 |ference |between |
|000033c0| 75 70 64 61 74 69 6e 67 | 20 74 68 65 20 62 61 6c |updating| the bal|
|000033d0| 61 6e 63 65 73 20 66 6f | 72 20 6f 75 72 20 72 69 |ances fo|r our ri|
|000033e0| 67 68 74 0a 58 61 6e 64 | 20 6c 65 66 74 20 72 6f |ght.Xand| left ro|
|000033f0| 74 61 74 69 6f 6e 73 20 | 69 73 20 6f 6e 6c 79 20 |tations |is only |
|00003400| 74 68 65 20 6f 63 63 75 | 72 72 65 6e 63 65 20 6f |the occu|rrence o|
|00003410| 66 20 61 20 27 2b 27 20 | 77 68 65 72 65 20 77 65 |f a '+' |where we|
|00003420| 20 77 6f 75 6c 64 20 0a | 58 6c 69 6b 65 20 74 6f | would .|Xlike to|
|00003430| 20 73 65 65 20 61 20 27 | 2d 27 20 69 6e 20 74 68 | see a '|-' in th|
|00003440| 65 20 61 73 73 69 67 6e | 6d 65 6e 74 20 6f 70 65 |e assign|ment ope|
|00003450| 72 61 74 6f 72 2c 20 61 | 6e 64 20 74 68 65 20 73 |rator, a|nd the s|
|00003460| 69 67 6e 20 6f 66 20 74 | 68 65 20 0a 58 66 69 72 |ign of t|he .Xfir|
|00003470| 73 74 20 61 72 67 75 6d | 65 6e 74 20 74 6f 20 74 |st argum|ent to t|
|00003480| 68 65 20 4d 41 58 20 6d | 61 63 72 6f 2e 20 49 66 |he MAX m|acro. If|
|00003490| 20 77 65 20 68 61 64 20 | 61 20 66 75 6e 63 74 69 | we had |a functi|
|000034a0| 6f 6e 20 74 68 61 74 20 | 77 6f 75 6c 64 0a 58 6d |on that |would.Xm|
|000034b0| 61 70 20 4c 45 46 54 20 | 74 6f 20 2b 31 20 61 6e |ap LEFT |to +1 an|
|000034c0| 64 20 52 49 47 48 54 20 | 74 6f 20 2d 31 20 77 65 |d RIGHT |to -1 we|
|000034d0| 20 63 6f 75 6c 64 20 6d | 75 6c 74 69 70 6c 79 20 | could m|ultiply |
|000034e0| 62 79 20 74 68 65 20 72 | 65 73 75 6c 74 0a 58 6f |by the r|esult.Xo|
|000034f0| 66 20 74 68 61 74 20 66 | 75 6e 63 74 69 6f 6e 20 |f that f|unction |
|00003500| 74 6f 20 75 70 64 61 74 | 65 20 6f 75 72 20 62 61 |to updat|e our ba|
|00003510| 6c 61 6e 63 65 73 2e 20 | 53 75 63 68 20 61 20 66 |lances. |Such a f|
|00003520| 75 6e 63 74 69 6f 6e 20 | 69 73 0a 58 0a 58 20 20 |unction |is.X.X |
|00003530| 20 20 20 20 20 20 66 28 | 78 29 20 3d 20 31 20 2d | f(|x) = 1 -|
|00003540| 20 32 78 0a 58 0a 58 22 | 66 22 20 6d 61 70 73 20 | 2x.X.X"|f" maps |
|00003550| 30 20 74 6f 20 31 20 61 | 6e 64 20 6d 61 70 73 20 |0 to 1 a|nd maps |
|00003560| 20 31 20 74 6f 20 2d 31 | 2e 20 54 68 69 73 20 66 | 1 to -1|. This f|
|00003570| 75 6e 63 74 69 6f 6e 20 | 77 69 6c 6c 20 4e 4f 54 |unction |will NOT|
|00003580| 20 6d 61 70 20 4c 45 46 | 54 0a 58 61 6e 64 20 52 | map LEF|T.Xand R|
|00003590| 49 47 48 54 20 74 6f 20 | 74 68 65 20 73 61 6d 65 |IGHT to |the same|
|000035a0| 20 76 61 6c 75 65 20 72 | 65 67 61 72 64 6c 65 73 | value r|egardles|
|000035b0| 73 20 6f 66 20 77 68 69 | 63 68 20 69 73 20 31 20 |s of whi|ch is 1 |
|000035c0| 61 6e 64 20 77 68 69 63 | 68 20 69 73 0a 58 30 20 |and whic|h is.X0 |
|000035d0| 68 6f 77 65 76 65 72 2e | 20 49 66 20 77 65 20 77 |however.| If we w|
|000035e0| 69 73 68 20 6f 75 72 20 | 66 75 6e 63 74 69 6f 6e |ish our |function|
|000035f0| 20 74 6f 20 68 61 76 65 | 20 74 68 69 73 20 70 72 | to have| this pr|
|00003600| 6f 70 65 72 74 79 20 74 | 68 65 6e 20 77 65 0a 58 |operty t|hen we.X|
|00003610| 63 61 6e 20 6d 75 6c 74 | 69 70 6c 79 20 28 31 20 |can mult|iply (1 |
|00003620| 2d 20 32 78 29 20 62 79 | 20 28 52 49 47 48 54 20 |- 2x) by| (RIGHT |
|00003630| 2d 20 4c 45 46 54 29 20 | 73 6f 20 74 68 61 74 20 |- LEFT) |so that |
|00003640| 74 68 65 20 72 65 73 75 | 6c 74 20 22 73 77 69 74 |the resu|lt "swit|
|00003650| 63 68 65 73 22 0a 58 73 | 69 67 6e 73 20 61 63 63 |ches".Xs|igns acc|
|00003660| 6f 72 64 69 6e 67 6c 79 | 20 64 65 70 65 6e 64 69 |ordingly| dependi|
|00003670| 6e 67 20 75 70 6f 6e 20 | 77 68 65 74 68 65 72 20 |ng upon |whether |
|00003680| 4c 45 46 54 20 69 73 20 | 30 20 6f 72 20 52 49 47 |LEFT is |0 or RIG|
|00003690| 48 54 20 69 73 20 30 2e | 0a 58 54 68 69 73 20 64 |HT is 0.|.XThis d|
|000036a0| 65 66 69 6e 65 73 20 61 | 20 6e 65 77 20 66 75 6e |efines a| new fun|
|000036b0| 63 74 69 6f 6e 20 22 67 | 22 3a 0a 58 0a 58 20 20 |ction "g|":.X.X |
|000036c0| 20 20 20 20 20 20 67 28 | 78 29 20 3d 20 28 31 20 | g(|x) = (1 |
|000036d0| 2d 20 32 78 29 28 52 49 | 47 48 54 20 2d 20 4c 45 |- 2x)(RI|GHT - LE|
|000036e0| 46 54 29 0a 58 0a 58 49 | 66 20 4c 45 46 54 20 3d |FT).X.XI|f LEFT =|
|000036f0| 20 30 20 61 6e 64 20 52 | 49 47 48 54 20 3d 20 31 | 0 and R|IGHT = 1|
|00003700| 20 74 68 65 6e 3a 0a 58 | 0a 58 20 20 20 20 20 20 | then:.X|.X |
|00003710| 20 20 67 28 4c 45 46 54 | 29 20 20 3d 20 28 31 20 | g(LEFT|) = (1 |
|00003720| 2d 20 32 2a 30 29 28 31 | 20 2d 20 30 29 20 3d 20 |- 2*0)(1| - 0) = |
|00003730| 20 31 2a 31 20 20 20 20 | 3d 20 31 0a 58 20 20 20 | 1*1 |= 1.X |
|00003740| 20 20 20 20 20 67 28 52 | 49 47 48 54 29 20 3d 20 | g(R|IGHT) = |
|00003750| 28 31 20 2d 20 32 2a 31 | 29 28 31 20 2d 20 30 29 |(1 - 2*1|)(1 - 0)|
|00003760| 20 3d 20 28 2d 31 29 2a | 31 20 20 3d 20 2d 31 0a | = (-1)*|1 = -1.|
|00003770| 58 0a 58 49 66 20 4c 45 | 46 54 20 3d 20 31 20 61 |X.XIf LE|FT = 1 a|
|00003780| 6e 64 20 52 49 47 48 54 | 20 3d 20 30 20 74 68 65 |nd RIGHT| = 0 the|
|00003790| 6e 3a 0a 58 0a 58 20 20 | 20 20 20 20 20 20 67 28 |n:.X.X | g(|
|000037a0| 4c 45 46 54 29 20 20 3d | 20 28 31 20 2d 20 32 2a |LEFT) =| (1 - 2*|
|000037b0| 31 29 28 30 20 2d 20 31 | 29 20 3d 20 28 2d 31 29 |1)(0 - 1|) = (-1)|
|000037c0| 2a 28 2d 31 29 20 20 3d | 20 31 0a 58 20 20 20 20 |*(-1) =| 1.X |
|000037d0| 20 20 20 20 67 28 52 49 | 47 48 54 29 20 3d 20 28 | g(RI|GHT) = (|
|000037e0| 31 20 2d 20 32 2a 30 29 | 28 30 20 2d 20 31 29 20 |1 - 2*0)|(0 - 1) |
|000037f0| 3d 20 20 31 2a 28 2d 31 | 29 20 20 20 20 3d 20 2d |= 1*(-1|) = -|
|00003800| 31 0a 58 0a 58 53 6f 2c | 20 61 73 20 64 65 73 69 |1.X.XSo,| as desi|
|00003810| 72 65 64 2c 20 74 68 65 | 20 66 75 6e 63 74 69 6f |red, the| functio|
|00003820| 6e 20 22 67 22 20 6d 61 | 70 73 20 4c 45 46 54 20 |n "g" ma|ps LEFT |
|00003830| 74 6f 20 2b 31 20 61 6e | 64 20 52 49 47 48 54 20 |to +1 an|d RIGHT |
|00003840| 74 6f 20 2d 31 0a 58 72 | 65 67 61 72 64 6c 65 73 |to -1.Xr|egardles|
|00003850| 73 20 6f 66 20 77 68 69 | 63 68 20 69 73 20 30 20 |s of whi|ch is 0 |
|00003860| 61 6e 64 20 77 68 69 63 | 68 20 69 73 20 31 2e 0a |and whic|h is 1..|
|00003870| 58 0c 0a 58 4e 6f 77 2c | 20 69 66 20 77 65 20 69 |X..XNow,| if we i|
|00003880| 6e 74 72 6f 64 75 63 65 | 20 61 20 6e 65 77 20 76 |ntroduce| a new v|
|00003890| 61 72 69 61 62 6c 65 20 | 63 61 6c 6c 65 64 20 22 |ariable |called "|
|000038a0| 66 61 63 74 6f 72 22 20 | 61 6e 64 20 61 73 73 69 |factor" |and assi|
|000038b0| 67 6e 0a 58 69 74 20 74 | 68 65 20 76 61 6c 75 65 |gn.Xit t|he value|
|000038c0| 20 22 67 28 64 69 72 29 | 22 2c 20 77 65 20 6d 61 | "g(dir)|", we ma|
|000038d0| 79 20 75 70 64 61 74 65 | 20 74 68 65 20 62 61 6c |y update| the bal|
|000038e0| 61 6e 63 65 73 20 69 6e | 20 6f 75 72 20 72 6f 74 |ances in| our rot|
|000038f0| 61 74 69 6f 6e 0a 58 72 | 6f 75 74 69 6e 65 20 77 |ation.Xr|outine w|
|00003900| 69 74 68 6f 75 74 20 75 | 73 69 6e 67 20 61 20 63 |ithout u|sing a c|
|00003910| 6f 6e 64 69 74 69 6f 6e | 61 6c 20 73 74 61 74 65 |ondition|al state|
|00003920| 6d 65 6e 74 3a 0a 58 0a | 58 20 20 20 20 20 20 20 |ment:.X.|X |
|00003930| 20 20 20 20 20 20 20 20 | 20 20 66 6f 72 20 61 20 | | for a |
|00003940| 72 6f 74 61 74 69 6f 6e | 20 69 6e 20 74 68 65 20 |rotation| in the |
|00003950| 22 64 69 72 22 20 64 69 | 72 65 63 74 69 6f 6e 0a |"dir" di|rection.|
|00003960| 58 20 20 20 20 20 20 20 | 20 2d 2d 2d 2d 2d 2d 2d |X | -------|
|00003970| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003980| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003990| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000039a0| 2d 2d 2d 2d 2d 0a 58 20 | 20 20 20 20 20 20 20 6f |-----.X | o|
|000039b0| 6c 64 5f 72 6f 6f 74 2d | 3e 62 61 6c 20 2d 3d 20 |ld_root-|>bal -= |
|000039c0| 20 66 61 63 74 6f 72 20 | 2a 20 28 20 31 20 2b 20 | factor |* ( 1 + |
|000039d0| 4d 41 58 28 20 66 61 63 | 74 6f 72 20 2a 20 74 72 |MAX( fac|tor * tr|
|000039e0| 65 65 2d 3e 62 61 6c 2c | 20 30 29 20 29 3b 0a 58 |ee->bal,| 0) );.X|
|000039f0| 20 20 20 20 20 20 20 20 | 74 72 65 65 2d 3e 62 61 | |tree->ba|
|00003a00| 6c 20 20 20 20 20 2b 3d | 20 20 66 61 63 74 6f 72 |l +=| factor|
|00003a10| 20 2a 20 28 20 31 20 2b | 20 4d 41 58 28 20 66 61 | * ( 1 +| MAX( fa|
|00003a20| 63 74 6f 72 20 2a 20 6f | 6c 64 5f 72 6f 6f 74 2d |ctor * o|ld_root-|
|00003a30| 3e 62 61 6c 2c 20 30 29 | 20 29 3b 0a 58 0a 58 55 |>bal, 0)| );.X.XU|
|00003a40| 73 69 6e 67 20 74 68 69 | 73 2c 20 74 68 65 20 6e |sing thi|s, the n|
|00003a50| 65 77 20 63 6f 64 65 20 | 66 6f 72 20 6f 75 72 20 |ew code |for our |
|00003a60| 72 6f 74 61 74 69 6f 6e | 20 72 6f 75 74 69 6e 65 |rotation| routine|
|00003a70| 20 62 65 63 6f 6d 65 73 | 3a 0a 58 0a 58 20 20 20 | becomes|:.X.X |
|00003a80| 20 20 20 20 20 23 64 65 | 66 69 6e 65 20 20 4f 54 | #de|fine OT|
|00003a90| 48 45 52 5f 44 49 52 28 | 78 29 20 20 20 28 20 31 |HER_DIR(|x) ( 1|
|00003aa0| 20 2d 20 28 78 29 20 29 | 0a 58 0a 58 20 20 20 20 | - (x) )|.X.X |
|00003ab0| 20 20 20 20 74 79 70 65 | 64 65 66 20 20 73 68 6f | type|def sho|
|00003ac0| 72 74 20 20 44 49 52 45 | 43 54 49 4f 4e 0a 58 0a |rt DIRE|CTION.X.|
|00003ad0| 58 20 20 20 20 20 20 20 | 20 76 6f 69 64 20 20 72 |X | void r|
|00003ae0| 6f 74 61 74 65 20 28 74 | 72 65 65 2c 20 64 69 72 |otate (t|ree, dir|
|00003af0| 29 0a 58 20 20 20 20 20 | 20 20 20 20 20 41 56 4c |).X | AVL|
|00003b00| 5f 54 52 45 45 20 20 20 | 20 74 72 65 65 3b 0a 58 |_TREE | tree;.X|
|00003b10| 20 20 20 20 20 20 20 20 | 20 20 44 49 52 45 43 54 | | DIRECT|
|00003b20| 49 4f 4e 20 20 20 64 69 | 72 3b 0a 58 20 20 20 20 |ION di|r;.X |
|00003b30| 20 20 20 20 7b 0a 58 20 | 20 20 20 20 20 20 20 20 | {.X | |
|00003b40| 20 41 56 4c 5f 54 52 45 | 45 20 20 20 20 6f 6c 64 | AVL_TRE|E old|
|00003b50| 5f 72 6f 6f 74 20 20 3d | 20 74 72 65 65 3b 0a 58 |_root =| tree;.X|
|00003b60| 20 20 20 20 20 20 20 20 | 20 20 44 49 52 45 43 54 | | DIRECT|
|00003b70| 49 4f 4e 20 20 20 6f 74 | 68 65 72 5f 64 69 72 20 |ION ot|her_dir |
|00003b80| 3d 20 4f 54 48 45 52 5f | 44 49 52 28 64 69 72 29 |= OTHER_|DIR(dir)|
|00003b90| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 73 68 6f |;.X | sho|
|00003ba0| 72 74 20 20 20 20 20 20 | 20 66 61 63 74 6f 72 20 |rt | factor |
|00003bb0| 3d 20 28 52 49 47 48 54 | 20 2d 20 4c 45 46 54 29 |= (RIGHT| - LEFT)|
|00003bc0| 20 2a 20 28 31 20 2d 20 | 28 32 20 2a 20 64 69 72 | * (1 - |(2 * dir|
|00003bd0| 29 29 3b 0a 58 0a 58 20 | 20 20 20 20 20 20 20 20 |));.X.X | |
|00003be0| 20 20 20 20 20 20 20 2f | 2a 20 72 6f 74 61 74 65 | /|* rotate|
|00003bf0| 20 2a 2f 0a 58 20 20 20 | 20 20 20 20 20 20 20 74 | */.X | t|
|00003c00| 72 65 65 20 3d 20 74 72 | 65 65 2d 3e 73 75 62 74 |ree = tr|ee->subt|
|00003c10| 72 65 65 5b 6f 74 68 65 | 72 5f 64 69 72 5d 3b 0a |ree[othe|r_dir];.|
|00003c20| 58 20 20 20 20 20 20 20 | 20 20 20 6f 6c 64 5f 72 |X | old_r|
|00003c30| 6f 6f 74 2d 3e 73 75 62 | 74 72 65 65 5b 6f 74 68 |oot->sub|tree[oth|
|00003c40| 65 72 5f 64 69 72 5d 20 | 3d 20 74 72 65 65 2d 3e |er_dir] |= tree->|
|00003c50| 73 75 62 74 72 65 65 5b | 64 69 72 5d 3b 0a 58 20 |subtree[|dir];.X |
|00003c60| 20 20 20 20 20 20 20 20 | 20 74 72 65 65 2d 3e 73 | | tree->s|
|00003c70| 75 62 74 72 65 65 5b 64 | 69 72 5d 20 3d 20 6f 6c |ubtree[d|ir] = ol|
|00003c80| 64 5f 72 6f 6f 74 3b 0a | 58 0a 58 20 20 20 20 20 |d_root;.|X.X |
|00003c90| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 75 70 | | /* up|
|00003ca0| 64 61 74 65 20 62 61 6c | 61 6e 63 65 73 20 2a 2f |date bal|ances */|
|00003cb0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 6f 6c 64 5f |.X | old_|
|00003cc0| 72 6f 6f 74 2d 3e 62 61 | 6c 20 2d 3d 20 20 66 61 |root->ba|l -= fa|
|00003cd0| 63 74 6f 72 20 2a 20 28 | 20 31 20 2b 20 4d 41 58 |ctor * (| 1 + MAX|
|00003ce0| 28 20 66 61 63 74 6f 72 | 20 2a 20 74 72 65 65 2d |( factor| * tree-|
|00003cf0| 3e 62 61 6c 2c 20 30 29 | 20 29 3b 0a 58 20 20 20 |>bal, 0)| );.X |
|00003d00| 20 20 20 20 20 20 20 74 | 72 65 65 2d 3e 62 61 6c | t|ree->bal|
|00003d10| 20 20 20 20 20 2b 3d 20 | 20 66 61 63 74 6f 72 20 | += | factor |
|00003d20| 2a 20 28 20 31 20 2b 20 | 4d 41 58 28 20 66 61 63 |* ( 1 + |MAX( fac|
|00003d30| 74 6f 72 20 2a 20 6f 6c | 64 5f 72 6f 6f 74 2d 3e |tor * ol|d_root->|
|00003d40| 62 61 6c 2c 20 30 29 20 | 29 3b 0a 58 0a 58 20 20 |bal, 0) |);.X.X |
|00003d50| 20 20 20 20 20 20 7d 2f | 2a 20 72 6f 74 61 74 65 | }/|* rotate|
|00003d60| 20 2a 2f 0a 58 0a 58 48 | 6f 77 65 76 65 72 2c 20 | */.X.XH|owever, |
|00003d70| 61 6c 74 68 6f 75 67 68 | 20 74 68 69 73 20 73 65 |although| this se|
|00003d80| 63 6f 6e 64 20 76 65 72 | 73 69 6f 6e 20 6f 66 20 |cond ver|sion of |
|00003d90| 22 72 6f 74 61 74 65 22 | 20 69 73 20 6d 6f 72 65 |"rotate"| is more|
|00003da0| 20 63 6f 6d 70 61 63 74 | 20 61 6e 64 20 0a 58 64 | compact| and .Xd|
|00003db0| 6f 65 73 6e 27 74 20 72 | 65 71 75 69 72 65 20 74 |oesn't r|equire t|
|00003dc0| 68 65 20 75 73 65 20 6f | 66 20 61 20 63 6f 6e 64 |he use o|f a cond|
|00003dd0| 69 74 69 6f 6e 61 6c 20 | 74 65 73 74 20 6f 6e 20 |itional |test on |
|00003de0| 74 68 65 20 76 61 72 69 | 61 62 6c 65 20 22 64 69 |the vari|able "di|
|00003df0| 72 22 2c 0a 58 49 74 20 | 6d 61 79 20 61 63 74 75 |r",.XIt |may actu|
|00003e00| 61 6c 6c 79 20 72 75 6e | 20 73 6c 6f 77 65 72 20 |ally run| slower |
|00003e10| 74 68 61 6e 20 6f 75 72 | 20 66 69 72 73 74 20 76 |than our| first v|
|00003e20| 65 72 73 69 6f 6e 20 6f | 66 20 22 72 6f 74 61 74 |ersion o|f "rotat|
|00003e30| 65 22 20 62 65 63 61 75 | 73 65 0a 58 74 68 65 20 |e" becau|se.Xthe |
|00003e40| 74 69 6d 65 20 72 65 71 | 75 69 72 65 64 20 74 6f |time req|uired to|
|00003e50| 20 6d 61 6b 65 20 74 68 | 65 20 22 74 65 73 74 22 | make th|e "test"|
|00003e60| 20 6d 61 79 20 77 65 6c | 6c 20 62 65 20 6c 65 73 | may wel|l be les|
|00003e70| 73 20 74 68 61 6e 20 74 | 68 65 20 74 69 6d 65 0a |s than t|he time.|
|00003e80| 58 72 65 71 75 69 72 65 | 64 20 74 6f 20 70 65 72 |Xrequire|d to per|
|00003e90| 66 6f 72 6d 20 74 68 65 | 20 61 64 64 69 74 69 6f |form the| additio|
|00003ea0| 6e 61 6c 20 6d 75 6c 74 | 69 70 6c 69 63 61 74 69 |nal mult|iplicati|
|00003eb0| 6f 6e 73 20 61 6e 64 20 | 73 75 62 74 72 61 63 74 |ons and |subtract|
|00003ec0| 69 6f 6e 73 2e 0a 58 0a | 58 4e 6f 77 20 61 20 64 |ions..X.|XNow a d|
|00003ed0| 6f 75 62 6c 65 20 72 6f | 74 61 74 69 6f 6e 20 63 |ouble ro|tation c|
|00003ee0| 61 6e 20 62 65 20 69 6d | 70 6c 65 6d 65 6e 74 65 |an be im|plemente|
|00003ef0| 64 20 61 73 20 61 20 73 | 65 72 69 65 73 20 6f 66 |d as a s|eries of|
|00003f00| 20 73 69 6e 67 6c 65 20 | 72 6f 74 61 74 69 6f 6e | single |rotation|
|00003f10| 73 3a 0a 58 0a 58 2f 2a | 0a 58 2a 20 72 6f 74 61 |s:.X.X/*|.X* rota|
|00003f20| 74 65 5f 74 77 69 63 65 | 28 29 20 20 2d 2d 20 20 |te_twice|() -- |
|00003f30| 72 6f 74 61 74 65 20 61 | 20 67 69 76 65 6e 20 6e |rotate a| given n|
|00003f40| 6f 64 65 20 69 6e 20 74 | 68 65 20 67 69 76 65 6e |ode in t|he given|
|00003f50| 20 64 69 72 65 63 74 69 | 6f 6e 0a 58 2a 20 20 20 | directi|on.X* |
|00003f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f70| 20 20 61 6e 64 20 74 68 | 65 6e 20 69 6e 20 74 68 | and th|en in th|
|00003f80| 65 20 6f 70 70 6f 73 69 | 74 65 20 64 69 72 65 63 |e opposi|te direc|
|00003f90| 74 69 6f 6e 0a 58 2a 20 | 20 20 20 20 20 20 20 20 |tion.X* | |
|00003fa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 74 6f 20 72 | | to r|
|00003fb0| 65 73 74 6f 72 65 20 74 | 68 65 20 62 61 6c 61 6e |estore t|he balan|
|00003fc0| 63 65 20 6f 66 20 61 20 | 74 72 65 65 0a 58 2a 2f |ce of a |tree.X*/|
|00003fd0| 0a 58 76 6f 69 64 20 72 | 6f 74 61 74 65 5f 74 77 |.Xvoid r|otate_tw|
|00003fe0| 69 63 65 28 20 72 6f 6f | 74 70 2c 20 64 69 72 20 |ice( roo|tp, dir |
|00003ff0| 29 0a 58 41 56 4c 74 72 | 65 65 20 20 20 20 2a 72 |).XAVLtr|ee *r|
|00004000| 6f 6f 74 70 3b 0a 58 44 | 49 52 45 43 54 49 4f 4e |ootp;.XD|IRECTION|
|00004010| 20 20 64 69 72 3b 0a 58 | 7b 0a 58 20 20 20 20 44 | dir;.X|{.X D|
|00004020| 49 52 45 43 54 49 4f 4e | 20 20 20 6f 74 68 65 72 |IRECTION| other|
|00004030| 5f 64 69 72 20 3d 20 4f | 50 50 4f 53 49 54 45 28 |_dir = O|PPOSITE(|
|00004040| 20 64 69 72 20 29 3b 0a | 58 20 20 0a 58 20 20 20 | dir );.|X .X |
|00004050| 20 72 6f 74 61 74 65 5f | 6f 6e 63 65 28 20 26 28 | rotate_|once( &(|
|00004060| 20 28 2a 72 6f 6f 74 70 | 29 20 2d 3e 20 73 75 62 | (*rootp|) -> sub|
|00004070| 74 72 65 65 5b 20 6f 74 | 68 65 72 5f 64 69 72 20 |tree[ ot|her_dir |
|00004080| 5d 20 29 2c 20 6f 74 68 | 65 72 5f 64 69 72 20 29 |] ), oth|er_dir )|
|00004090| 3b 20 20 0a 58 20 20 20 | 20 72 6f 74 61 74 65 5f |; .X | rotate_|
|000040a0| 6f 6e 63 65 28 20 72 6f | 6f 74 70 2c 20 64 69 72 |once( ro|otp, dir|
|000040b0| 20 29 3b 0a 58 0a 58 7d | 2f 2a 20 72 6f 74 61 74 | );.X.X}|/* rotat|
|000040c0| 65 5f 74 77 69 63 65 20 | 2a 2f 0a 58 0a 58 0c 0a |e_twice |*/.X.X..|
|000040d0| 58 41 4e 4f 54 48 45 52 | 20 4d 45 54 48 4f 44 20 |XANOTHER| METHOD |
|000040e0| 46 4f 52 20 43 41 4c 43 | 55 4c 41 54 49 4e 47 20 |FOR CALC|ULATING |
|000040f0| 42 41 4c 41 4e 43 45 53 | 20 41 46 54 45 52 20 52 |BALANCES| AFTER R|
|00004100| 4f 54 41 54 49 4f 4e 3a | 0a 58 3d 3d 3d 3d 3d 3d |OTATION:|.X======|
|00004110| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004120| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004130| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004140| 3d 0a 58 4f 6e 65 20 6d | 61 79 20 75 73 65 20 61 |=.XOne m|ay use a|
|00004150| 20 64 69 66 66 65 72 65 | 6e 74 20 6d 65 74 68 6f | differe|nt metho|
|00004160| 64 20 74 68 61 6e 20 74 | 68 65 20 6f 6e 65 20 64 |d than t|he one d|
|00004170| 65 73 63 72 69 62 65 64 | 20 61 62 6f 76 65 20 77 |escribed| above w|
|00004180| 68 69 63 68 0a 58 69 73 | 20 70 65 72 68 61 70 73 |hich.Xis| perhaps|
|00004190| 20 73 69 6d 70 6c 65 72 | 2e 20 4e 6f 74 65 20 68 | simpler|. Note h|
|000041a0| 6f 77 65 76 65 72 20 74 | 68 61 74 20 74 68 65 20 |owever t|hat the |
|000041b0| 6d 65 74 68 6f 64 20 66 | 6f 72 20 75 70 64 61 74 |method f|or updat|
|000041c0| 69 6e 67 20 62 61 6c 61 | 6e 63 65 73 0a 58 64 65 |ing bala|nces.Xde|
|000041d0| 73 63 72 69 62 65 64 20 | 61 62 6f 76 65 20 77 6f |scribed |above wo|
|000041e0| 72 6b 73 20 72 65 67 61 | 72 64 6c 65 73 73 20 6f |rks rega|rdless o|
|000041f0| 66 20 77 68 61 74 20 6e | 75 6d 62 65 72 73 20 74 |f what n|umbers t|
|00004200| 68 65 20 62 61 6c 61 6e | 63 65 20 66 61 63 74 6f |he balan|ce facto|
|00004210| 72 0a 58 6d 61 79 20 63 | 6f 6e 74 61 69 6e 20 28 |r.Xmay c|ontain (|
|00004220| 61 73 20 6c 6f 6e 67 20 | 61 73 20 74 68 65 79 20 |as long |as they |
|00004230| 61 72 65 20 63 6f 72 72 | 65 63 74 20 2d 2d 20 69 |are corr|ect -- i|
|00004240| 74 20 77 6f 72 6b 73 2c | 20 6e 6f 20 6d 61 74 74 |t works,| no matt|
|00004250| 65 72 20 68 6f 77 0a 58 | 69 6d 62 61 6c 61 6e 63 |er how.X|imbalanc|
|00004260| 65 64 29 2e 20 49 66 20 | 77 65 20 74 61 6b 65 20 |ed). If |we take |
|00004270| 69 6e 74 6f 20 61 63 63 | 6f 75 6e 74 20 73 6f 6d |into acc|ount som|
|00004280| 65 20 6f 66 20 63 6f 6e | 64 69 74 69 6f 6e 73 20 |e of con|ditions |
|00004290| 74 68 61 74 20 63 61 75 | 73 65 0a 58 61 20 72 6f |that cau|se.Xa ro|
|000042a0| 74 61 74 69 6f 6e 2c 20 | 77 65 20 68 61 76 65 20 |tation, |we have |
|000042b0| 6d 6f 72 65 20 69 6e 66 | 6f 72 6d 61 74 69 6f 6e |more inf|ormation|
|000042c0| 20 74 6f 20 77 6f 72 6b | 20 77 69 74 68 20 28 73 | to work| with (s|
|000042d0| 75 63 68 20 74 68 61 74 | 20 74 68 65 20 0a 58 6e |uch that| the .Xn|
|000042e0| 6f 64 65 20 74 6f 20 62 | 65 20 72 6f 74 61 74 65 |ode to b|e rotate|
|000042f0| 64 20 68 61 73 20 61 20 | 62 61 6c 61 6e 63 65 20 |d has a |balance |
|00004300| 6f 66 20 2b 32 20 6f 72 | 20 2d 32 20 65 74 63 2e |of +2 or| -2 etc.|
|00004310| 2e 29 0a 58 0a 58 46 6f | 72 20 61 20 73 69 6e 67 |.).X.XFo|r a sing|
|00004320| 6c 65 20 4c 4c 20 72 6f | 74 61 74 69 6f 6e 20 77 |le LL ro|tation w|
|00004330| 65 20 68 61 76 65 20 6f | 6e 65 20 6f 66 20 74 77 |e have o|ne of tw|
|00004340| 6f 20 70 6f 73 73 69 62 | 69 6c 69 74 69 65 73 3a |o possib|ilities:|
|00004350| 0a 58 0a 58 0a 58 20 20 | 20 20 20 20 20 20 20 20 |.X.X.X | |
|00004360| 20 20 20 20 20 20 20 20 | 41 20 20 20 20 20 20 20 | |A |
|00004370| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004380| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 42 0a | | B.|
|00004390| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X | |
|000043a0| 20 20 2f 20 5c 20 20 20 | 20 20 20 20 20 20 20 20 | / \ | |
|000043b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000043c0| 20 20 20 20 20 20 20 20 | 2f 20 5c 0a 58 20 20 20 | |/ \.X |
|000043d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2f 20 20 | | / |
|000043e0| 20 5c 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | \ | |
|000043f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004400| 20 20 20 2f 20 20 20 5c | 0a 58 20 20 20 20 20 20 | / \|.X |
|00004410| 20 20 20 20 20 20 20 20 | 20 61 20 20 20 20 20 42 | | a B|
|00004420| 20 20 20 20 20 20 20 20 | 20 20 20 3d 3d 3e 20 20 | | ==> |
|00004430| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 41 | | A|
|00004440| 20 20 20 20 20 63 0a 58 | 20 20 20 20 20 20 20 20 | c.X| |
|00004450| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 20 5c 20 | | / \ |
|00004460| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004470| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 20 5c 0a | | / \.|
|00004480| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X | |
|00004490| 20 20 20 20 2f 20 20 20 | 5c 20 20 20 20 20 20 20 | / |\ |
|000044a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000044b0| 20 20 20 20 2f 20 20 20 | 5c 0a 58 20 20 20 20 20 | / |\.X |
|000044c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 62 20 20 | | b |
|000044d0| 20 20 20 63 20 20 20 20 | 20 20 20 20 20 20 20 20 | c | |
|000044e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 61 20 20 | | a |
|000044f0| 20 20 20 62 0a 58 0a 58 | 3d 3d 3d 3d 3d 3d 3d 3d | b.X.X|========|
|00004500| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004510| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004520| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004530| 3d 3d 3d 3d 3d 3d 0a 58 | 20 20 20 20 20 20 20 20 |======.X| |
|00004540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004550| 20 20 20 20 20 42 41 4c | 41 4e 43 45 20 46 41 43 | BAL|ANCE FAC|
|00004560| 54 4f 52 53 0a 58 20 20 | 20 20 20 20 20 20 20 20 |TORS.X | |
|00004570| 42 45 46 4f 52 45 20 52 | 4f 54 41 54 49 4f 4e 20 |BEFORE R|OTATION |
|00004580| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004590| 20 20 20 20 20 41 46 54 | 45 52 20 52 4f 54 41 54 | AFT|ER ROTAT|
|000045a0| 49 4f 4e 0a 58 20 20 20 | 20 20 20 20 20 20 2d 2d |ION.X | --|
|000045b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000045c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000045d0| 20 20 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | -----|--------|
|000045e0| 2d 2d 2d 0a 58 63 61 73 | 65 20 31 29 20 20 20 41 |---.Xcas|e 1) A|
|000045f0| 20 3d 20 2b 32 20 3b 20 | 42 20 3d 20 2b 31 20 20 | = +2 ; |B = +1 |
|00004600| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004610| 20 20 20 20 41 20 3d 20 | 30 20 20 3b 20 42 20 3d | A = |0 ; B =|
|00004620| 20 30 20 0a 58 63 61 73 | 65 20 32 29 20 20 20 41 | 0 .Xcas|e 2) A|
|00004630| 20 3d 20 2b 32 20 3b 20 | 42 20 3d 20 30 20 20 20 | = +2 ; |B = 0 |
|00004640| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004650| 20 20 20 20 41 20 3d 20 | 2b 31 20 3b 20 42 20 3d | A = |+1 ; B =|
|00004660| 20 2d 31 0a 58 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d | -1.X===|========|
|00004670| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004680| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004690| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000046a0| 3d 3d 3d 0a 58 0a 58 20 | 73 6f 20 69 6e 20 65 69 |===.X.X |so in ei|
|000046b0| 74 68 65 72 20 63 61 73 | 65 20 20 4e 65 77 42 20 |ther cas|e NewB |
|000046c0| 3d 20 4f 6c 64 42 20 2d | 31 20 61 6e 64 20 6e 65 |= OldB -|1 and ne|
|000046d0| 77 41 20 3d 20 2d 6e 65 | 77 42 20 73 6f 20 77 65 |wA = -ne|wB so we|
|000046e0| 20 67 65 74 0a 58 20 41 | 20 3d 20 2d 20 28 2d 2d | get.X A| = - (--|
|000046f0| 42 29 20 66 6f 72 20 61 | 20 73 69 6e 67 6c 65 20 |B) for a| single |
|00004700| 6c 65 66 74 20 72 6f 74 | 61 74 69 6f 6e 2e 0a 58 |left rot|ation..X|
|00004710| 0a 58 46 6f 72 20 61 20 | 73 69 6e 67 6c 65 20 52 |.XFor a |single R|
|00004720| 52 20 72 6f 74 61 74 69 | 6f 6e 20 74 68 65 20 70 |R rotati|on the p|
|00004730| 6f 73 73 69 62 69 6c 69 | 74 69 65 73 20 61 72 65 |ossibili|ties are|
|00004740| 20 28 54 68 65 20 70 69 | 63 74 75 72 65 20 69 73 | (The pi|cture is|
|00004750| 20 61 0a 58 6d 69 72 72 | 6f 72 20 69 6d 61 67 65 | a.Xmirr|or image|
|00004760| 20 28 73 77 61 70 20 61 | 6c 6c 20 72 69 67 68 74 | (swap a|ll right|
|00004770| 20 61 6e 64 20 6c 65 66 | 74 20 6b 69 64 73 20 6f | and lef|t kids o|
|00004780| 66 20 65 61 63 68 20 6e | 6f 64 65 29 20 6f 66 20 |f each n|ode) of |
|00004790| 74 68 65 20 4c 4c 20 6f | 6e 65 29 0a 58 3d 3d 3d |the LL o|ne).X===|
|000047a0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000047b0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000047c0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000047d0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 0a 58 20 20 20 |========|===.X |
|000047e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000047f0| 20 20 20 20 20 20 20 20 | 20 20 42 41 4c 41 4e 43 | | BALANC|
|00004800| 45 20 46 41 43 54 4f 52 | 53 0a 58 20 20 20 20 20 |E FACTOR|S.X |
|00004810| 20 20 20 20 20 42 45 46 | 4f 52 45 20 52 4f 54 41 | BEF|ORE ROTA|
|00004820| 54 49 4f 4e 20 20 20 20 | 20 20 20 20 20 20 20 20 |TION | |
|00004830| 20 20 20 20 20 20 20 20 | 20 20 41 46 54 45 52 20 | | AFTER |
|00004840| 52 4f 54 41 54 49 4f 4e | 0a 58 20 20 20 20 20 20 |ROTATION|.X |
|00004850| 20 20 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | -----|--------|
|00004860| 2d 2d 2d 2d 2d 20 20 20 | 20 20 20 20 20 20 20 20 |----- | |
|00004870| 20 20 20 20 20 20 20 20 | 2d 2d 2d 2d 2d 2d 2d 2d | |--------|
|00004880| 2d 2d 2d 2d 2d 2d 2d 2d | 0a 58 63 61 73 65 20 31 |--------|.Xcase 1|
|00004890| 29 20 20 20 41 20 3d 20 | 2d 32 20 3b 20 42 20 3d |) A = |-2 ; B =|
|000048a0| 20 2d 31 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | -1 | |
|000048b0| 20 20 20 20 20 20 20 20 | 20 41 20 3d 20 30 20 20 | | A = 0 |
|000048c0| 3b 20 42 20 3d 20 30 20 | 0a 58 63 61 73 65 20 32 |; B = 0 |.Xcase 2|
|000048d0| 29 20 20 20 41 20 3d 20 | 2d 32 20 3b 20 42 20 3d |) A = |-2 ; B =|
|000048e0| 20 30 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | 0 | |
|000048f0| 20 20 20 20 20 20 20 20 | 20 41 20 3d 20 2d 31 20 | | A = -1 |
|00004900| 3b 20 42 20 3d 20 2b 31 | 0a 58 3d 3d 3d 3d 3d 3d |; B = +1|.X======|
|00004910| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004920| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004930| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00004940| 3d 3d 3d 3d 3d 3d 3d 3d | 0a 58 0a 58 20 73 6f 20 |========|.X.X so |
|00004950| 69 6e 20 65 69 74 68 65 | 72 20 63 61 73 65 20 20 |in eithe|r case |
|00004960| 4e 65 77 42 20 3d 20 4f | 6c 64 42 20 2b 31 20 61 |NewB = O|ldB +1 a|
|00004970| 6e 64 20 6e 65 77 41 20 | 3d 20 2d 6e 65 77 42 20 |nd newA |= -newB |
|00004980| 73 6f 20 77 65 20 67 65 | 74 0a 58 20 41 20 3d 20 |so we ge|t.X A = |
|00004990| 2d 20 28 2b 2b 42 29 20 | 66 6f 72 20 61 20 73 69 |- (++B) |for a si|
|000049a0| 6e 67 6c 65 20 6c 65 66 | 74 20 72 6f 74 61 74 69 |ngle lef|t rotati|
|000049b0| 6f 6e 2e 0a 58 0c 0a 58 | 54 68 69 73 20 6d 65 61 |on..X..X|This mea|
|000049c0| 6e 73 20 74 68 61 74 20 | 77 65 20 63 61 6e 20 75 |ns that |we can u|
|000049d0| 73 65 20 74 68 65 20 66 | 6f 6c 6c 6f 77 69 6e 67 |se the f|ollowing|
|000049e0| 20 74 6f 20 75 70 64 61 | 74 65 20 62 61 6c 61 6e | to upda|te balan|
|000049f0| 63 65 73 3a 0a 58 0a 58 | 20 20 20 20 20 20 20 2f |ces:.X.X| /|
|00004a00| 2a 20 44 69 72 65 63 74 | 69 6f 6e 61 6c 20 44 65 |* Direct|ional De|
|00004a10| 66 69 6e 69 74 69 6f 6e | 73 20 2a 2f 0a 58 74 79 |finition|s */.Xty|
|00004a20| 70 65 64 65 66 20 20 73 | 68 6f 72 74 20 20 44 49 |pedef s|hort DI|
|00004a30| 52 45 43 54 49 4f 4e 3b | 0a 58 23 64 65 66 69 6e |RECTION;|.X#defin|
|00004a40| 65 20 20 4c 45 46 54 20 | 20 20 20 20 20 20 20 20 |e LEFT | |
|00004a50| 20 20 20 20 30 0a 58 23 | 64 65 66 69 6e 65 20 20 | 0.X#|define |
|00004a60| 52 49 47 48 54 20 20 20 | 20 20 20 20 20 20 20 20 |RIGHT | |
|00004a70| 20 31 0a 58 23 64 65 66 | 69 6e 65 20 20 4f 50 50 | 1.X#def|ine OPP|
|00004a80| 4f 53 49 54 45 28 78 29 | 20 20 20 20 20 28 20 31 |OSITE(x)| ( 1|
|00004a90| 20 2d 20 28 78 29 20 29 | 0a 58 20 20 0a 58 0a 58 | - (x) )|.X .X.X|
|00004aa0| 20 20 20 20 20 20 20 2f | 2a 20 72 65 74 75 72 6e | /|* return|
|00004ab0| 20 63 6f 64 65 73 20 75 | 73 65 64 20 62 79 20 61 | codes u|sed by a|
|00004ac0| 76 6c 5f 69 6e 73 65 72 | 74 28 29 2c 20 61 76 6c |vl_inser|t(), avl|
|00004ad0| 5f 64 65 6c 65 74 65 28 | 29 2c 20 61 6e 64 20 62 |_delete(|), and b|
|00004ae0| 61 6c 61 6e 63 65 28 29 | 20 2a 2f 0a 58 23 64 65 |alance()| */.X#de|
|00004af0| 66 69 6e 65 20 20 48 45 | 49 47 48 54 5f 55 4e 43 |fine HE|IGHT_UNC|
|00004b00| 48 41 4e 47 45 44 09 30 | 0a 58 23 64 65 66 69 6e |HANGED.0|.X#defin|
|00004b10| 65 20 20 48 45 49 47 48 | 54 5f 43 48 41 4e 47 45 |e HEIGH|T_CHANGE|
|00004b20| 44 09 09 31 0a 58 0a 58 | 0a 58 2f 2a 0a 58 2a 20 |D..1.X.X|.X/*.X* |
|00004b30| 72 6f 74 61 74 65 5f 6f | 6e 63 65 28 29 20 20 2d |rotate_o|nce() -|
|00004b40| 2d 20 20 72 6f 74 61 74 | 65 20 61 20 67 69 76 65 |- rotat|e a give|
|00004b50| 6e 20 6e 6f 64 65 20 69 | 6e 20 74 68 65 20 67 69 |n node i|n the gi|
|00004b60| 76 65 6e 20 64 69 72 65 | 63 74 69 6f 6e 0a 58 2a |ven dire|ction.X*|
|00004b70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004b80| 20 20 20 20 74 6f 20 72 | 65 73 74 6f 72 65 20 74 | to r|estore t|
|00004b90| 68 65 20 62 61 6c 61 6e | 63 65 20 6f 66 20 61 20 |he balan|ce of a |
|00004ba0| 74 72 65 65 0a 58 2a 2f | 0a 58 73 68 6f 72 74 20 |tree.X*/|.Xshort |
|00004bb0| 72 6f 74 61 74 65 5f 6f | 6e 63 65 28 20 72 6f 6f |rotate_o|nce( roo|
|00004bc0| 74 70 2c 20 64 69 72 20 | 29 0a 58 41 56 4c 74 72 |tp, dir |).XAVLtr|
|00004bd0| 65 65 20 20 20 20 2a 72 | 6f 6f 74 70 3b 0a 58 44 |ee *r|ootp;.XD|
|00004be0| 49 52 45 43 54 49 4f 4e | 20 20 64 69 72 3b 0a 58 |IRECTION| dir;.X|
|00004bf0| 7b 0a 58 20 20 20 44 49 | 52 45 43 54 49 4f 4e 20 |{.X DI|RECTION |
|00004c00| 20 20 6f 74 68 65 72 5f | 64 69 72 20 3d 20 4f 50 | other_|dir = OP|
|00004c10| 50 4f 53 49 54 45 28 20 | 64 69 72 20 29 3b 09 2f |POSITE( |dir );./|
|00004c20| 2a 20 6f 70 70 6f 73 69 | 74 65 20 64 69 72 65 63 |* opposi|te direc|
|00004c30| 74 69 6f 6e 20 74 6f 20 | 22 64 69 72 22 20 2a 2f |tion to |"dir" */|
|00004c40| 0a 58 20 20 20 41 56 4c | 74 72 65 65 20 20 20 20 |.X AVL|tree |
|00004c50| 20 6f 6c 64 5f 72 6f 6f | 74 20 20 3d 20 2a 72 6f | old_roo|t = *ro|
|00004c60| 6f 74 70 3b 09 09 2f 2a | 20 63 6f 70 79 20 6f 66 |otp;../*| copy of|
|00004c70| 20 6f 72 69 67 69 6e 61 | 6c 20 72 6f 6f 74 20 6f | origina|l root o|
|00004c80| 66 20 74 72 65 65 20 2a | 2f 0a 58 20 20 20 73 68 |f tree *|/.X sh|
|00004c90| 6f 72 74 09 68 74 5f 75 | 6e 63 68 61 6e 67 65 64 |ort.ht_u|nchanged|
|00004ca0| 3b 09 09 09 2f 2a 20 74 | 72 75 65 20 69 66 20 68 |;.../* t|rue if h|
|00004cb0| 65 69 67 68 74 20 75 6e | 63 68 61 6e 67 65 64 20 |eight un|changed |
|00004cc0| 2a 2f 0a 58 0a 58 20 20 | 20 2f 2a 20 48 65 72 65 |*/.X.X | /* Here|
|00004cd0| 20 77 65 20 6e 65 65 64 | 20 74 6f 20 74 61 6b 65 | we need| to take|
|00004ce0| 20 69 6e 74 6f 20 61 63 | 63 6f 75 6e 74 20 74 68 | into ac|count th|
|00004cf0| 65 20 73 70 65 63 69 61 | 6c 20 63 61 73 65 20 74 |e specia|l case t|
|00004d00| 68 61 74 20 6f 63 63 75 | 72 73 20 77 68 65 6e 20 |hat occu|rs when |
|00004d10| 61 20 0a 58 20 20 20 2a | 2a 20 73 69 6e 67 6c 65 |a .X *|* single|
|00004d20| 20 72 6f 74 61 74 69 6f | 6e 20 77 61 73 20 6d 61 | rotatio|n was ma|
|00004d30| 64 65 20 62 75 74 20 74 | 68 65 20 48 45 49 47 48 |de but t|he HEIGH|
|00004d40| 54 20 6f 66 20 74 68 65 | 20 72 6f 74 61 74 65 64 |T of the| rotated|
|00004d50| 20 74 72 65 65 20 64 69 | 64 20 4e 4f 54 0a 58 20 | tree di|d NOT.X |
|00004d60| 20 20 2a 2a 20 63 68 61 | 6e 67 65 20 61 73 20 61 | ** cha|nge as a|
|00004d70| 20 72 65 73 75 6c 74 20 | 6f 66 20 74 68 65 20 72 | result |of the r|
|00004d80| 6f 74 61 74 69 6f 6e 20 | 28 77 65 20 77 69 6c 6c |otation |(we will|
|00004d90| 20 6e 65 65 64 20 74 68 | 69 73 20 6c 61 74 65 72 | need th|is later|
|00004da0| 29 0a 58 20 20 20 2a 2f | 0a 58 20 20 20 68 74 5f |).X */|.X ht_|
|00004db0| 75 6e 63 68 61 6e 67 65 | 64 20 3d 20 28 20 28 2a |unchange|d = ( (*|
|00004dc0| 72 6f 6f 74 70 29 20 2d | 3e 20 73 75 62 74 72 65 |rootp) -|> subtre|
|00004dd0| 65 5b 20 6f 74 68 65 72 | 5f 64 69 72 20 5d 20 2d |e[ other|_dir ] -|
|00004de0| 3e 20 62 61 6c 20 29 20 | 3f 20 46 41 4c 53 45 20 |> bal ) |? FALSE |
|00004df0| 3a 20 54 52 55 45 3b 0a | 58 20 20 0a 58 20 20 20 |: TRUE;.|X .X |
|00004e00| 20 20 20 20 20 2f 2a 20 | 61 73 73 69 67 6e 20 6e | /* |assign n|
|00004e10| 65 77 20 72 6f 6f 74 20 | 2a 2f 0a 58 20 20 20 20 |ew root |*/.X |
|00004e20| 2a 72 6f 6f 74 70 20 3d | 20 6f 6c 64 5f 72 6f 6f |*rootp =| old_roo|
|00004e30| 74 20 2d 3e 20 73 75 62 | 74 72 65 65 5b 20 6f 74 |t -> sub|tree[ ot|
|00004e40| 68 65 72 5f 64 69 72 20 | 5d 3b 0a 58 20 20 0a 58 |her_dir |];.X .X|
|00004e50| 20 20 20 20 20 20 20 20 | 2f 2a 20 6e 65 77 2d 72 | |/* new-r|
|00004e60| 6f 6f 74 20 65 78 63 68 | 61 6e 67 65 73 20 69 74 |oot exch|anges it|
|00004e70| 27 73 20 22 64 69 72 22 | 20 73 75 62 74 72 65 65 |'s "dir"| subtree|
|00004e80| 20 66 6f 72 20 69 74 27 | 73 20 70 61 72 65 6e 74 | for it'|s parent|
|00004e90| 20 2a 2f 0a 58 20 20 20 | 20 6f 6c 64 5f 72 6f 6f | */.X | old_roo|
|00004ea0| 74 20 2d 3e 20 73 75 62 | 74 72 65 65 5b 20 6f 74 |t -> sub|tree[ ot|
|00004eb0| 68 65 72 5f 64 69 72 20 | 5d 20 20 20 3d 20 20 20 |her_dir |] = |
|00004ec0| 28 2a 72 6f 6f 74 70 29 | 20 2d 3e 20 73 75 62 74 |(*rootp)| -> subt|
|00004ed0| 72 65 65 5b 20 64 69 72 | 20 5d 3b 0a 58 20 20 20 |ree[ dir| ];.X |
|00004ee0| 20 28 2a 72 6f 6f 74 70 | 29 20 2d 3e 20 73 75 62 | (*rootp|) -> sub|
|00004ef0| 74 72 65 65 5b 20 64 69 | 72 20 5d 20 20 20 20 20 |tree[ di|r ] |
|00004f00| 20 20 20 20 3d 20 20 20 | 6f 6c 64 5f 72 6f 6f 74 | = |old_root|
|00004f10| 3b 0a 58 20 20 0a 58 20 | 20 20 20 20 20 20 20 2f |;.X .X | /|
|00004f20| 2a 20 75 70 64 61 74 65 | 20 62 61 6c 61 6e 63 65 |* update| balance|
|00004f30| 73 20 2a 2f 0a 58 20 20 | 20 20 6f 6c 64 5f 72 6f |s */.X | old_ro|
|00004f40| 6f 74 20 2d 3e 20 62 61 | 6c 20 3d 20 2d 28 20 64 |ot -> ba|l = -( d|
|00004f50| 69 72 20 3d 3d 20 4c 45 | 46 54 20 3f 20 2d 2d 28 |ir == LE|FT ? --(|
|00004f60| 20 28 2a 72 6f 6f 74 70 | 29 20 2d 3e 20 62 61 6c | (*rootp|) -> bal|
|00004f70| 20 29 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 | ).X | |
|00004f80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004f90| 20 20 20 20 20 20 20 20 | 20 3a 20 2b 2b 28 20 28 | | : ++( (|
|00004fa0| 2a 72 6f 6f 74 70 29 20 | 2d 3e 20 62 61 6c 20 29 |*rootp) |-> bal )|
|00004fb0| 20 20 29 3b 0a 58 20 20 | 0a 58 20 20 20 20 72 65 | );.X |.X re|
|00004fc0| 74 75 72 6e 20 20 68 74 | 5f 75 6e 63 68 61 6e 67 |turn ht|_unchang|
|00004fd0| 65 64 3b 0a 58 7d 2f 2a | 20 72 6f 74 61 74 65 5f |ed;.X}/*| rotate_|
|00004fe0| 6f 6e 63 65 20 2a 2f 0a | 58 0c 0a 58 57 65 20 67 |once */.|X..XWe g|
|00004ff0| 65 74 20 61 6e 20 65 76 | 65 6e 20 6e 69 63 65 72 |et an ev|en nicer|
|00005000| 20 73 63 65 6e 61 72 69 | 6f 20 77 68 65 6e 20 77 | scenari|o when w|
|00005010| 65 20 6c 6f 6f 6b 20 61 | 74 20 4c 52 20 61 6e 64 |e look a|t LR and|
|00005020| 20 52 4c 20 72 6f 74 61 | 74 69 6f 6e 73 2e 0a 58 | RL rota|tions..X|
|00005030| 46 6f 72 20 61 20 64 6f | 75 62 6c 65 20 4c 52 20 |For a do|uble LR |
|00005040| 72 6f 74 61 74 69 6f 6e | 20 77 65 20 68 61 76 65 |rotation| we have|
|00005050| 20 6f 6e 65 20 6f 66 20 | 74 68 72 65 65 20 70 6f | one of |three po|
|00005060| 73 73 69 62 69 6c 69 74 | 69 65 73 3a 0a 58 0a 58 |ssibilit|ies:.X.X|
|00005070| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.X | |
|00005080| 20 20 20 20 41 20 20 20 | 20 20 20 20 20 20 20 20 | A | |
|00005090| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000050a0| 20 20 20 20 20 20 20 20 | 20 20 42 0a 58 20 20 20 | | B.X |
|000050b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 20 | | / |
|000050c0| 5c 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |\ | |
|000050d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000050e0| 20 20 20 20 2f 20 5c 0a | 58 20 20 20 20 20 20 20 | / \.|X |
|000050f0| 20 20 20 20 20 20 20 20 | 20 2f 20 20 20 5c 20 20 | | / \ |
|00005100| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005110| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 20 | | / |
|00005120| 20 20 20 20 5c 0a 58 20 | 20 20 20 20 20 20 20 20 | \.X | |
|00005130| 20 20 20 20 20 20 61 20 | 20 20 20 20 43 20 20 20 | a | C |
|00005140| 20 20 20 20 20 20 20 20 | 3d 3d 3e 20 20 20 20 20 | |==> |
|00005150| 20 20 20 20 20 20 20 20 | 20 20 20 41 20 20 20 20 | | A |
|00005160| 20 20 20 43 0a 58 20 20 | 20 20 20 20 20 20 20 20 | C.X | |
|00005170| 20 20 20 20 20 20 20 20 | 20 20 2f 20 5c 20 20 20 | | / \ |
|00005180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005190| 20 20 20 20 20 20 20 20 | 20 2f 20 5c 20 20 20 20 | | / \ |
|000051a0| 20 2f 20 5c 0a 58 20 20 | 20 20 20 20 20 20 20 20 | / \.X | |
|000051b0| 20 20 20 20 20 20 20 20 | 20 2f 20 20 20 5c 20 20 | | / \ |
|000051c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000051d0| 20 20 20 20 20 20 20 20 | 2f 20 20 20 7c 20 20 20 | |/ | |
|000051e0| 7c 20 20 20 5c 0a 58 20 | 20 20 20 20 20 20 20 20 || \.X | |
|000051f0| 20 20 20 20 20 20 20 20 | 20 42 20 20 20 20 20 63 | | B c|
|00005200| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005210| 20 20 20 20 20 20 20 20 | 61 20 20 20 62 31 20 20 | |a b1 |
|00005220| 20 62 32 20 20 20 63 0a | 58 20 20 20 20 20 20 20 | b2 c.|X |
|00005230| 20 20 20 20 20 20 20 20 | 20 20 2f 20 5c 20 0a 58 | | / \ .X|
|00005240| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005250| 2f 20 20 20 5c 0a 58 20 | 20 20 20 20 20 20 20 20 |/ \.X | |
|00005260| 20 20 20 20 20 62 31 20 | 20 20 20 62 32 0a 58 0a | b1 | b2.X.|
|00005270| 58 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |X=======|========|
|00005280| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005290| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000052a0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 0a |========|=======.|
|000052b0| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X | |
|000052c0| 20 20 20 20 20 20 20 20 | 20 20 42 41 4c 41 4e 43 | | BALANC|
|000052d0| 45 20 46 41 43 54 4f 52 | 53 0a 58 20 20 20 20 42 |E FACTOR|S.X B|
|000052e0| 45 46 4f 52 45 20 52 4f | 54 41 54 49 4f 4e 20 20 |EFORE RO|TATION |
|000052f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005300| 20 20 20 20 20 20 20 20 | 20 20 20 20 41 46 54 45 | | AFTE|
|00005310| 52 20 52 4f 54 41 54 49 | 4f 4e 0a 58 2d 2d 2d 2d |R ROTATI|ON.X----|
|00005320| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005330| 2d 2d 2d 2d 20 20 20 20 | 20 20 20 20 20 20 20 20 |---- | |
|00005340| 20 20 20 20 20 20 20 20 | 2d 2d 2d 2d 2d 2d 2d 2d | |--------|
|00005350| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 0a |--------|-------.|
|00005360| 58 41 20 3d 20 2b 32 20 | 3b 20 43 20 3d 20 2d 31 |XA = +2 |; C = -1|
|00005370| 20 3b 20 42 20 3d 20 2b | 31 20 20 20 20 20 20 20 | ; B = +|1 |
|00005380| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 41 20 3d | | A =|
|00005390| 20 2d 31 20 3b 20 42 20 | 3d 20 30 20 3b 20 43 20 | -1 ; B |= 0 ; C |
|000053a0| 3d 20 30 0a 58 41 20 3d | 20 2b 32 20 3b 20 43 20 |= 0.XA =| +2 ; C |
|000053b0| 3d 20 2d 31 20 3b 20 42 | 20 3d 20 20 30 20 20 20 |= -1 ; B| = 0 |
|000053c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000053d0| 20 41 20 3d 20 20 30 20 | 3b 20 42 20 3d 20 30 20 | A = 0 |; B = 0 |
|000053e0| 3b 20 43 20 3d 20 30 0a | 58 41 20 3d 20 2b 32 20 |; C = 0.|XA = +2 |
|000053f0| 3b 20 43 20 3d 20 2d 31 | 20 3b 20 42 20 3d 20 2d |; C = -1| ; B = -|
|00005400| 31 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |1 | |
|00005410| 20 20 20 20 20 41 20 3d | 20 20 30 20 3b 20 42 20 | A =| 0 ; B |
|00005420| 3d 20 30 20 3b 20 43 20 | 3d 2b 31 0a 58 3d 3d 3d |= 0 ; C |=+1.X===|
|00005430| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005440| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005450| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005460| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 0a 58 0a 58 53 |========|===.X.XS|
|00005470| 6f 20 77 65 20 67 65 74 | 2c 20 69 6e 20 61 6c 6c |o we get|, in all|
|00005480| 20 74 68 72 65 65 20 63 | 61 73 65 73 3a 0a 58 0a | three c|ases:.X.|
|00005490| 58 20 20 20 20 20 20 20 | 20 20 20 6e 65 77 41 20 |X | newA |
|000054a0| 3d 20 2d 6d 61 78 28 20 | 6f 6c 64 42 2c 20 30 20 |= -max( |oldB, 0 |
|000054b0| 29 0a 58 20 20 20 20 20 | 20 20 20 20 20 6e 65 77 |).X | new|
|000054c0| 43 20 3d 20 2d 6d 69 6e | 28 20 6f 6c 64 42 2c 20 |C = -min|( oldB, |
|000054d0| 30 20 29 0a 58 20 20 20 | 20 20 20 20 20 20 20 6e |0 ).X | n|
|000054e0| 65 77 42 20 3d 20 30 0a | 58 0a 58 4e 6f 77 20 66 |ewB = 0.|X.XNow f|
|000054f0| 6f 72 20 61 20 64 6f 75 | 62 6c 65 20 52 4c 20 72 |or a dou|ble RL r|
|00005500| 6f 74 61 74 69 6f 6e 20 | 77 65 20 68 61 76 65 20 |otation |we have |
|00005510| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 70 6f |the foll|owing po|
|00005520| 73 73 69 62 69 6c 69 74 | 69 65 73 20 28 61 67 61 |ssibilit|ies (aga|
|00005530| 69 6e 2c 20 74 68 65 0a | 58 70 69 63 74 75 72 65 |in, the.|Xpicture|
|00005540| 20 69 73 20 74 68 65 20 | 6d 69 72 72 6f 72 20 69 | is the |mirror i|
|00005550| 6d 61 67 65 20 6f 66 20 | 74 68 65 20 4c 52 20 63 |mage of |the LR c|
|00005560| 61 73 65 29 3a 0a 58 0a | 58 3d 3d 3d 3d 3d 3d 3d |ase):.X.|X=======|
|00005570| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005580| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005590| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000055a0| 3d 3d 3d 3d 3d 3d 3d 0a | 58 20 20 20 20 20 20 20 |=======.|X |
|000055b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000055c0| 20 20 42 41 4c 41 4e 43 | 45 20 46 41 43 54 4f 52 | BALANC|E FACTOR|
|000055d0| 53 0a 58 20 20 20 20 42 | 45 46 4f 52 45 20 52 4f |S.X B|EFORE RO|
|000055e0| 54 41 54 49 4f 4e 20 20 | 20 20 20 20 20 20 20 20 |TATION | |
|000055f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005600| 20 20 20 20 41 46 54 45 | 52 20 52 4f 54 41 54 49 | AFTE|R ROTATI|
|00005610| 4f 4e 0a 58 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |ON.X----|--------|
|00005620| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 20 20 20 20 |--------|---- |
|00005630| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005640| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005650| 2d 2d 2d 2d 2d 2d 2d 0a | 58 41 20 3d 20 2d 32 20 |-------.|XA = -2 |
|00005660| 3b 20 43 20 3d 20 2b 31 | 20 3b 20 42 20 3d 20 2b |; C = +1| ; B = +|
|00005670| 31 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |1 | |
|00005680| 20 20 20 20 20 41 20 3d | 20 2d 31 20 3b 20 42 20 | A =| -1 ; B |
|00005690| 3d 20 30 20 3b 20 43 20 | 3d 20 30 0a 58 41 20 3d |= 0 ; C |= 0.XA =|
|000056a0| 20 2d 32 20 3b 20 43 20 | 3d 20 2b 31 20 3b 20 42 | -2 ; C |= +1 ; B|
|000056b0| 20 3d 20 20 30 20 20 20 | 20 20 20 20 20 20 20 20 | = 0 | |
|000056c0| 20 20 20 20 20 20 20 20 | 20 41 20 3d 20 20 30 20 | | A = 0 |
|000056d0| 3b 20 42 20 3d 20 30 20 | 3b 20 43 20 3d 20 30 0a |; B = 0 |; C = 0.|
|000056e0| 58 41 20 3d 20 2d 32 20 | 3b 20 43 20 3d 20 2b 31 |XA = -2 |; C = +1|
|000056f0| 20 3b 20 42 20 3d 20 2d | 31 20 20 20 20 20 20 20 | ; B = -|1 |
|00005700| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 41 20 3d | | A =|
|00005710| 20 20 30 20 3b 20 42 20 | 3d 20 30 20 3b 20 43 20 | 0 ; B |= 0 ; C |
|00005720| 3d 2b 31 0a 58 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |=+1.X===|========|
|00005730| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005740| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005750| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00005760| 3d 3d 3d 0a 58 0a 58 53 | 6f 20 77 65 20 67 65 74 |===.X.XS|o we get|
|00005770| 2c 20 69 6e 20 61 6c 6c | 20 74 68 72 65 65 20 63 |, in all| three c|
|00005780| 61 73 65 73 3a 0a 58 0a | 58 20 20 20 20 20 20 20 |ases:.X.|X |
|00005790| 20 20 20 6e 65 77 41 20 | 3d 20 2d 6d 61 78 28 20 | newA |= -max( |
|000057a0| 6f 6c 64 42 2c 20 30 20 | 29 0a 58 20 20 20 20 20 |oldB, 0 |).X |
|000057b0| 20 20 20 20 20 6e 65 77 | 43 20 3d 20 2d 6d 69 6e | new|C = -min|
|000057c0| 28 20 6f 6c 64 42 2c 20 | 30 20 29 0a 58 20 20 20 |( oldB, |0 ).X |
|000057d0| 20 20 20 20 20 20 20 6e | 65 77 42 20 3d 20 30 0a | n|ewB = 0.|
|000057e0| 58 0a 58 54 68 69 73 20 | 69 73 20 45 58 41 43 54 |X.XThis |is EXACT|
|000057f0| 4c 59 20 77 68 61 74 20 | 77 65 20 68 61 64 20 66 |LY what |we had f|
|00005800| 6f 72 20 74 68 65 20 4c | 52 20 63 61 73 65 20 28 |or the L|R case (|
|00005810| 69 73 6e 74 20 74 68 61 | 74 20 6e 69 63 65 21 21 |isnt tha|t nice!!|
|00005820| 21 29 20 73 6f 20 6e 6f | 77 20 77 65 20 63 61 6e |!) so no|w we can|
|00005830| 20 0a 58 63 6f 64 65 20 | 75 70 20 61 20 64 6f 75 | .Xcode |up a dou|
|00005840| 62 6c 65 20 72 6f 74 61 | 74 69 6f 6e 20 61 73 20 |ble rota|tion as |
|00005850| 66 6f 6c 6c 6f 77 73 3a | 0a 58 0c 0a 58 2f 2a 0a |follows:|.X..X/*.|
|00005860| 58 2a 20 72 6f 74 61 74 | 65 5f 74 77 69 63 65 28 |X* rotat|e_twice(|
|00005870| 29 20 20 2d 2d 20 20 72 | 6f 74 61 74 65 20 61 20 |) -- r|otate a |
|00005880| 67 69 76 65 6e 20 6e 6f | 64 65 20 69 6e 20 74 68 |given no|de in th|
|00005890| 65 20 67 69 76 65 6e 20 | 64 69 72 65 63 74 69 6f |e given |directio|
|000058a0| 6e 0a 58 2a 20 20 20 20 | 20 20 20 20 20 20 20 20 |n.X* | |
|000058b0| 20 20 20 20 20 20 20 20 | 20 61 6e 64 20 74 68 65 | | and the|
|000058c0| 6e 20 69 6e 20 74 68 65 | 20 6f 70 70 6f 73 69 74 |n in the| opposit|
|000058d0| 65 20 64 69 72 65 63 74 | 69 6f 6e 0a 58 2a 20 20 |e direct|ion.X* |
|000058e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000058f0| 20 20 20 74 6f 20 72 65 | 73 74 6f 72 65 20 74 68 | to re|store th|
|00005900| 65 20 62 61 6c 61 6e 63 | 65 20 6f 66 20 61 20 74 |e balanc|e of a t|
|00005910| 72 65 65 0a 58 2a 2f 0a | 58 76 6f 69 64 20 72 6f |ree.X*/.|Xvoid ro|
|00005920| 74 61 74 65 5f 74 77 69 | 63 65 28 20 72 6f 6f 74 |tate_twi|ce( root|
|00005930| 70 2c 20 64 69 72 20 29 | 0a 58 41 56 4c 74 72 65 |p, dir )|.XAVLtre|
|00005940| 65 20 20 20 20 2a 72 6f | 6f 74 70 3b 0a 58 44 49 |e *ro|otp;.XDI|
|00005950| 52 45 43 54 49 4f 4e 20 | 20 64 69 72 3b 0a 58 7b |RECTION | dir;.X{|
|00005960| 0a 58 20 44 49 52 45 43 | 54 49 4f 4e 20 20 20 6f |.X DIREC|TION o|
|00005970| 74 68 65 72 5f 64 69 72 | 09 09 3d 20 4f 50 50 4f |ther_dir|..= OPPO|
|00005980| 53 49 54 45 28 20 64 69 | 72 20 29 3b 0a 58 20 41 |SITE( di|r );.X A|
|00005990| 56 4c 74 72 65 65 20 20 | 20 20 20 6f 6c 64 5f 72 |VLtree | old_r|
|000059a0| 6f 6f 74 09 09 3d 20 2a | 72 6f 6f 74 70 2c 0a 58 |oot..= *|rootp,.X|
|000059b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 6f 6c 64 | | old|
|000059c0| 5f 6f 74 68 65 72 5f 64 | 69 72 5f 73 75 62 74 72 |_other_d|ir_subtr|
|000059d0| 65 65 09 3d 20 28 2a 72 | 6f 6f 74 70 29 20 2d 3e |ee.= (*r|ootp) ->|
|000059e0| 20 73 75 62 74 72 65 65 | 5b 20 6f 74 68 65 72 5f | subtree|[ other_|
|000059f0| 64 69 72 20 5d 3b 0a 58 | 20 20 20 20 0a 58 20 20 |dir ];.X| .X |
|00005a00| 20 20 20 20 20 20 2f 2a | 20 61 73 73 69 67 6e 20 | /*| assign |
|00005a10| 6e 65 77 20 72 6f 6f 74 | 20 2a 2f 0a 58 20 2a 72 |new root| */.X *r|
|00005a20| 6f 6f 74 70 20 3d 20 6f | 6c 64 5f 72 6f 6f 74 20 |ootp = o|ld_root |
|00005a30| 2d 3e 20 73 75 62 74 72 | 65 65 5b 20 6f 74 68 65 |-> subtr|ee[ othe|
|00005a40| 72 5f 64 69 72 20 5d 20 | 2d 3e 20 73 75 62 74 72 |r_dir ] |-> subtr|
|00005a50| 65 65 5b 20 64 69 72 20 | 5d 3b 0a 58 20 20 0a 58 |ee[ dir |];.X .X|
|00005a60| 20 20 20 20 20 20 20 20 | 2f 2a 20 6e 65 77 2d 72 | |/* new-r|
|00005a70| 6f 6f 74 20 65 78 63 68 | 61 6e 67 65 73 20 69 74 |oot exch|anges it|
|00005a80| 27 73 20 22 64 69 72 22 | 20 73 75 62 74 72 65 65 |'s "dir"| subtree|
|00005a90| 20 66 6f 72 20 69 74 27 | 73 20 67 72 61 6e 64 70 | for it'|s grandp|
|00005aa0| 61 72 65 6e 74 20 2a 2f | 0a 58 20 6f 6c 64 5f 72 |arent */|.X old_r|
|00005ab0| 6f 6f 74 20 2d 3e 20 73 | 75 62 74 72 65 65 5b 20 |oot -> s|ubtree[ |
|00005ac0| 6f 74 68 65 72 5f 64 69 | 72 20 5d 20 20 3d 20 20 |other_di|r ] = |
|00005ad0| 20 28 2a 72 6f 6f 74 70 | 29 20 2d 3e 20 73 75 62 | (*rootp|) -> sub|
|00005ae0| 74 72 65 65 5b 20 64 69 | 72 20 5d 3b 0a 58 20 28 |tree[ di|r ];.X (|
|00005af0| 2a 72 6f 6f 74 70 29 20 | 2d 3e 20 73 75 62 74 72 |*rootp) |-> subtr|
|00005b00| 65 65 5b 20 64 69 72 20 | 5d 20 20 20 20 20 20 20 |ee[ dir |] |
|00005b10| 20 3d 20 20 20 6f 6c 64 | 5f 72 6f 6f 74 3b 0a 58 | = old|_root;.X|
|00005b20| 20 20 0a 58 20 20 20 20 | 20 20 20 2f 2a 20 6e 65 | .X | /* ne|
|00005b30| 77 2d 72 6f 6f 74 20 65 | 78 63 68 61 6e 67 65 73 |w-root e|xchanges|
|00005b40| 20 69 74 27 73 20 22 6f | 74 68 65 72 2d 64 69 72 | it's "o|ther-dir|
|00005b50| 22 20 73 75 62 74 72 65 | 65 20 66 6f 72 20 69 74 |" subtre|e for it|
|00005b60| 27 73 20 70 61 72 65 6e | 74 20 2a 2f 0a 58 20 6f |'s paren|t */.X o|
|00005b70| 6c 64 5f 6f 74 68 65 72 | 5f 64 69 72 5f 73 75 62 |ld_other|_dir_sub|
|00005b80| 74 72 65 65 20 2d 3e 20 | 73 75 62 74 72 65 65 5b |tree -> |subtree[|
|00005b90| 20 64 69 72 20 5d 20 3d | 20 20 20 28 2a 72 6f 6f | dir ] =| (*roo|
|00005ba0| 74 70 29 20 2d 3e 20 73 | 75 62 74 72 65 65 5b 20 |tp) -> s|ubtree[ |
|00005bb0| 6f 74 68 65 72 5f 64 69 | 72 20 5d 3b 0a 58 20 28 |other_di|r ];.X (|
|00005bc0| 2a 72 6f 6f 74 70 29 20 | 2d 3e 20 73 75 62 74 72 |*rootp) |-> subtr|
|00005bd0| 65 65 5b 20 6f 74 68 65 | 72 5f 64 69 72 20 5d 09 |ee[ othe|r_dir ].|
|00005be0| 09 20 3d 20 20 20 6f 6c | 64 5f 6f 74 68 65 72 5f |. = ol|d_other_|
|00005bf0| 64 69 72 5f 73 75 62 74 | 72 65 65 3b 0a 58 20 20 |dir_subt|ree;.X |
|00005c00| 0a 58 20 20 20 20 20 20 | 20 20 2f 2a 20 75 70 64 |.X | /* upd|
|00005c10| 61 74 65 20 62 61 6c 61 | 6e 63 65 73 20 2a 2f 0a |ate bala|nces */.|
|00005c20| 58 20 28 2a 72 6f 6f 74 | 70 29 20 2d 3e 20 73 75 |X (*root|p) -> su|
|00005c30| 62 74 72 65 65 5b 20 4c | 45 46 54 20 5d 20 2d 3e |btree[ L|EFT ] ->|
|00005c40| 20 62 61 6c 20 20 20 3d | 20 20 2d 4d 41 58 28 20 | bal =| -MAX( |
|00005c50| 28 2a 72 6f 6f 74 70 29 | 20 2d 3e 20 62 61 6c 2c |(*rootp)| -> bal,|
|00005c60| 20 30 20 29 3b 0a 58 20 | 28 2a 72 6f 6f 74 70 29 | 0 );.X |(*rootp)|
|00005c70| 20 2d 3e 20 73 75 62 74 | 72 65 65 5b 20 52 49 47 | -> subt|ree[ RIG|
|00005c80| 48 54 20 5d 20 2d 3e 20 | 62 61 6c 20 20 3d 20 20 |HT ] -> |bal = |
|00005c90| 2d 4d 49 4e 28 20 28 2a | 72 6f 6f 74 70 29 20 2d |-MIN( (*|rootp) -|
|00005ca0| 3e 20 62 61 6c 2c 20 30 | 20 29 3b 0a 58 20 28 2a |> bal, 0| );.X (*|
|00005cb0| 72 6f 6f 74 70 29 20 2d | 3e 20 62 61 6c 20 20 20 |rootp) -|> bal |
|00005cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005cd0| 20 20 20 3d 20 20 30 3b | 0a 58 0a 58 7d 2f 2a 20 | = 0;|.X.X}/* |
|00005ce0| 72 6f 74 61 74 65 5f 74 | 77 69 63 65 20 2a 2f 0a |rotate_t|wice */.|
|00005cf0| 58 0a 58 4e 6f 77 20 69 | 73 6e 74 20 74 68 61 74 |X.XNow i|snt that|
|00005d00| 20 73 70 65 63 69 61 6c | 21 20 4e 6f 77 20 74 68 | special|! Now th|
|00005d10| 61 74 20 77 65 20 68 61 | 76 65 20 74 68 65 20 72 |at we ha|ve the r|
|00005d20| 6f 74 61 74 69 6f 6e 20 | 72 6f 75 74 69 6e 65 73 |otation |routines|
|00005d30| 20 77 72 69 74 74 65 6e | 2c 0a 58 77 65 20 6a 75 | written|,.Xwe ju|
|00005d40| 73 74 20 6e 65 65 64 20 | 74 6f 20 77 6f 72 72 79 |st need |to worry|
|00005d50| 20 61 62 6f 75 74 20 77 | 68 65 6e 20 74 6f 20 63 | about w|hen to c|
|00005d60| 61 6c 6c 20 74 68 65 6d | 2e 20 4f 6e 65 20 68 65 |all them|. One he|
|00005d70| 6c 70 20 69 73 20 61 20 | 72 6f 75 74 69 6e 65 20 |lp is a |routine |
|00005d80| 63 61 6c 6c 65 64 0a 58 | 62 61 6c 61 6e 63 65 20 |called.X|balance |
|00005d90| 77 68 69 63 68 20 69 73 | 20 63 61 6c 6c 65 64 20 |which is| called |
|00005da0| 77 68 65 6e 20 61 20 6e | 6f 64 65 20 67 65 74 73 |when a n|ode gets|
|00005db0| 20 74 6f 6f 20 68 65 61 | 76 79 20 6f 6e 20 61 20 | too hea|vy on a |
|00005dc0| 70 61 72 74 69 63 75 6c | 61 72 20 73 69 64 65 2e |particul|ar side.|
|00005dd0| 20 0a 58 48 65 72 65 20 | 77 65 20 6e 65 65 64 20 | .XHere |we need |
|00005de0| 74 6f 20 74 61 6b 65 20 | 69 6e 74 6f 20 61 63 63 |to take |into acc|
|00005df0| 6f 75 6e 74 20 74 68 65 | 20 73 70 65 63 69 61 6c |ount the| special|
|00005e00| 20 63 61 73 65 20 74 68 | 61 74 20 6f 63 63 75 72 | case th|at occur|
|00005e10| 73 20 77 68 65 6e 20 61 | 20 0a 58 73 69 6e 67 6c |s when a| .Xsingl|
|00005e20| 65 20 72 6f 74 61 74 69 | 6f 6e 20 77 61 73 20 6d |e rotati|on was m|
|00005e30| 61 64 65 20 62 75 74 20 | 74 68 65 20 48 45 49 47 |ade but |the HEIG|
|00005e40| 48 54 20 6f 66 20 74 68 | 65 20 72 6f 74 61 74 65 |HT of th|e rotate|
|00005e50| 64 20 74 72 65 65 20 64 | 69 64 20 4e 4f 54 20 63 |d tree d|id NOT c|
|00005e60| 68 61 6e 67 65 0a 58 61 | 73 20 61 20 72 65 73 75 |hange.Xa|s a resu|
|00005e70| 6c 74 20 6f 66 20 74 68 | 65 20 72 6f 74 61 74 69 |lt of th|e rotati|
|00005e80| 6f 6e 20 28 64 69 73 63 | 75 73 73 65 64 20 69 6e |on (disc|ussed in|
|00005e90| 20 6d 6f 72 65 20 64 65 | 74 61 69 6c 20 69 6e 20 | more de|tail in |
|00005ea0| 74 68 65 20 6e 65 78 74 | 20 73 65 63 74 69 6f 6e |the next| section|
|00005eb0| 29 3a 0a 58 0a 58 0c 0a | 58 20 20 20 20 20 20 20 |):.X.X..|X |
|00005ec0| 2f 2a 20 72 65 74 75 72 | 6e 20 63 6f 64 65 73 20 |/* retur|n codes |
|00005ed0| 75 73 65 64 20 62 79 20 | 61 76 6c 5f 69 6e 73 65 |used by |avl_inse|
|00005ee0| 72 74 28 29 2c 20 61 76 | 6c 5f 64 65 6c 65 74 65 |rt(), av|l_delete|
|00005ef0| 28 29 2c 20 61 6e 64 20 | 62 61 6c 61 6e 63 65 28 |(), and |balance(|
|00005f00| 29 20 2a 2f 0a 58 23 64 | 65 66 69 6e 65 20 20 48 |) */.X#d|efine H|
|00005f10| 45 49 47 48 54 5f 55 4e | 43 48 41 4e 47 45 44 09 |EIGHT_UN|CHANGED.|
|00005f20| 30 0a 58 23 64 65 66 69 | 6e 65 20 20 48 45 49 47 |0.X#defi|ne HEIG|
|00005f30| 48 54 5f 43 48 41 4e 47 | 45 44 09 09 31 0a 58 0a |HT_CHANG|ED..1.X.|
|00005f40| 58 20 20 20 20 20 20 20 | 2f 2a 20 42 61 6c 61 6e |X |/* Balan|
|00005f50| 63 65 20 44 65 66 69 6e | 69 74 69 6f 6e 73 20 2a |ce Defin|itions *|
|00005f60| 2f 0a 58 23 64 65 66 69 | 6e 65 20 20 4c 45 46 54 |/.X#defi|ne LEFT|
|00005f70| 5f 48 45 41 56 59 20 20 | 20 20 20 20 20 20 20 20 |_HEAVY | |
|00005f80| 20 20 2d 31 0a 58 23 64 | 65 66 69 6e 65 20 20 42 | -1.X#d|efine B|
|00005f90| 41 4c 41 4e 43 45 44 20 | 20 20 20 20 20 20 20 20 |ALANCED | |
|00005fa0| 20 20 20 20 20 20 30 0a | 58 23 64 65 66 69 6e 65 | 0.|X#define|
|00005fb0| 20 20 52 49 47 48 54 5f | 48 45 41 56 59 20 20 20 | RIGHT_|HEAVY |
|00005fc0| 20 20 20 20 20 20 20 20 | 20 31 0a 58 23 64 65 66 | | 1.X#def|
|00005fd0| 69 6e 65 20 20 4c 45 46 | 54 5f 49 4d 42 41 4c 41 |ine LEF|T_IMBALA|
|00005fe0| 4e 43 45 28 6e 64 29 20 | 20 20 20 28 20 28 6e 64 |NCE(nd) | ( (nd|
|00005ff0| 29 2d 3e 62 61 6c 20 3c | 20 4c 45 46 54 5f 48 45 |)->bal <| LEFT_HE|
|00006000| 41 56 59 20 20 29 0a 58 | 23 64 65 66 69 6e 65 20 |AVY ).X|#define |
|00006010| 20 52 49 47 48 54 5f 49 | 4d 42 41 4c 41 4e 43 45 | RIGHT_I|MBALANCE|
|00006020| 28 6e 64 29 20 20 20 28 | 20 28 6e 64 29 2d 3e 62 |(nd) (| (nd)->b|
|00006030| 61 6c 20 3e 20 52 49 47 | 48 54 5f 48 45 41 56 59 |al > RIG|HT_HEAVY|
|00006040| 20 29 0a 58 0a 58 2f 2a | 0a 58 2a 20 62 61 6c 61 | ).X.X/*|.X* bala|
|00006050| 6e 63 65 28 29 20 20 2d | 2d 20 20 64 65 74 65 72 |nce() -|- deter|
|00006060| 6d 69 6e 65 73 20 61 6e | 64 20 70 65 72 66 6f 72 |mines an|d perfor|
|00006070| 6d 73 20 74 68 65 20 20 | 73 65 71 75 65 6e 63 65 |ms the |sequence|
|00006080| 20 6f 66 20 72 6f 74 61 | 74 69 6f 6e 73 20 6e 65 | of rota|tions ne|
|00006090| 65 64 65 64 0a 58 2a 20 | 20 20 20 20 20 20 20 20 |eded.X* | |
|000060a0| 20 20 20 20 20 20 20 20 | 20 20 28 69 66 20 61 6e | | (if an|
|000060b0| 79 29 20 74 6f 20 72 65 | 73 74 6f 72 65 20 74 68 |y) to re|store th|
|000060c0| 65 20 62 61 6c 61 6e 63 | 65 20 6f 66 20 61 20 67 |e balanc|e of a g|
|000060d0| 69 76 65 6e 20 74 72 65 | 65 2e 0a 58 2a 0a 58 2a |iven tre|e..X*.X*|
|000060e0| 20 20 20 20 20 52 65 74 | 75 72 6e 73 20 31 20 69 | Ret|urns 1 i|
|000060f0| 66 20 74 72 65 65 20 68 | 65 69 67 68 74 20 63 68 |f tree h|eight ch|
|00006100| 61 6e 67 65 64 20 64 75 | 65 20 74 6f 20 72 6f 74 |anged du|e to rot|
|00006110| 61 74 69 6f 6e 3b 20 30 | 20 6f 74 68 65 72 77 69 |ation; 0| otherwi|
|00006120| 73 65 0a 58 2a 2f 0a 58 | 73 68 6f 72 74 20 20 62 |se.X*/.X|short b|
|00006130| 61 6c 61 6e 63 65 28 20 | 72 6f 6f 74 70 20 29 0a |alance( |rootp ).|
|00006140| 58 41 56 4c 74 72 65 65 | 20 20 20 20 2a 72 6f 6f |XAVLtree| *roo|
|00006150| 74 70 3b 0a 58 7b 0a 58 | 20 20 20 20 73 68 6f 72 |tp;.X{.X| shor|
|00006160| 74 20 20 73 70 65 63 69 | 61 6c 5f 63 61 73 65 20 |t speci|al_case |
|00006170| 3d 20 46 41 4c 53 45 3b | 0a 58 0a 58 20 20 20 20 |= FALSE;|.X.X |
|00006180| 69 66 20 28 20 4c 45 46 | 54 5f 49 4d 42 41 4c 41 |if ( LEF|T_IMBALA|
|00006190| 4e 43 45 28 20 2a 72 6f | 6f 74 70 20 29 20 20 29 |NCE( *ro|otp ) )|
|000061a0| 20 20 7b 20 20 20 2f 2a | 20 6e 65 65 64 20 61 20 | { /*| need a |
|000061b0| 72 69 67 68 74 20 72 6f | 74 61 74 69 6f 6e 20 2a |right ro|tation *|
|000061c0| 2f 0a 58 20 20 20 20 20 | 20 20 20 69 66 20 28 20 |/.X | if ( |
|000061d0| 28 2a 72 6f 6f 74 70 29 | 20 2d 3e 20 73 75 62 74 |(*rootp)| -> subt|
|000061e0| 72 65 65 5b 20 4c 45 46 | 54 20 5d 20 2d 3e 20 62 |ree[ LEF|T ] -> b|
|000061f0| 61 6c 20 20 3d 3d 20 20 | 52 49 47 48 54 5f 48 45 |al == |RIGHT_HE|
|00006200| 41 56 59 20 29 0a 58 20 | 20 20 20 20 20 20 20 20 |AVY ).X | |
|00006210| 20 20 20 72 6f 74 61 74 | 65 5f 74 77 69 63 65 28 | rotat|e_twice(|
|00006220| 20 72 6f 6f 74 70 2c 20 | 52 49 47 48 54 20 29 3b | rootp, |RIGHT );|
|00006230| 20 20 20 20 2f 2a 20 64 | 6f 75 62 6c 65 20 52 4c | /* d|ouble RL|
|00006240| 20 72 6f 74 61 74 69 6f | 6e 20 6e 65 65 64 65 64 | rotatio|n needed|
|00006250| 20 2a 2f 0a 58 0a 58 20 | 20 20 20 20 20 20 20 65 | */.X.X | e|
|00006260| 6c 73 65 09 2f 2a 20 73 | 69 6e 67 6c 65 20 52 52 |lse./* s|ingle RR|
|00006270| 20 72 6f 74 61 74 69 6f | 6e 20 6e 65 65 64 65 64 | rotatio|n needed|
|00006280| 20 2a 2f 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 | */.X | |
|00006290| 20 73 70 65 63 69 61 6c | 5f 63 61 73 65 20 3d 20 | special|_case = |
|000062a0| 72 6f 74 61 74 65 5f 6f | 6e 63 65 28 20 72 6f 6f |rotate_o|nce( roo|
|000062b0| 74 70 2c 20 52 49 47 48 | 54 20 29 3b 0a 58 20 20 |tp, RIGH|T );.X |
|000062c0| 20 20 7d 2f 2a 20 69 66 | 20 2a 2f 0a 58 20 20 0a | }/* if| */.X .|
|000062d0| 58 20 20 20 20 65 6c 73 | 65 20 69 66 20 28 20 52 |X els|e if ( R|
|000062e0| 49 47 48 54 5f 49 4d 42 | 41 4c 41 4e 43 45 28 20 |IGHT_IMB|ALANCE( |
|000062f0| 2a 72 6f 6f 74 70 20 29 | 20 20 29 20 20 7b 20 20 |*rootp )| ) { |
|00006300| 20 2f 2a 20 6e 65 65 64 | 20 61 20 6c 65 66 74 20 | /* need| a left |
|00006310| 72 6f 74 61 74 69 6f 6e | 20 2a 2f 0a 58 20 20 20 |rotation| */.X |
|00006320| 20 20 20 20 20 69 66 20 | 28 20 28 2a 72 6f 6f 74 | if |( (*root|
|00006330| 70 29 20 2d 3e 20 73 75 | 62 74 72 65 65 5b 20 52 |p) -> su|btree[ R|
|00006340| 49 47 48 54 20 5d 20 2d | 3e 20 62 61 6c 20 20 3d |IGHT ] -|> bal =|
|00006350| 3d 20 20 4c 45 46 54 5f | 48 45 41 56 59 20 29 0a |= LEFT_|HEAVY ).|
|00006360| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 72 6f 74 |X | rot|
|00006370| 61 74 65 5f 74 77 69 63 | 65 28 20 72 6f 6f 74 70 |ate_twic|e( rootp|
|00006380| 2c 20 4c 45 46 54 20 29 | 3b 20 20 20 20 20 2f 2a |, LEFT )|; /*|
|00006390| 20 64 6f 75 62 6c 65 20 | 4c 52 20 72 6f 74 61 74 | double |LR rotat|
|000063a0| 69 6f 6e 20 6e 65 65 64 | 65 64 20 2a 2f 0a 58 0a |ion need|ed */.X.|
|000063b0| 58 20 20 20 20 20 20 20 | 20 65 6c 73 65 09 2f 2a |X | else./*|
|000063c0| 20 73 69 6e 67 6c 65 20 | 4c 4c 20 72 6f 74 61 74 | single |LL rotat|
|000063d0| 69 6f 6e 20 6e 65 65 64 | 65 64 20 2a 2f 0a 58 20 |ion need|ed */.X |
|000063e0| 20 20 20 20 20 20 20 20 | 20 20 20 73 70 65 63 69 | | speci|
|000063f0| 61 6c 5f 63 61 73 65 20 | 3d 20 72 6f 74 61 74 65 |al_case |= rotate|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
