0000: 23 23 0a 23 23 20 54 68 69 73 20 66 69 6c 65 20 ##.## This file
0010: 69 6d 70 6c 65 6d 65 6e 74 73 20 61 6e 20 69 6e implements an in
0020: 2d 6d 65 6d 6f 72 79 20 62 61 6c 61 6e 63 65 64 -memory balanced
0030: 20 62 69 6e 61 72 79 20 74 72 65 65 2e 20 20 54 binary tree. T
0040: 68 69 73 20 63 6f 64 65 0a 23 23 20 77 61 73 20 his code.## was
0050: 6f 72 69 67 69 6e 61 6c 6c 79 20 62 72 6f 75 67 originally broug
0060: 68 74 20 69 6e 20 74 6f 20 69 6d 70 6c 65 6d 65 ht in to impleme
0070: 6e 74 20 61 6e 20 65 66 66 69 63 69 65 6e 74 20 nt an efficient
0080: 70 72 69 6f 72 69 74 79 20 71 75 65 75 65 0a 23 priority queue.#
0090: 23 20 66 6f 72 20 74 68 65 20 44 69 6a 6b 73 74 # for the Dijkst
00a0: 72 61 27 73 20 73 68 6f 72 74 65 73 74 20 70 61 ra's shortest pa
00b0: 74 68 20 61 6c 67 6f 72 69 74 68 6d 20 69 6e 20 th algorithm in
00c0: 63 72 65 77 72 6f 75 74 65 2e 63 2e 0a 23 23 0a crewroute.c..##.
00d0: 23 23 20 54 68 69 73 20 66 69 6c 65 20 63 6f 6e ## This file con
00e0: 74 61 69 6e 73 20 63 6f 64 65 20 69 6d 70 6f 72 tains code impor
00f0: 74 65 64 20 69 6e 74 6f 20 52 45 41 44 49 20 66 ted into READI f
0100: 72 6f 6d 20 61 6e 6f 74 68 65 72 20 70 72 6f 6a rom another proj
0110: 65 63 74 2e 0a 23 23 20 54 68 65 20 74 65 78 74 ect..## The text
0120: 20 6f 66 20 74 68 65 20 6f 72 69 67 69 6e 61 6c of the original
0130: 20 68 65 61 64 65 72 20 63 6f 6d 6d 65 6e 74 20 header comment
0140: 66 6f 6c 6c 6f 77 73 3a 0a 23 23 0a 23 23 0a 23 follows:.##.##.#
0150: 23 20 41 20 70 61 63 6b 61 67 65 20 6f 66 20 72 # A package of r
0160: 6f 75 74 69 6e 65 73 20 66 6f 72 20 68 61 6e 64 outines for hand
0170: 6c 69 6e 67 20 62 61 6c 61 6e 63 65 64 20 62 69 ling balanced bi
0180: 6e 61 72 79 20 74 72 65 65 73 2e 0a 23 23 20 43 nary trees..## C
0190: 6f 70 79 72 69 67 68 74 20 28 63 29 20 31 39 39 opyright (c) 199
01a0: 30 20 62 79 20 44 2e 20 52 69 63 68 61 72 64 20 0 by D. Richard
01b0: 48 69 70 70 0a 23 23 0d 0a 0d 0a 6d 79 20 63 6f Hipp.##....my co
01c0: 64 65 20 70 75 62 6c 69 63 2d 73 74 72 75 63 74 de public-struct
01d0: 75 72 65 20 7b 0d 0a 74 79 70 65 64 65 66 20 73 ure {..typedef s
01e0: 74 72 75 63 74 20 54 72 65 65 20 54 72 65 65 3b truct Tree Tree;
01f0: 0d 0a 2f 2a 20 41 20 63 6f 6d 70 6c 65 74 65 20 ../* A complete
0200: 62 69 6e 61 72 79 20 74 72 65 65 20 69 73 20 64 binary tree is d
0210: 65 66 69 6e 65 64 20 62 79 20 61 6e 20 69 6e 73 efined by an ins
0220: 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c tance of the fol
0230: 6c 6f 77 69 6e 67 0d 0a 2a 2a 20 73 74 72 75 63 lowing..** struc
0240: 74 75 72 65 0d 0a 2a 2f 0d 0a 73 74 72 75 63 74 ture..*/..struct
0250: 20 54 72 65 65 20 7b 0d 0a 20 20 69 6e 74 20 28 Tree {.. int (
0260: 2a 78 43 6f 6d 70 61 72 65 29 28 63 6f 6e 73 74 *xCompare)(const
0270: 20 76 6f 69 64 2a 2c 20 63 6f 6e 73 74 20 76 6f void*, const vo
0280: 69 64 2a 29 3b 20 2f 2a 20 43 6f 6d 70 61 72 69 id*); /* Compari
0290: 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0d son function */.
02a0: 0a 20 20 76 6f 69 64 20 2a 28 2a 78 43 6f 70 79 . void *(*xCopy
02b0: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 29 3b 20 )(const void*);
02c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
02d0: 20 4b 65 79 20 63 6f 70 79 20 66 75 6e 63 74 69 Key copy functi
02e0: 6f 6e 2c 20 6f 72 20 4e 55 4c 4c 20 2a 2f 0d 0a on, or NULL */..
02f0: 20 20 76 6f 69 64 20 28 2a 78 46 72 65 65 29 28 void (*xFree)(
0300: 76 6f 69 64 2a 29 3b 20 20 20 20 20 20 20 20 20 void*);
0310: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
0320: 4b 65 79 20 64 65 6c 65 74 65 20 66 75 6e 63 74 Key delete funct
0330: 69 6f 6e 20 2a 2f 0d 0a 20 20 73 74 72 75 63 74 ion */.. struct
0340: 20 54 72 65 65 45 6c 65 6d 20 2a 74 6f 70 3b 20 TreeElem *top;
0350: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0360: 20 20 20 20 20 2f 2a 20 54 68 65 20 74 6f 70 2d /* The top-
0370: 6d 6f 73 74 20 6e 6f 64 65 20 6f 66 20 74 68 65 most node of the
0380: 20 74 72 65 65 20 2a 2f 0d 0a 7d 3b 0d 0a 0a 2f tree */..};.../
0390: 2a 20 45 61 63 68 20 6e 6f 64 65 20 69 6e 20 74 * Each node in t
03a0: 68 65 20 62 69 6e 61 72 79 20 74 72 65 65 20 69 he binary tree i
03b0: 73 20 72 65 70 72 65 73 65 6e 74 65 64 20 62 79 s represented by
03c0: 20 61 20 73 69 6e 67 6c 65 20 69 6e 73 74 61 6e a single instan
03d0: 63 65 0a 2a 2a 20 6f 66 20 74 68 65 20 66 6f 6c ce.** of the fol
03e0: 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 lowing structure
03f0: 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 .*/.typedef stru
0400: 63 74 20 54 72 65 65 45 6c 65 6d 20 54 72 65 65 ct TreeElem Tree
0410: 45 6c 65 6d 3b 0a 73 74 72 75 63 74 20 54 72 65 Elem;.struct Tre
0420: 65 45 6c 65 6d 20 7b 0a 20 20 76 6f 69 64 20 2a eElem {. void *
0430: 64 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 20 data;
0440: 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 /* Pointer to
0450: 74 68 65 20 75 73 65 72 27 73 20 64 61 74 61 20 the user's data
0460: 2a 2f 0a 20 20 76 6f 69 64 20 2a 6b 65 79 3b 20 */. void *key;
0470: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
0480: 54 68 65 20 6b 65 79 20 61 73 73 6f 63 69 61 74 The key associat
0490: 65 64 20 77 69 74 68 20 74 68 69 73 20 65 6c 65 ed with this ele
04a0: 6d 65 6e 74 20 2a 2f 0a 20 20 54 72 65 65 45 6c ment */. TreeEl
04b0: 65 6d 20 2a 6c 65 66 74 3b 20 20 20 20 20 20 20 em *left;
04c0: 20 20 2f 2a 20 4c 65 66 74 20 64 61 75 67 68 74 /* Left daught
04d0: 65 72 20 2a 2f 0a 20 20 54 72 65 65 45 6c 65 6d er */. TreeElem
04e0: 20 2a 72 69 67 68 74 3b 20 20 20 20 20 20 20 20 *right;
04f0: 2f 2a 20 52 69 67 68 74 20 64 61 75 67 68 74 65 /* Right daughte
0500: 72 20 2a 2f 0a 20 20 69 6e 74 20 77 65 69 67 68 r */. int weigh
0510: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f t; /
0520: 2a 20 57 65 69 67 68 74 20 6f 66 20 74 68 69 73 * Weight of this
0530: 20 6e 6f 64 65 20 2a 2f 0a 7d 3b 0a 7d 0d 0a 0d node */.};.}...
0540: 0a 6d 79 20 63 5f 66 75 6e 63 74 69 6f 6e 20 7b .my c_function {
0550: 76 6f 69 64 20 54 72 65 65 49 6e 69 74 28 54 72 void TreeInit(Tr
0560: 65 65 20 2a 74 72 65 65 2c 20 69 6e 74 20 28 2a ee *tree, int (*
0570: 78 43 6f 6d 70 61 72 65 29 28 63 6f 6e 73 74 20 xCompare)(const
0580: 76 6f 69 64 2a 2c 20 63 6f 6e 73 74 20 76 6f 69 void*, const voi
0590: 64 2a 29 2c 76 6f 69 64 20 2a 28 2a 78 43 6f 70 d*),void *(*xCop
05a0: 79 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 29 2c y)(const void*),
05b0: 76 6f 69 64 20 28 2a 78 46 72 65 65 29 28 76 6f void (*xFree)(vo
05c0: 69 64 2a 29 29 7d 20 7b 0a 2f 2a 20 54 75 72 6e id*))} {./* Turn
05d0: 20 62 75 6c 6b 20 6d 65 6d 6f 72 79 20 69 6e 74 bulk memory int
05e0: 6f 20 61 20 54 72 65 65 20 73 74 72 75 63 74 75 o a Tree structu
05f0: 72 65 0d 0a 20 20 54 72 65 65 20 2a 74 72 65 65 re.. Tree *tree
0600: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,
0610: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0620: 20 20 54 72 65 65 20 6f 62 6a 65 63 74 20 74 6f Tree object to
0630: 20 69 6e 69 74 69 61 6c 69 7a 65 0d 0a 20 20 69 initialize.. i
0640: 6e 74 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 63 nt (*xCompare)(c
0650: 6f 6e 73 74 20 76 6f 69 64 2a 2c 20 63 6f 6e 73 onst void*, cons
0660: 74 20 76 6f 69 64 2a 29 2c 20 20 43 6f 6d 70 61 t void*), Compa
0670: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 0d 0a rison function..
0680: 20 20 76 6f 69 64 20 2a 28 2a 78 43 6f 70 79 29 void *(*xCopy)
0690: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 29 2c 20 20 (const void*),
06a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 4b 65 Ke
06b0: 79 20 63 6f 70 79 20 66 75 6e 63 74 69 6f 6e 20 y copy function
06c0: 6f 72 20 4e 55 4c 4c 20 0d 0a 20 20 76 6f 69 64 or NULL .. void
06d0: 20 28 2a 78 46 72 65 65 29 28 76 6f 69 64 2a 29 (*xFree)(void*)
06e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
06f0: 20 20 20 20 20 20 20 20 4b 65 79 20 64 65 6c 65 Key dele
0700: 74 65 20 66 75 6e 63 74 69 6f 6e 20 6f 72 20 4e te function or N
0710: 55 4c 4c 0d 0a 2a 2f 0d 0a 20 20 74 72 65 65 2d ULL..*/.. tree-
0720: 3e 78 43 6f 6d 70 61 72 65 20 3d 20 78 43 6f 6d >xCompare = xCom
0730: 70 61 72 65 3b 0a 20 20 74 72 65 65 2d 3e 78 43 pare;. tree->xC
0740: 6f 70 79 20 3d 20 78 43 6f 70 79 3b 0a 20 20 74 opy = xCopy;. t
0750: 72 65 65 2d 3e 78 46 72 65 65 20 3d 20 78 46 72 ree->xFree = xFr
0760: 65 65 3b 0a 20 20 74 72 65 65 2d 3e 74 6f 70 20 ee;. tree->top
0770: 3d 20 30 3b 0a 7d 0a 0d 0a 6d 79 20 63 5f 66 75 = 0;.}...my c_fu
0780: 6e 63 74 69 6f 6e 20 7b 69 6e 74 20 54 72 65 65 nction {int Tree
0790: 43 6f 75 6e 74 28 54 72 65 65 20 2a 70 54 72 65 Count(Tree *pTre
07a0: 65 29 7d 20 7b 0a 20 20 2f 2a 20 52 65 74 75 72 e)} {. /* Retur
07b0: 6e 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 n the number of
07c0: 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 68 65 20 elements in the
07d0: 74 72 65 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70 tree. */. if( p
07e0: 54 72 65 65 20 26 26 20 70 54 72 65 65 2d 3e 74 Tree && pTree->t
07f0: 6f 70 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e op ){. return
0800: 20 70 54 72 65 65 2d 3e 74 6f 70 2d 3e 77 65 69 pTree->top->wei
0810: 67 68 74 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 ght;. }else{.
0820: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a return 0;. }.
0830: 7d 0d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 }....my c_functi
0840: 6f 6e 20 7b 73 74 61 74 69 63 20 76 6f 69 64 20 on {static void
0850: 54 72 65 65 43 6c 65 61 72 4e 6f 64 65 28 54 72 TreeClearNode(Tr
0860: 65 65 45 6c 65 6d 20 2a 70 2c 20 76 6f 69 64 20 eeElem *p, void
0870: 28 2a 78 46 72 65 65 29 28 76 6f 69 64 2a 29 29 (*xFree)(void*))
0880: 7d 20 7b 0a 20 20 2f 2a 20 44 65 6c 65 74 65 20 } {. /* Delete
0890: 61 20 73 69 6e 67 6c 65 20 6e 6f 64 65 20 6f 66 a single node of
08a0: 20 74 68 65 20 62 69 6e 61 72 79 20 74 72 65 65 the binary tree
08b0: 20 61 6e 64 20 61 6c 6c 20 6f 66 20 69 74 73 20 and all of its
08c0: 63 68 69 6c 64 72 65 6e 20 2a 2f 0a 20 20 69 66 children */. if
08d0: 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b ( p==0 ) return;
08e0: 0a 20 20 69 66 28 20 70 2d 3e 6c 65 66 74 20 29 . if( p->left )
08f0: 20 54 72 65 65 43 6c 65 61 72 4e 6f 64 65 28 70 TreeClearNode(p
0900: 2d 3e 6c 65 66 74 2c 20 78 46 72 65 65 29 3b 0a ->left, xFree);.
0910: 20 20 69 66 28 20 70 2d 3e 72 69 67 68 74 20 29 if( p->right )
0920: 20 54 72 65 65 43 6c 65 61 72 4e 6f 64 65 28 70 TreeClearNode(p
0930: 2d 3e 72 69 67 68 74 2c 20 78 46 72 65 65 29 3b ->right, xFree);
0940: 0a 20 20 69 66 28 20 78 46 72 65 65 20 29 7b 0a . if( xFree ){.
0950: 20 20 20 20 78 46 72 65 65 28 70 2d 3e 6b 65 79 xFree(p->key
0960: 29 3b 0a 20 20 7d 0a 20 20 54 63 6c 5f 46 72 65 );. }. Tcl_Fre
0970: 65 28 28 63 68 61 72 20 2a 29 70 29 3b 0a 7d 0d e((char *)p);.}.
0980: 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 6f 6e ...my c_function
0990: 20 7b 76 6f 69 64 20 54 72 65 65 43 6c 65 61 72 {void TreeClear
09a0: 28 54 72 65 65 20 2a 74 72 65 65 29 7d 20 7b 0a (Tree *tree)} {.
09b0: 20 20 2f 2a 20 52 65 6d 6f 76 65 20 61 6c 6c 20 /* Remove all
09c0: 6e 6f 64 65 73 20 66 72 6f 6d 20 61 20 74 72 65 nodes from a tre
09d0: 65 20 2a 2f 0a 20 20 69 66 28 20 74 72 65 65 2d e */. if( tree-
09e0: 3e 74 6f 70 20 29 7b 0a 20 20 20 20 54 72 65 65 >top ){. Tree
09f0: 43 6c 65 61 72 4e 6f 64 65 28 74 72 65 65 2d 3e ClearNode(tree->
0a00: 74 6f 70 2c 20 74 72 65 65 2d 3e 78 46 72 65 65 top, tree->xFree
0a10: 29 3b 0a 20 20 7d 0a 20 20 74 72 65 65 2d 3e 74 );. }. tree->t
0a20: 6f 70 20 3d 20 30 3b 0a 7d 0a 0d 0a 6d 79 20 63 op = 0;.}...my c
0a30: 5f 66 75 6e 63 74 69 6f 6e 20 7b 76 6f 69 64 20 _function {void
0a40: 2a 54 72 65 65 46 69 6e 64 28 54 72 65 65 20 2a *TreeFind(Tree *
0a50: 74 72 65 65 2c 20 63 6f 6e 73 74 20 76 6f 69 64 tree, const void
0a60: 20 2a 6b 65 79 29 7d 20 7b 0d 0a 2f 2a 20 46 69 *key)} {../* Fi
0a70: 6e 64 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6f nd the element o
0a80: 66 20 74 68 65 20 74 72 65 65 20 28 69 66 20 61 f the tree (if a
0a90: 6e 79 29 20 77 68 6f 73 65 20 6b 65 79 20 6d 61 ny) whose key ma
0aa0: 74 63 68 65 73 20 22 6b 65 79 22 2e 0d 0a 2a 2a tches "key"...**
0ab0: 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 Return a pointe
0ac0: 72 20 74 6f 20 74 68 65 20 64 61 74 61 20 66 6f r to the data fo
0ad0: 72 20 74 68 61 74 20 65 6c 65 6d 65 6e 74 2e 20 r that element.
0ae0: 20 49 66 20 6e 6f 20 6d 61 74 63 68 0d 0a 2a 2a If no match..**
0af0: 20 69 73 20 66 6f 75 6e 64 2c 20 72 65 74 75 72 is found, retur
0b00: 6e 20 4e 55 4c 4c 2e 0d 0a 2a 2f 0a 20 20 54 72 n NULL...*/. Tr
0b10: 65 65 45 6c 65 6d 20 2a 70 3b 0a 0a 20 20 70 20 eeElem *p;.. p
0b20: 3d 20 74 72 65 65 2d 3e 74 6f 70 3b 0a 20 20 77 = tree->top;. w
0b30: 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 69 hile( p ){. i
0b40: 6e 74 20 63 20 3d 20 74 72 65 65 2d 3e 78 43 6f nt c = tree->xCo
0b50: 6d 70 61 72 65 28 70 2d 3e 6b 65 79 2c 20 6b 65 mpare(p->key, ke
0b60: 79 29 3b 0a 20 20 20 20 69 66 28 20 63 3d 3d 30 y);. if( c==0
0b70: 20 29 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e ){. return
0b80: 20 70 2d 3e 64 61 74 61 3b 0a 20 20 20 20 7d 65 p->data;. }e
0b90: 6c 73 65 20 69 66 28 20 63 3c 30 20 29 7b 0a 20 lse if( c<0 ){.
0ba0: 20 20 20 20 20 70 20 3d 20 70 2d 3e 72 69 67 68 p = p->righ
0bb0: 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 t;. }else{.
0bc0: 20 20 20 20 70 20 3d 20 70 2d 3e 6c 65 66 74 3b p = p->left;
0bd0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 . }. }. ret
0be0: 75 72 6e 20 30 3b 0a 7d 0a 0d 0a 6d 79 20 63 5f urn 0;.}...my c_
0bf0: 66 75 6e 63 74 69 6f 6e 20 7b 69 6e 74 20 54 72 function {int Tr
0c00: 65 65 52 61 6e 6b 28 54 72 65 65 20 2a 74 72 65 eeRank(Tree *tre
0c10: 65 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 6b e, const void *k
0c20: 65 79 29 7d 20 7b 0a 20 20 2f 2a 20 49 66 20 74 ey)} {. /* If t
0c30: 68 65 20 6e 6f 64 65 20 77 69 74 68 20 6b 65 79 he node with key
0c40: 20 22 6b 65 79 22 20 69 73 20 74 68 65 20 6c 65 "key" is the le
0c50: 66 74 2d 6d 6f 73 74 20 65 6c 65 6d 65 6e 74 20 ft-most element
0c60: 6f 66 20 74 68 65 20 74 72 65 65 2c 20 0a 20 20 of the tree, .
0c70: 2a 2a 20 72 65 74 75 72 6e 20 30 2e 20 20 49 66 ** return 0. If
0c80: 20 69 74 20 69 73 20 74 68 65 20 73 65 63 6f 6e it is the secon
0c90: 64 20 74 6f 20 74 68 65 20 6c 65 66 74 2c 20 72 d to the left, r
0ca0: 65 74 75 72 6e 20 31 2e 20 20 41 6e 64 20 73 6f eturn 1. And so
0cb0: 0a 20 20 2a 2a 20 66 6f 72 74 68 2e 0a 20 20 2a . ** forth.. *
0cc0: 2a 0a 20 20 2a 2a 20 49 66 20 74 68 65 72 65 20 *. ** If there
0cd0: 69 73 20 6e 6f 20 6e 6f 64 65 20 69 6e 20 74 68 is no node in th
0ce0: 65 20 74 72 65 65 20 77 69 74 68 20 74 68 65 20 e tree with the
0cf0: 6b 65 79 20 22 6b 65 79 22 2c 20 74 68 65 6e 20 key "key", then
0d00: 72 65 74 75 72 6e 0a 20 20 2a 2a 20 74 68 65 20 return. ** the
0d10: 6e 75 6d 62 65 72 20 74 68 61 74 20 77 6f 75 6c number that woul
0d20: 64 20 68 61 76 65 20 62 65 65 6e 20 72 65 74 75 d have been retu
0d30: 72 6e 65 64 20 69 66 20 73 75 63 68 20 61 20 6e rned if such a n
0d40: 6f 64 65 20 77 65 72 65 0a 20 20 2a 2a 20 69 6e ode were. ** in
0d50: 73 65 72 74 65 64 2e 0a 20 20 2a 2f 0a 20 20 54 serted.. */. T
0d60: 72 65 65 45 6c 65 6d 20 2a 70 3b 0a 20 20 69 6e reeElem *p;. in
0d70: 74 20 72 61 6e 6b 20 3d 20 30 3b 0a 0a 20 20 70 t rank = 0;.. p
0d80: 20 3d 20 74 72 65 65 2d 3e 74 6f 70 3b 0a 20 20 = tree->top;.
0d90: 77 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 while( p ){.
0da0: 69 6e 74 20 63 20 3d 20 74 72 65 65 2d 3e 78 43 int c = tree->xC
0db0: 6f 6d 70 61 72 65 28 70 2d 3e 6b 65 79 2c 20 6b ompare(p->key, k
0dc0: 65 79 29 3b 0a 20 20 20 20 69 66 28 20 63 3d 3d ey);. if( c==
0dd0: 30 20 29 7b 0a 20 20 20 20 20 20 72 61 6e 6b 20 0 ){. rank
0de0: 2b 3d 20 70 2d 3e 6c 65 66 74 20 3f 20 70 2d 3e += p->left ? p->
0df0: 6c 65 66 74 2d 3e 77 65 69 67 68 74 3a 20 30 3b left->weight: 0;
0e00: 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 . break;.
0e10: 20 20 7d 65 6c 73 65 20 69 66 28 20 63 3c 30 20 }else if( c<0
0e20: 29 7b 0a 20 20 20 20 20 20 72 61 6e 6b 20 2b 3d ){. rank +=
0e30: 20 28 70 2d 3e 6c 65 66 74 20 3f 20 70 2d 3e 6c (p->left ? p->l
0e40: 65 66 74 2d 3e 77 65 69 67 68 74 3a 20 30 29 20 eft->weight: 0)
0e50: 2b 20 31 3b 0a 20 20 20 20 20 20 70 20 3d 20 70 + 1;. p = p
0e60: 2d 3e 72 69 67 68 74 3b 0a 20 20 20 20 7d 65 6c ->right;. }el
0e70: 73 65 7b 0a 20 20 20 20 20 20 70 20 3d 20 70 2d se{. p = p-
0e80: 3e 6c 65 66 74 3b 0a 20 20 20 20 7d 0a 20 20 7d >left;. }. }
0e90: 0a 20 20 72 65 74 75 72 6e 20 72 61 6e 6b 3b 0a . return rank;.
0ea0: 7d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 6f }...my c_functio
0eb0: 6e 20 7b 73 74 61 74 69 63 20 54 72 65 65 45 6c n {static TreeEl
0ec0: 65 6d 20 2a 54 72 65 65 46 69 6e 64 4e 74 68 45 em *TreeFindNthE
0ed0: 6c 65 6d 28 54 72 65 65 20 2a 74 72 65 65 2c 20 lem(Tree *tree,
0ee0: 69 6e 74 20 6e 29 7d 20 7b 0a 20 20 2f 2a 20 52 int n)} {. /* R
0ef0: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 eturn a pointer
0f00: 74 6f 20 74 68 65 20 4e 2d 74 68 20 65 6c 65 6d to the N-th elem
0f10: 65 6e 74 20 6f 66 20 61 20 74 72 65 65 2e 20 20 ent of a tree.
0f20: 28 54 68 65 20 6c 65 66 74 2d 6d 6f 73 74 0a 20 (The left-most.
0f30: 20 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 6e ** element is n
0f40: 75 6d 62 65 72 20 30 2c 20 74 68 65 20 6e 65 78 umber 0, the nex
0f50: 74 20 69 73 20 6e 75 6d 62 65 72 20 31 20 61 6e t is number 1 an
0f60: 64 20 73 6f 20 66 6f 72 74 68 2e 29 0a 20 20 2a d so forth.). *
0f70: 2f 0a 20 20 54 72 65 65 45 6c 65 6d 20 2a 70 3b /. TreeElem *p;
0f80: 0a 0a 20 20 70 20 3d 20 74 72 65 65 2d 3e 74 6f .. p = tree->to
0f90: 70 3b 0a 20 20 77 68 69 6c 65 28 20 70 20 29 7b p;. while( p ){
0fa0: 0a 20 20 20 20 69 6e 74 20 63 20 3d 20 70 2d 3e . int c = p->
0fb0: 6c 65 66 74 20 3f 20 70 2d 3e 6c 65 66 74 2d 3e left ? p->left->
0fc0: 77 65 69 67 68 74 20 3a 20 30 3b 0a 20 20 20 20 weight : 0;.
0fd0: 69 66 28 20 6e 3d 3d 63 20 29 7b 0a 20 20 20 20 if( n==c ){.
0fe0: 20 20 72 65 74 75 72 6e 20 70 3b 0a 20 20 20 20 return p;.
0ff0: 7d 65 6c 73 65 20 69 66 28 20 6e 3e 63 20 29 7b }else if( n>c ){
1000: 0a 20 20 20 20 20 20 6e 20 2d 3d 20 63 2b 31 3b . n -= c+1;
1010: 0a 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 72 69 . p = p->ri
1020: 67 68 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a ght;. }else{.
1030: 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 6c 65 66 p = p->lef
1040: 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 t;. }. }. r
1050: 65 74 75 72 6e 20 30 3b 0a 7d 0a 0d 0a 6d 79 20 eturn 0;.}...my
1060: 63 5f 66 75 6e 63 74 69 6f 6e 20 7b 76 6f 69 64 c_function {void
1070: 20 2a 54 72 65 65 44 61 74 61 28 54 72 65 65 20 *TreeData(Tree
1080: 2a 74 72 65 65 2c 20 69 6e 74 20 6e 29 7d 20 7b *tree, int n)} {
1090: 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65 . /* Return the
10a0: 20 64 61 74 61 20 61 73 73 6f 63 69 61 74 65 64 data associated
10b0: 20 77 69 74 68 20 74 68 65 20 4e 2d 74 68 20 65 with the N-th e
10c0: 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 74 72 lement of the tr
10d0: 65 65 2e 20 20 52 65 74 75 72 6e 0a 20 20 2a 2a ee. Return. **
10e0: 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65 20 69 NULL if there i
10f0: 73 20 6e 6f 20 4e 2d 74 68 20 65 6c 65 6d 65 6e s no N-th elemen
1100: 74 2e 0a 20 20 2a 2f 0a 20 20 54 72 65 65 45 6c t.. */. TreeEl
1110: 65 6d 20 2a 70 20 3d 20 54 72 65 65 46 69 6e 64 em *p = TreeFind
1120: 4e 74 68 45 6c 65 6d 28 74 72 65 65 2c 6e 29 3b NthElem(tree,n);
1130: 0a 20 20 72 65 74 75 72 6e 20 70 20 3f 20 70 2d . return p ? p-
1140: 3e 64 61 74 61 20 3a 20 30 3b 0a 7d 0a 0d 0a 6d >data : 0;.}...m
1150: 79 20 63 5f 66 75 6e 63 74 69 6f 6e 20 7b 63 6f y c_function {co
1160: 6e 73 74 20 76 6f 69 64 20 2a 54 72 65 65 4b 65 nst void *TreeKe
1170: 79 28 54 72 65 65 20 2a 74 72 65 65 2c 20 69 6e y(Tree *tree, in
1180: 74 20 6e 29 7d 20 7b 0a 20 20 2f 2a 20 52 65 74 t n)} {. /* Ret
1190: 75 72 6e 20 74 68 65 20 6b 65 79 20 61 73 73 6f urn the key asso
11a0: 63 69 61 74 65 64 20 77 69 74 68 20 74 68 65 20 ciated with the
11b0: 4e 2d 74 68 20 65 6c 65 6d 65 6e 74 20 6f 66 20 N-th element of
11c0: 74 68 65 20 74 72 65 65 2e 20 20 52 65 74 75 72 the tree. Retur
11d0: 6e 0a 20 20 2a 2a 20 4e 55 4c 4c 20 69 66 20 74 n. ** NULL if t
11e0: 68 65 72 65 20 69 73 20 6e 6f 20 4e 2d 74 68 20 here is no N-th
11f0: 65 6c 65 6d 65 6e 74 2e 0a 20 20 2a 2f 0a 20 20 element.. */.
1200: 54 72 65 65 45 6c 65 6d 20 2a 70 20 3d 20 54 72 TreeElem *p = Tr
1210: 65 65 46 69 6e 64 4e 74 68 45 6c 65 6d 28 74 72 eeFindNthElem(tr
1220: 65 65 2c 6e 29 3b 0a 20 20 69 66 28 20 70 20 29 ee,n);. if( p )
1230: 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 70 2d 3e {. return p->
1240: 6b 65 79 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 key;. }else{.
1250: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a return 0;. }.
1260: 7d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 6f }...my c_functio
1270: 6e 20 7b 73 74 61 74 69 63 20 76 6f 69 64 20 54 n {static void T
1280: 72 65 65 42 61 6c 61 6e 63 65 28 54 72 65 65 45 reeBalance(TreeE
1290: 6c 65 6d 20 2a 2a 70 70 45 6c 65 6d 29 7d 20 7b lem **ppElem)} {
12a0: 0a 20 20 2f 2a 0a 20 20 2a 2a 20 44 65 66 69 6e . /*. ** Defin
12b0: 69 74 69 6f 6e 73 3a 0a 20 20 2a 2a 20 57 45 49 itions:. ** WEI
12c0: 47 48 54 0a 20 20 2a 2a 20 20 20 54 68 65 20 77 GHT. ** The w
12d0: 65 69 67 68 74 20 6f 66 20 61 20 6e 6f 64 65 20 eight of a node
12e0: 69 73 20 74 68 65 20 74 6f 74 61 6c 20 6e 75 6d is the total num
12f0: 62 65 72 20 6f 66 20 63 68 69 6c 64 72 65 6e 20 ber of children
1300: 66 6f 72 20 74 68 65 20 6e 6f 64 65 0a 20 20 2a for the node. *
1310: 2a 20 20 20 70 6c 75 73 20 31 2e 20 20 4c 65 61 * plus 1. Lea
1320: 66 20 6e 6f 64 65 73 20 68 61 76 65 20 61 20 77 f nodes have a w
1330: 65 69 67 68 74 20 6f 66 20 31 2e 20 20 54 68 65 eight of 1. The
1340: 20 72 6f 6f 74 20 6e 6f 64 65 20 68 61 73 20 61 root node has a
1350: 20 77 65 69 67 68 74 0a 20 20 2a 2a 20 20 20 77 weight. ** w
1360: 68 69 63 68 20 65 71 75 61 6c 73 20 74 68 65 20 hich equals the
1370: 6e 75 6d 62 65 72 20 6f 66 20 6e 6f 64 65 73 20 number of nodes
1380: 69 6e 20 74 68 65 20 74 72 65 65 2e 0a 20 20 2a in the tree.. *
1390: 2a 0a 20 20 2a 2a 20 42 41 4c 41 4e 43 45 0a 20 *. ** BALANCE.
13a0: 20 2a 2a 20 20 20 41 20 6e 6f 64 65 20 69 73 20 ** A node is
13b0: 62 61 6c 61 6e 63 65 64 20 69 66 20 74 68 65 20 balanced if the
13c0: 77 65 69 67 68 74 20 6f 66 20 74 68 65 20 6f 6e weight of the on
13d0: 65 20 63 68 69 6c 64 20 69 73 20 6e 6f 74 20 6d e child is not m
13e0: 6f 72 65 20 74 68 61 6e 0a 20 20 2a 2a 20 20 20 ore than. **
13f0: 74 77 69 63 65 20 74 68 65 20 77 65 69 67 68 74 twice the weight
1400: 20 6f 66 20 74 68 65 20 6f 74 68 65 72 20 63 68 of the other ch
1410: 69 6c 64 2e 0a 20 20 2a 2f 0a 0a 20 20 2f 2a 20 ild.. */.. /*
1420: 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 72 6f The following ro
1430: 75 74 69 6e 65 20 72 65 62 61 6c 61 6e 63 65 73 utine rebalances
1440: 20 74 68 65 20 74 72 65 65 20 72 6f 6f 74 65 64 the tree rooted
1450: 20 61 74 20 2a 70 70 45 6c 65 6d 20 61 66 74 65 at *ppElem afte
1460: 72 0a 20 20 2a 2a 20 74 68 65 20 69 6e 73 65 72 r. ** the inser
1470: 74 69 6f 6e 20 6f 72 20 64 65 6c 65 74 69 6f 6e tion or deletion
1480: 20 6f 66 20 61 20 73 69 6e 67 6c 65 20 61 6e 63 of a single anc
1490: 65 73 74 6f 72 2e 0a 20 20 2a 2f 0a 20 20 54 72 estor.. */. Tr
14a0: 65 65 45 6c 65 6d 20 2a 6e 3b 20 20 20 20 20 2f eeElem *n; /
14b0: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 73 65 6c * Pointer to sel
14c0: 66 20 2a 2f 0a 20 20 69 6e 74 20 6c 2c 72 3b 20 f */. int l,r;
14d0: 20 20 20 20 20 20 20 20 2f 2a 20 57 65 69 67 68 /* Weigh
14e0: 74 20 6f 66 20 6c 65 66 74 20 61 6e 64 20 72 69 t of left and ri
14f0: 67 68 74 20 64 61 75 67 68 74 65 72 73 20 2a 2f ght daughters */
1500: 0a 20 20 69 6e 74 20 61 2c 62 3b 20 20 20 20 20 . int a,b;
1510: 20 20 20 20 2f 2a 20 57 65 69 67 68 74 73 20 6f /* Weights o
1520: 66 20 76 61 72 69 6f 75 73 20 6e 6f 64 65 73 20 f various nodes
1530: 2a 2f 0a 0a 20 20 69 66 28 20 70 70 45 6c 65 6d */.. if( ppElem
1540: 3d 3d 30 20 7c 7c 20 28 6e 3d 2a 70 70 45 6c 65 ==0 || (n=*ppEle
1550: 6d 29 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a m)==0 ) return;.
1560: 20 20 6c 20 3d 20 6e 2d 3e 6c 65 66 74 20 3f 20 l = n->left ?
1570: 6e 2d 3e 6c 65 66 74 2d 3e 77 65 69 67 68 74 3a n->left->weight:
1580: 20 30 3b 0a 20 20 72 20 3d 20 6e 2d 3e 72 69 67 0;. r = n->rig
1590: 68 74 20 3f 20 6e 2d 3e 72 69 67 68 74 2d 3e 77 ht ? n->right->w
15a0: 65 69 67 68 74 3a 20 30 3b 0a 20 20 69 66 28 20 eight: 0;. if(
15b0: 6c 3e 72 2a 32 20 29 7b 20 20 20 20 2f 2a 20 54 l>r*2 ){ /* T
15c0: 6f 6f 20 68 65 61 76 79 20 6f 6e 20 74 68 65 20 oo heavy on the
15d0: 6c 65 66 74 20 73 69 64 65 20 2a 2f 0a 20 20 20 left side */.
15e0: 20 54 72 65 65 45 6c 65 6d 20 2a 6e 6c 3b 20 20 TreeElem *nl;
15f0: 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f /* Pointer to
1600: 20 6c 65 66 74 20 64 61 75 67 68 74 65 72 20 2a left daughter *
1610: 2f 0a 20 20 20 20 54 72 65 65 45 6c 65 6d 20 2a /. TreeElem *
1620: 6e 72 3b 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 nr; /* Point
1630: 65 72 20 74 6f 20 72 69 67 68 74 20 64 61 75 67 er to right daug
1640: 68 74 65 72 20 2a 2f 0a 20 20 20 20 69 6e 74 20 hter */. int
1650: 6c 6c 2c 20 6c 72 3b 20 20 20 20 20 20 20 2f 2a ll, lr; /*
1660: 20 57 65 69 67 68 74 20 6f 66 20 6c 65 66 74 20 Weight of left
1670: 64 61 75 67 68 74 65 72 27 73 20 6c 65 66 74 20 daughter's left
1680: 61 6e 64 20 72 69 67 68 74 20 64 61 75 67 68 74 and right daught
1690: 65 72 20 2a 2f 0a 20 20 20 20 6e 6c 20 3d 20 6e er */. nl = n
16a0: 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 6c 6c 20 3d ->left;. ll =
16b0: 20 6e 6c 2d 3e 6c 65 66 74 20 3f 20 6e 6c 2d 3e nl->left ? nl->
16c0: 6c 65 66 74 2d 3e 77 65 69 67 68 74 3a 20 30 3b left->weight: 0;
16d0: 0a 20 20 20 20 6c 72 20 3d 20 6e 6c 2d 3e 72 69 . lr = nl->ri
16e0: 67 68 74 20 3f 20 6e 6c 2d 3e 72 69 67 68 74 2d ght ? nl->right-
16f0: 3e 77 65 69 67 68 74 3a 20 30 3b 0a 20 20 20 20 >weight: 0;.
1700: 69 66 28 20 6c 6c 3e 6c 72 20 7c 7c 20 6e 6c 2d if( ll>lr || nl-
1710: 3e 72 69 67 68 74 3d 3d 30 20 29 7b 0a 20 20 20 >right==0 ){.
1720: 20 20 20 2f 2a 0a 20 20 20 20 20 20 2a 2a 20 43 /*. ** C
1730: 6f 6e 76 65 72 74 20 66 72 6f 6d 3a 20 20 6e 20 onvert from: n
1740: 20 20 20 20 74 6f 3a 20 20 6e 6c 0a 20 20 20 20 to: nl.
1750: 20 20 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 **
1760: 20 20 20 2f 20 5c 20 20 20 20 20 20 20 20 2f 20 / \ /
1770: 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 20 \. **
1780: 20 20 20 20 20 20 20 20 20 6e 6c 20 20 63 20 20 nl c
1790: 20 20 20 20 61 20 20 20 20 6e 0a 20 20 20 20 20 a n.
17a0: 20 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 **
17b0: 2f 20 20 5c 20 20 20 20 20 20 20 20 20 20 20 20 / \
17c0: 2f 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 / \. **
17d0: 20 20 20 20 20 20 20 20 61 20 20 20 20 62 20 20 a b
17e0: 20 20 20 20 20 20 20 20 62 20 20 20 63 0a 20 20 b c.
17f0: 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 6e 2d 3e */. n->
1800: 6c 65 66 74 20 3d 20 6e 6c 2d 3e 72 69 67 68 74 left = nl->right
1810: 3b 0a 20 20 20 20 20 20 6e 6c 2d 3e 72 69 67 68 ;. nl->righ
1820: 74 20 3d 20 6e 3b 0a 20 20 20 20 20 20 6e 2d 3e t = n;. n->
1830: 77 65 69 67 68 74 20 3d 20 61 20 3d 20 72 20 2b weight = a = r +
1840: 20 6c 72 20 2b 20 31 3b 0a 20 20 20 20 20 20 6e lr + 1;. n
1850: 6c 2d 3e 77 65 69 67 68 74 20 3d 20 61 20 2b 20 l->weight = a +
1860: 6c 6c 20 2b 20 31 3b 0a 20 20 20 20 20 20 2a 70 ll + 1;. *p
1870: 70 45 6c 65 6d 20 3d 20 6e 6c 3b 0a 20 20 20 20 pElem = nl;.
1880: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 2f 2a 0a }else{. /*.
1890: 20 20 20 20 20 20 2a 2a 20 43 6f 6e 76 65 72 74 ** Convert
18a0: 20 66 72 6f 6d 3a 20 20 6e 20 20 20 20 20 20 20 from: n
18b0: 20 74 6f 3a 20 20 6e 72 0a 20 20 20 20 20 20 2a to: nr. *
18c0: 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 *
18d0: 2f 20 5c 20 20 20 20 20 20 20 20 20 20 20 2f 20 / \ /
18e0: 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 20 \. **
18f0: 20 20 20 20 20 20 20 20 6e 6c 20 20 20 64 20 20 nl d
1900: 20 20 20 20 20 20 6e 6c 20 20 20 20 6e 0a 20 20 nl n.
1910: 20 20 20 20 2a 2a 20 20 20 20 20 20 20 20 20 20 **
1920: 20 20 2f 20 20 5c 20 20 20 20 20 20 20 20 20 20 / \
1930: 2f 20 5c 20 20 20 2f 20 5c 0a 20 20 20 20 20 20 / \ / \.
1940: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 61 20 20 ** a
1950: 20 20 6e 72 20 20 20 20 20 20 20 61 20 20 20 62 nr a b
1960: 20 63 20 20 20 64 0a 20 20 20 20 20 20 2a 2a 20 c d. **
1970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 20 /
1980: 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 20 \. **
1990: 20 20 20 20 20 20 20 20 20 62 20 20 20 20 63 0a b c.
19a0: 20 20 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 69 */. i
19b0: 6e 74 20 6c 72 6c 2c 20 6c 72 72 3b 20 20 20 20 nt lrl, lrr;
19c0: 2f 2a 20 57 65 69 67 68 74 20 6f 66 20 47 72 65 /* Weight of Gre
19d0: 61 74 2d 67 72 61 6e 64 64 61 75 67 68 74 65 72 at-granddaughter
19e0: 20 6e 6f 64 65 73 20 2a 2f 0a 20 20 20 20 20 20 nodes */.
19f0: 6e 72 20 3d 20 6e 6c 2d 3e 72 69 67 68 74 3b 0a nr = nl->right;.
1a00: 20 20 20 20 20 20 6c 72 6c 20 3d 20 6e 72 2d 3e lrl = nr->
1a10: 6c 65 66 74 20 3f 20 6e 72 2d 3e 6c 65 66 74 2d left ? nr->left-
1a20: 3e 77 65 69 67 68 74 3a 20 30 3b 0a 20 20 20 20 >weight: 0;.
1a30: 20 20 6c 72 72 20 3d 20 6e 72 2d 3e 72 69 67 68 lrr = nr->righ
1a40: 74 20 3f 20 6e 72 2d 3e 72 69 67 68 74 2d 3e 77 t ? nr->right->w
1a50: 65 69 67 68 74 3a 20 30 3b 0a 20 20 20 20 20 20 eight: 0;.
1a60: 6e 6c 2d 3e 72 69 67 68 74 20 3d 20 6e 72 2d 3e nl->right = nr->
1a70: 6c 65 66 74 3b 0a 20 20 20 20 20 20 6e 72 2d 3e left;. nr->
1a80: 6c 65 66 74 20 3d 20 6e 6c 3b 0a 20 20 20 20 20 left = nl;.
1a90: 20 6e 2d 3e 6c 65 66 74 20 3d 20 6e 72 2d 3e 72 n->left = nr->r
1aa0: 69 67 68 74 3b 0a 20 20 20 20 20 20 6e 72 2d 3e ight;. nr->
1ab0: 72 69 67 68 74 20 3d 20 6e 3b 0a 20 20 20 20 20 right = n;.
1ac0: 20 6e 2d 3e 77 65 69 67 68 74 20 3d 20 61 20 3d n->weight = a =
1ad0: 20 6c 72 72 20 2b 20 72 20 2b 20 31 3b 0a 20 20 lrr + r + 1;.
1ae0: 20 20 20 20 6e 6c 2d 3e 77 65 69 67 68 74 20 3d nl->weight =
1af0: 20 62 20 3d 20 6c 6c 20 2b 20 6c 72 6c 20 2b 20 b = ll + lrl +
1b00: 31 3b 0a 20 20 20 20 20 20 6e 72 2d 3e 77 65 69 1;. nr->wei
1b10: 67 68 74 20 3d 20 61 20 2b 20 62 20 2b 20 31 3b ght = a + b + 1;
1b20: 0a 20 20 20 20 20 20 2a 70 70 45 6c 65 6d 20 3d . *ppElem =
1b30: 20 6e 72 3b 0a 20 20 20 20 7d 0a 20 20 7d 65 6c nr;. }. }el
1b40: 73 65 20 69 66 28 20 72 3e 6c 2a 32 20 29 7b 2f se if( r>l*2 ){/
1b50: 2a 20 54 6f 6f 20 64 65 65 70 20 6f 6e 20 74 68 * Too deep on th
1b60: 65 20 72 69 67 68 74 20 73 69 64 65 20 2a 2f 0a e right side */.
1b70: 20 20 20 20 54 72 65 65 45 6c 65 6d 20 2a 6e 6c TreeElem *nl
1b80: 3b 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 ; /* Pointer
1b90: 20 74 6f 20 6c 65 66 74 20 64 61 75 67 68 74 65 to left daughte
1ba0: 72 20 2a 2f 0a 20 20 20 20 54 72 65 65 45 6c 65 r */. TreeEle
1bb0: 6d 20 2a 6e 72 3b 20 20 20 20 20 2f 2a 20 50 6f m *nr; /* Po
1bc0: 69 6e 74 65 72 20 74 6f 20 72 69 67 68 74 20 64 inter to right d
1bd0: 61 75 67 68 74 65 72 20 2a 2f 0a 20 20 20 20 69 aughter */. i
1be0: 6e 74 20 72 6c 2c 20 72 72 3b 20 20 20 20 20 20 nt rl, rr;
1bf0: 20 2f 2a 20 57 65 69 67 68 74 20 6f 66 20 72 69 /* Weight of ri
1c00: 67 68 74 20 64 61 75 67 68 74 65 72 27 73 20 6c ght daughter's l
1c10: 65 66 74 20 61 6e 64 20 72 69 67 68 74 20 64 61 eft and right da
1c20: 75 67 68 74 65 72 20 2a 2f 0a 20 20 20 20 6e 72 ughter */. nr
1c30: 20 3d 20 6e 2d 3e 72 69 67 68 74 3b 0a 20 20 20 = n->right;.
1c40: 20 72 6c 20 3d 20 6e 72 2d 3e 6c 65 66 74 20 3f rl = nr->left ?
1c50: 20 6e 72 2d 3e 6c 65 66 74 2d 3e 77 65 69 67 68 nr->left->weigh
1c60: 74 3a 20 30 3b 0a 20 20 20 20 72 72 20 3d 20 6e t: 0;. rr = n
1c70: 72 2d 3e 72 69 67 68 74 20 3f 20 6e 72 2d 3e 72 r->right ? nr->r
1c80: 69 67 68 74 2d 3e 77 65 69 67 68 74 3a 20 30 3b ight->weight: 0;
1c90: 0a 20 20 20 20 69 66 28 20 72 72 3e 72 6c 20 7c . if( rr>rl |
1ca0: 7c 20 6e 72 2d 3e 6c 65 66 74 3d 3d 30 20 29 7b | nr->left==0 ){
1cb0: 0a 20 20 20 20 20 20 2f 2a 0a 20 20 20 20 20 20 . /*.
1cc0: 2a 2a 20 43 6f 6e 76 65 72 74 20 66 72 6f 6d 3a ** Convert from:
1cd0: 20 20 6e 20 20 20 20 20 20 20 20 20 74 6f 3a 20 n to:
1ce0: 20 6e 72 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 nr. **
1cf0: 20 20 20 20 20 20 20 20 20 20 20 2f 20 5c 20 20 / \
1d00: 20 20 20 20 20 20 20 20 20 20 2f 20 20 5c 0a 20 / \.
1d10: 20 20 20 20 20 2a 2a 20 20 20 20 20 20 20 20 20 **
1d20: 20 20 20 20 20 61 20 20 20 6e 72 20 20 20 20 20 a nr
1d30: 20 20 20 20 6e 20 20 20 20 63 20 0a 20 20 20 20 n c .
1d40: 20 20 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 **
1d50: 20 20 20 20 20 2f 20 20 5c 20 20 20 20 20 20 20 / \
1d60: 2f 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 / \. **
1d70: 20 20 20 20 20 20 20 20 20 20 20 20 62 20 20 20 b
1d80: 20 63 20 20 20 20 20 61 20 20 20 62 0a 20 20 20 c a b.
1d90: 20 20 20 2a 2f 0a 20 20 20 20 20 20 6e 2d 3e 72 */. n->r
1da0: 69 67 68 74 20 3d 20 6e 72 2d 3e 6c 65 66 74 3b ight = nr->left;
1db0: 0a 20 20 20 20 20 20 6e 72 2d 3e 6c 65 66 74 20 . nr->left
1dc0: 3d 20 6e 3b 0a 20 20 20 20 20 20 6e 2d 3e 77 65 = n;. n->we
1dd0: 69 67 68 74 20 3d 20 61 20 3d 20 6c 20 2b 20 72 ight = a = l + r
1de0: 6c 20 2b 20 31 3b 0a 20 20 20 20 20 20 6e 72 2d l + 1;. nr-
1df0: 3e 77 65 69 67 68 74 20 3d 20 61 20 2b 20 72 72 >weight = a + rr
1e00: 20 2b 20 31 3b 0a 20 20 20 20 20 20 2a 70 70 45 + 1;. *ppE
1e10: 6c 65 6d 20 3d 20 6e 72 3b 0a 20 20 20 20 7d 65 lem = nr;. }e
1e20: 6c 73 65 7b 0a 20 20 20 20 20 20 2f 2a 0a 20 20 lse{. /*.
1e30: 20 20 20 20 2a 2a 20 43 6f 6e 76 65 72 74 20 66 ** Convert f
1e40: 72 6f 6d 3a 20 20 6e 20 20 20 20 20 20 20 20 20 rom: n
1e50: 74 6f 3a 20 20 6e 6c 0a 20 20 20 20 20 20 2a 2a to: nl. **
1e60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
1e70: 20 5c 20 20 20 20 20 20 20 20 20 20 20 20 2f 20 \ /
1e80: 20 5c 0a 20 20 20 20 20 20 2a 2a 20 20 20 20 20 \. **
1e90: 20 20 20 20 20 20 20 20 20 61 20 20 20 6e 72 20 a nr
1ea0: 20 20 20 20 20 20 20 20 6e 20 20 20 20 6e 72 0a n nr.
1eb0: 20 20 20 20 20 20 2a 2a 20 20 20 20 20 20 20 20 **
1ec0: 20 20 20 20 20 20 20 20 20 2f 20 20 5c 20 20 20 / \
1ed0: 20 20 20 20 2f 20 5c 20 20 20 2f 20 5c 0a 20 20 / \ / \.
1ee0: 20 20 20 20 2a 2a 20 20 20 20 20 20 20 20 20 20 **
1ef0: 20 20 20 20 20 6e 6c 20 20 20 20 64 20 20 20 20 nl d
1f00: 20 61 20 20 20 62 20 63 20 20 20 64 0a 20 20 20 a b c d.
1f10: 20 20 20 2a 2a 20 20 20 20 20 20 20 20 20 20 20 **
1f20: 20 20 20 2f 20 20 5c 0a 20 20 20 20 20 20 2a 2a / \. **
1f30: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 20 20 b
1f40: 20 20 63 0a 20 20 20 20 20 20 2a 2f 0a 20 20 20 c. */.
1f50: 20 20 20 69 6e 74 20 72 6c 6c 2c 72 6c 72 3b 20 int rll,rlr;
1f60: 20 20 20 2f 2a 20 57 65 69 67 68 74 73 20 6f 66 /* Weights of
1f70: 20 67 72 65 61 74 2d 67 72 61 6e 64 64 61 75 67 great-granddaug
1f80: 68 74 65 72 20 6e 6f 64 65 73 20 2a 2f 0a 20 20 hter nodes */.
1f90: 20 20 20 20 6e 6c 20 3d 20 6e 72 2d 3e 6c 65 66 nl = nr->lef
1fa0: 74 3b 0a 20 20 20 20 20 20 72 6c 6c 20 3d 20 6e t;. rll = n
1fb0: 6c 2d 3e 6c 65 66 74 20 3f 20 6e 6c 2d 3e 6c 65 l->left ? nl->le
1fc0: 66 74 2d 3e 77 65 69 67 68 74 3a 20 30 3b 0a 20 ft->weight: 0;.
1fd0: 20 20 20 20 20 72 6c 72 20 3d 20 6e 6c 2d 3e 72 rlr = nl->r
1fe0: 69 67 68 74 20 3f 20 6e 6c 2d 3e 72 69 67 68 74 ight ? nl->right
1ff0: 2d 3e 77 65 69 67 68 74 3a 20 30 3b 0a 20 20 20 ->weight: 0;.
2000: 20 20 20 6e 72 2d 3e 6c 65 66 74 20 3d 20 6e 6c nr->left = nl
2010: 2d 3e 72 69 67 68 74 3b 0a 20 20 20 20 20 20 6e ->right;. n
2020: 6c 2d 3e 72 69 67 68 74 20 3d 20 6e 72 3b 0a 20 l->right = nr;.
2030: 20 20 20 20 20 6e 2d 3e 72 69 67 68 74 20 3d 20 n->right =
2040: 6e 6c 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 20 20 nl->left;.
2050: 6e 6c 2d 3e 6c 65 66 74 20 3d 20 6e 3b 0a 20 20 nl->left = n;.
2060: 20 20 20 20 6e 2d 3e 77 65 69 67 68 74 20 3d 20 n->weight =
2070: 61 20 3d 20 6c 20 2b 20 72 6c 6c 20 2b 20 31 3b a = l + rll + 1;
2080: 0a 20 20 20 20 20 20 6e 72 2d 3e 77 65 69 67 68 . nr->weigh
2090: 74 20 3d 20 62 20 3d 20 72 72 20 2b 20 72 6c 72 t = b = rr + rlr
20a0: 20 2b 20 31 3b 0a 20 20 20 20 20 20 6e 6c 2d 3e + 1;. nl->
20b0: 77 65 69 67 68 74 20 3d 20 61 20 2b 20 62 20 2b weight = a + b +
20c0: 20 31 3b 0a 20 20 20 20 20 20 2a 70 70 45 6c 65 1;. *ppEle
20d0: 6d 20 3d 20 6e 6c 3b 0a 20 20 20 20 7d 0a 20 20 m = nl;. }.
20e0: 7d 65 6c 73 65 7b 20 2f 2a 20 4e 6f 64 65 20 69 }else{ /* Node i
20f0: 73 20 61 6c 72 65 61 64 79 20 62 61 6c 61 6e 63 s already balanc
2100: 65 64 2e 20 20 4a 75 73 74 20 72 65 63 6f 6d 70 ed. Just recomp
2110: 75 74 65 20 69 74 73 20 77 65 69 67 68 74 2e 20 ute its weight.
2120: 2a 2f 0a 20 20 20 20 6e 2d 3e 77 65 69 67 68 74 */. n->weight
2130: 20 3d 20 6c 20 2b 20 72 20 2b 20 31 3b 0a 20 20 = l + r + 1;.
2140: 7d 0a 7d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 }.}...my c_funct
2150: 69 6f 6e 20 7b 73 74 61 74 69 63 20 76 6f 69 64 ion {static void
2160: 20 2a 54 72 65 65 49 6e 73 65 72 74 45 6c 65 6d *TreeInsertElem
2170: 65 6e 74 28 54 72 65 65 20 2a 70 54 72 65 65 2c ent(Tree *pTree,
2180: 20 76 6f 69 64 20 2a 6b 65 79 2c 20 76 6f 69 64 void *key, void
2190: 20 2a 64 61 74 61 29 7d 20 7b 0a 20 20 2f 2a 0d *data)} {. /*.
21a0: 0a 20 20 54 72 65 65 20 2a 70 54 72 65 65 2c 20 . Tree *pTree,
21b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 54 68 65 The
21c0: 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 74 72 65 root of the tre
21d0: 65 0d 0a 20 20 76 6f 69 64 20 2a 6b 65 79 2c 20 e.. void *key,
21e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 49 I
21f0: 6e 73 65 72 74 20 64 61 74 61 20 61 74 20 74 68 nsert data at th
2200: 69 73 20 6b 65 79 0d 0a 20 20 76 6f 69 64 20 2a is key.. void *
2210: 64 61 74 61 20 20 20 20 20 20 20 20 20 20 20 20 data
2220: 20 20 20 20 44 61 74 61 20 74 6f 20 62 65 20 69 Data to be i
2230: 6e 73 65 72 74 65 64 0d 0a 20 20 2a 2f 0d 0a 20 nserted.. */..
2240: 20 2f 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65 /* This routine
2250: 20 65 69 74 68 65 72 20 63 68 61 6e 67 65 73 20 either changes
2260: 74 68 65 20 64 61 74 61 20 6f 6e 20 61 6e 20 65 the data on an e
2270: 78 69 73 74 69 6e 67 20 6e 6f 64 65 20 69 6e 20 xisting node in
2280: 74 68 65 20 74 72 65 65 2c 0a 20 20 2a 2a 20 6f the tree,. ** o
2290: 72 20 69 6e 73 65 72 74 73 20 61 20 6e 65 77 20 r inserts a new
22a0: 6e 6f 64 65 2e 20 20 22 6b 65 79 22 20 69 64 65 node. "key" ide
22b0: 6e 74 69 66 69 65 73 20 74 68 65 20 6e 6f 64 65 ntifies the node
22c0: 2e 20 20 49 66 20 74 68 65 20 64 61 74 61 20 6f . If the data o
22d0: 6e 0a 20 20 2a 2a 20 61 6e 20 65 78 69 73 74 69 n. ** an existi
22e0: 6e 67 20 6e 6f 64 65 20 69 73 20 63 68 61 6e 67 ng node is chang
22f0: 65 64 2c 20 74 68 65 6e 20 74 68 65 20 66 75 6e ed, then the fun
2300: 63 74 69 6f 6e 20 72 65 74 75 72 6e 73 20 74 68 ction returns th
2310: 65 20 6f 6c 64 20 64 61 74 61 2e 0a 20 20 2a 2a e old data.. **
2320: 20 49 66 20 61 20 6e 65 77 20 6e 6f 64 65 20 69 If a new node i
2330: 73 20 63 72 65 61 74 65 64 2c 20 4e 55 4c 4c 20 s created, NULL
2340: 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 20 20 2a is returned.. *
2350: 2f 0a 20 20 54 72 65 65 45 6c 65 6d 20 2a 6e 3b /. TreeElem *n;
2360: 0a 20 20 76 6f 69 64 20 2a 6f 6c 64 20 3d 20 30 . void *old = 0
2370: 3b 0a 20 20 54 72 65 65 45 6c 65 6d 20 2a 2a 68 ;. TreeElem **h
2380: 5b 31 30 30 5d 3b 20 20 2f 2a 20 53 75 66 66 69 [100]; /* Suffi
2390: 63 69 65 6e 74 20 66 6f 72 20 61 20 74 72 65 65 cient for a tree
23a0: 20 77 69 74 68 20 75 70 20 74 6f 20 34 2e 30 45 with up to 4.0E
23b0: 2b 31 37 20 6e 6f 64 65 73 20 2a 2f 0a 20 20 69 +17 nodes */. i
23c0: 6e 74 20 6c 65 76 65 6c 20 3d 20 30 3b 0a 0a 0a nt level = 0;...
23d0: 20 20 68 5b 30 5d 20 3d 20 26 70 54 72 65 65 2d h[0] = &pTree-
23e0: 3e 74 6f 70 3b 0a 20 20 6c 65 76 65 6c 20 3d 20 >top;. level =
23f0: 31 3b 0a 20 20 6e 20 3d 20 70 54 72 65 65 2d 3e 1;. n = pTree->
2400: 74 6f 70 3b 0a 20 20 77 68 69 6c 65 28 20 6e 20 top;. while( n
2410: 29 7b 0a 20 20 20 20 69 6e 74 20 63 3b 0a 20 20 ){. int c;.
2420: 20 20 63 20 3d 20 70 54 72 65 65 2d 3e 78 43 6f c = pTree->xCo
2430: 6d 70 61 72 65 28 6b 65 79 2c 20 6e 2d 3e 6b 65 mpare(key, n->ke
2440: 79 29 3b 0a 20 20 20 20 69 66 28 20 63 3c 30 20 y);. if( c<0
2450: 29 7b 0a 20 20 20 20 20 20 68 5b 6c 65 76 65 6c ){. h[level
2460: 2b 2b 5d 20 3d 20 26 28 6e 2d 3e 6c 65 66 74 29 ++] = &(n->left)
2470: 3b 0a 20 20 20 20 20 20 6e 20 3d 20 6e 2d 3e 6c ;. n = n->l
2480: 65 66 74 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 eft;. }else i
2490: 66 28 20 63 3e 30 20 29 7b 0a 20 20 20 20 20 20 f( c>0 ){.
24a0: 68 5b 6c 65 76 65 6c 2b 2b 5d 20 3d 20 26 28 6e h[level++] = &(n
24b0: 2d 3e 72 69 67 68 74 29 3b 0a 20 20 20 20 20 20 ->right);.
24c0: 6e 20 3d 20 6e 2d 3e 72 69 67 68 74 3b 0a 20 20 n = n->right;.
24d0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6f }else{. o
24e0: 6c 64 20 3d 20 6e 2d 3e 64 61 74 61 3b 0a 20 20 ld = n->data;.
24f0: 20 20 20 20 6e 2d 3e 64 61 74 61 20 3d 20 64 61 n->data = da
2500: 74 61 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 ta;
2510: 20 20 20 2f 2a 20 52 65 70 6c 61 63 65 20 64 61 /* Replace da
2520: 74 61 20 69 6e 20 61 6e 20 65 78 69 73 74 69 6e ta in an existin
2530: 67 20 6e 6f 64 65 20 2a 2f 0a 20 20 20 20 20 20 g node */.
2540: 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20 20 7d break;. }. }
2550: 0a 20 20 69 66 28 20 6e 3d 3d 30 20 29 7b 20 20 . if( n==0 ){
2560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2570: 20 20 20 2f 2a 20 49 6e 73 65 72 74 20 61 20 6c /* Insert a l
2580: 65 61 66 20 6e 6f 64 65 20 2a 2f 0a 20 20 20 20 eaf node */.
2590: 6c 65 76 65 6c 2d 2d 3b 0a 20 20 20 20 6e 20 3d level--;. n =
25a0: 20 2a 68 5b 6c 65 76 65 6c 5d 20 3d 20 28 54 72 *h[level] = (Tr
25b0: 65 65 45 6c 65 6d 20 2a 29 54 63 6c 5f 41 6c 6c eeElem *)Tcl_All
25c0: 6f 63 28 20 73 69 7a 65 6f 66 28 54 72 65 65 45 oc( sizeof(TreeE
25d0: 6c 65 6d 29 20 29 3b 0a 20 20 20 20 69 66 28 20 lem) );. if(
25e0: 6e 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 n==0 ){. re
25f0: 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d turn data;. }
2600: 0a 20 20 20 20 6e 2d 3e 64 61 74 61 20 3d 20 64 . n->data = d
2610: 61 74 61 3b 0a 20 20 20 20 69 66 28 20 70 54 72 ata;. if( pTr
2620: 65 65 2d 3e 78 43 6f 70 79 20 29 7b 0a 20 20 20 ee->xCopy ){.
2630: 20 20 20 6e 2d 3e 6b 65 79 20 3d 20 70 54 72 65 n->key = pTre
2640: 65 2d 3e 78 43 6f 70 79 28 6b 65 79 29 3b 0a 20 e->xCopy(key);.
2650: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 }else{.
2660: 6e 2d 3e 6b 65 79 20 3d 20 6b 65 79 3b 0a 20 20 n->key = key;.
2670: 20 20 7d 0a 20 20 20 20 6e 2d 3e 6c 65 66 74 20 }. n->left
2680: 3d 20 6e 2d 3e 72 69 67 68 74 20 3d 20 30 3b 0a = n->right = 0;.
2690: 20 20 20 20 77 68 69 6c 65 28 20 6c 65 76 65 6c while( level
26a0: 3e 3d 30 20 29 20 54 72 65 65 42 61 6c 61 6e 63 >=0 ) TreeBalanc
26b0: 65 28 68 5b 6c 65 76 65 6c 2d 2d 5d 29 3b 0a 20 e(h[level--]);.
26c0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 6f 6c 64 3b }. return old;
26d0: 0a 7d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 .}...my c_functi
26e0: 6f 6e 20 7b 73 74 61 74 69 63 20 54 72 65 65 45 on {static TreeE
26f0: 6c 65 6d 20 2a 54 72 65 65 44 65 6c 65 74 65 4e lem *TreeDeleteN
2700: 74 68 45 6c 65 6d 28 54 72 65 65 45 6c 65 6d 20 thElem(TreeElem
2710: 2a 2a 70 70 54 6f 70 2c 20 69 6e 74 20 4e 29 7d **ppTop, int N)}
2720: 20 7b 0a 20 20 2f 2a 20 55 6e 6c 69 6e 6b 20 74 {. /* Unlink t
2730: 68 65 20 4e 2d 74 68 20 6e 6f 64 65 20 6f 66 20 he N-th node of
2740: 74 68 65 20 74 72 65 65 20 61 6e 64 20 72 65 74 the tree and ret
2750: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f urn a pointer to
2760: 20 74 68 61 74 0a 20 20 2a 2a 20 6e 6f 64 65 2e that. ** node.
2770: 20 20 28 54 68 65 20 6c 65 66 74 2d 6d 6f 73 74 (The left-most
2780: 20 6e 6f 64 65 20 69 73 20 30 2c 20 74 68 65 20 node is 0, the
2790: 6e 65 78 74 20 6e 6f 64 65 20 74 6f 20 74 68 65 next node to the
27a0: 20 72 69 67 68 74 20 69 73 0a 20 20 2a 2a 20 31 right is. ** 1
27b0: 20 61 6e 64 20 73 6f 20 66 6f 72 74 68 2e 29 0a and so forth.).
27c0: 20 20 2a 2f 0a 20 20 54 72 65 65 45 6c 65 6d 20 */. TreeElem
27d0: 2a 70 3b 20 20 20 20 20 20 20 20 2f 2a 20 46 6f *p; /* Fo
27e0: 72 20 77 61 6c 6b 69 6e 67 20 74 68 65 20 74 72 r walking the tr
27f0: 65 65 20 2a 2f 0a 20 20 69 6e 74 20 6c 65 76 65 ee */. int leve
2800: 6c 20 3d 20 30 3b 20 20 20 20 20 20 2f 2a 20 44 l = 0; /* D
2810: 65 70 74 68 20 6f 66 20 74 68 65 20 62 6c 61 6e epth of the blan
2820: 63 69 6e 67 20 73 74 61 63 6b 20 2a 2f 0a 20 20 cing stack */.
2830: 54 72 65 65 45 6c 65 6d 20 2a 2a 68 5b 31 30 30 TreeElem **h[100
2840: 5d 3b 20 20 2f 2a 20 42 61 6c 61 6e 63 65 20 73 ]; /* Balance s
2850: 74 61 63 6b 2e 20 20 31 30 30 20 69 73 20 73 75 tack. 100 is su
2860: 66 66 69 63 69 65 6e 74 20 66 6f 72 20 62 61 6c fficient for bal
2870: 61 6e 63 69 6e 67 0a 20 20 20 20 20 20 20 20 20 ancing.
2880: 20 20 20 20 20 20 20 20 20 20 20 20 20 2a 2a 20 **
2890: 61 20 74 72 65 65 20 77 69 74 68 20 75 70 20 74 a tree with up t
28a0: 6f 20 34 2e 30 45 2b 31 37 20 6e 6f 64 65 73 20 o 4.0E+17 nodes
28b0: 2a 2f 0a 0a 20 20 68 5b 30 5d 20 3d 20 70 70 54 */.. h[0] = ppT
28c0: 6f 70 3b 0a 20 20 6c 65 76 65 6c 20 3d 20 31 3b op;. level = 1;
28d0: 0a 20 20 70 20 3d 20 2a 70 70 54 6f 70 3b 0a 20 . p = *ppTop;.
28e0: 20 77 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 while( p ){.
28f0: 20 69 6e 74 20 77 3b 0a 20 20 20 20 77 20 3d 20 int w;. w =
2900: 28 70 2d 3e 6c 65 66 74 20 3f 20 70 2d 3e 6c 65 (p->left ? p->le
2910: 66 74 2d 3e 77 65 69 67 68 74 3a 20 30 29 3b 0a ft->weight: 0);.
2920: 20 20 20 20 69 66 28 20 4e 3e 77 20 29 7b 0a 20 if( N>w ){.
2930: 20 20 20 20 20 68 5b 6c 65 76 65 6c 2b 2b 5d 20 h[level++]
2940: 3d 20 26 28 70 2d 3e 72 69 67 68 74 29 3b 0a 20 = &(p->right);.
2950: 20 20 20 20 20 70 20 3d 20 70 2d 3e 72 69 67 68 p = p->righ
2960: 74 3b 0a 20 20 20 20 20 20 4e 20 2d 3d 20 77 2b t;. N -= w+
2970: 31 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28 1;. }else if(
2980: 20 4e 3c 77 20 29 7b 0a 20 20 20 20 20 20 68 5b N<w ){. h[
2990: 6c 65 76 65 6c 2b 2b 5d 20 3d 20 26 28 70 2d 3e level++] = &(p->
29a0: 6c 65 66 74 29 3b 0a 20 20 20 20 20 20 70 20 3d left);. p =
29b0: 20 70 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 7d 65 p->left;. }e
29c0: 6c 73 65 7b 0a 20 20 20 20 20 20 62 72 65 61 6b lse{. break
29d0: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 ;. }. }. if
29e0: 28 20 70 20 29 7b 0a 20 20 20 20 6c 65 76 65 6c ( p ){. level
29f0: 2d 2d 3b 0a 20 20 20 20 69 66 28 20 70 2d 3e 6c --;. if( p->l
2a00: 65 66 74 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 eft==0 ){.
2a10: 2a 68 5b 6c 65 76 65 6c 5d 20 3d 20 70 2d 3e 72 *h[level] = p->r
2a20: 69 67 68 74 3b 0a 20 20 20 20 20 20 6c 65 76 65 ight;. leve
2a30: 6c 2d 2d 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 l--;. }else i
2a40: 66 28 20 70 2d 3e 72 69 67 68 74 3d 3d 30 20 29 f( p->right==0 )
2a50: 7b 0a 20 20 20 20 20 20 2a 68 5b 6c 65 76 65 6c {. *h[level
2a60: 5d 20 3d 20 70 2d 3e 6c 65 66 74 3b 0a 20 20 20 ] = p->left;.
2a70: 20 20 20 6c 65 76 65 6c 2d 2d 3b 0a 20 20 20 20 level--;.
2a80: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 54 72 65 }else{. Tre
2a90: 65 45 6c 65 6d 20 2a 78 3b 0a 20 20 20 20 20 20 eElem *x;.
2aa0: 78 20 3d 20 54 72 65 65 44 65 6c 65 74 65 4e 74 x = TreeDeleteNt
2ab0: 68 45 6c 65 6d 28 26 28 70 2d 3e 72 69 67 68 74 hElem(&(p->right
2ac0: 29 2c 30 29 3b 0a 20 20 20 20 20 20 78 2d 3e 72 ),0);. x->r
2ad0: 69 67 68 74 20 3d 20 70 2d 3e 72 69 67 68 74 3b ight = p->right;
2ae0: 0a 20 20 20 20 20 20 78 2d 3e 6c 65 66 74 20 3d . x->left =
2af0: 20 70 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 20 20 p->left;.
2b00: 2a 68 5b 6c 65 76 65 6c 5d 20 3d 20 78 3b 0a 20 *h[level] = x;.
2b10: 20 20 20 7d 0a 20 20 20 20 77 68 69 6c 65 28 20 }. while(
2b20: 6c 65 76 65 6c 3e 3d 30 20 29 20 54 72 65 65 42 level>=0 ) TreeB
2b30: 61 6c 61 6e 63 65 28 68 5b 6c 65 76 65 6c 2d 2d alance(h[level--
2b40: 5d 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e ]);. }. return
2b50: 20 70 3b 0a 7d 0a 0d 0a 6d 79 20 63 5f 66 75 6e p;.}...my c_fun
2b60: 63 74 69 6f 6e 20 7b 73 74 61 74 69 63 20 54 72 ction {static Tr
2b70: 65 65 45 6c 65 6d 20 2a 54 72 65 65 44 65 6c 65 eeElem *TreeDele
2b80: 74 65 45 6c 65 6d 28 54 72 65 65 20 2a 74 72 65 teElem(Tree *tre
2b90: 65 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 6b e, const void *k
2ba0: 65 79 29 7d 20 7b 0a 20 20 2f 2a 20 55 6e 6c 69 ey)} {. /* Unli
2bb0: 6e 6b 20 74 68 65 20 6e 6f 64 65 20 6f 66 20 74 nk the node of t
2bc0: 68 65 20 74 72 65 65 20 63 6f 72 72 65 73 70 6f he tree correspo
2bd0: 6e 64 69 6e 67 20 74 6f 20 6b 65 79 20 61 6e 64 nding to key and
2be0: 20 72 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 return a pointe
2bf0: 72 20 0a 20 20 2a 2a 20 74 6f 20 74 68 61 74 20 r . ** to that
2c00: 6e 6f 64 65 2e 0a 20 20 2a 2f 0a 20 20 54 72 65 node.. */. Tre
2c10: 65 45 6c 65 6d 20 2a 70 3b 20 20 20 20 20 20 20 eElem *p;
2c20: 20 2f 2a 20 46 6f 72 20 77 61 6c 6b 69 6e 67 20 /* For walking
2c30: 74 68 65 20 74 72 65 65 20 2a 2f 0a 20 20 69 6e the tree */. in
2c40: 74 20 6c 65 76 65 6c 20 3d 20 30 3b 20 20 20 20 t level = 0;
2c50: 20 20 2f 2a 20 44 65 70 74 68 20 6f 66 20 74 68 /* Depth of th
2c60: 65 20 62 6c 61 6e 63 69 6e 67 20 73 74 61 63 6b e blancing stack
2c70: 20 2a 2f 0a 20 20 54 72 65 65 45 6c 65 6d 20 2a */. TreeElem *
2c80: 2a 68 5b 31 30 30 5d 3b 20 20 2f 2a 20 42 61 6c *h[100]; /* Bal
2c90: 61 6e 63 65 20 73 74 61 63 6b 2e 20 20 31 30 30 ance stack. 100
2ca0: 20 69 73 20 73 75 66 66 69 63 69 65 6e 74 20 66 is sufficient f
2cb0: 6f 72 20 62 61 6c 61 6e 63 69 6e 67 0a 20 20 20 or balancing.
2cc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2cd0: 20 20 20 2a 2a 20 61 20 74 72 65 65 20 77 69 74 ** a tree wit
2ce0: 68 20 75 70 20 74 6f 20 34 2e 30 45 2b 31 37 20 h up to 4.0E+17
2cf0: 6e 6f 64 65 73 20 2a 2f 0a 0a 20 20 68 5b 30 5d nodes */.. h[0]
2d00: 20 3d 20 26 74 72 65 65 2d 3e 74 6f 70 3b 0a 20 = &tree->top;.
2d10: 20 6c 65 76 65 6c 20 3d 20 31 3b 0a 20 20 70 20 level = 1;. p
2d20: 3d 20 74 72 65 65 2d 3e 74 6f 70 3b 0a 20 20 77 = tree->top;. w
2d30: 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 69 hile( p ){. i
2d40: 6e 74 20 77 3b 0a 20 20 20 20 77 20 3d 20 74 72 nt w;. w = tr
2d50: 65 65 2d 3e 78 43 6f 6d 70 61 72 65 28 70 2d 3e ee->xCompare(p->
2d60: 6b 65 79 2c 20 6b 65 79 29 3b 0a 20 20 20 20 69 key, key);. i
2d70: 66 28 20 77 3c 30 20 29 7b 0a 20 20 20 20 20 20 f( w<0 ){.
2d80: 68 5b 6c 65 76 65 6c 2b 2b 5d 20 3d 20 26 28 70 h[level++] = &(p
2d90: 2d 3e 72 69 67 68 74 29 3b 0a 20 20 20 20 20 20 ->right);.
2da0: 70 20 3d 20 70 2d 3e 72 69 67 68 74 3b 0a 20 20 p = p->right;.
2db0: 20 20 7d 65 6c 73 65 20 69 66 28 20 77 3e 30 20 }else if( w>0
2dc0: 29 7b 0a 20 20 20 20 20 20 68 5b 6c 65 76 65 6c ){. h[level
2dd0: 2b 2b 5d 20 3d 20 26 28 70 2d 3e 6c 65 66 74 29 ++] = &(p->left)
2de0: 3b 0a 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 6c ;. p = p->l
2df0: 65 66 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a eft;. }else{.
2e00: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 break;.
2e10: 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 20 29 }. }. if( p )
2e20: 7b 0a 20 20 20 20 6c 65 76 65 6c 2d 2d 3b 0a 20 {. level--;.
2e30: 20 20 20 69 66 28 20 70 2d 3e 6c 65 66 74 3d 3d if( p->left==
2e40: 30 20 29 7b 0a 20 20 20 20 20 20 2a 68 5b 6c 65 0 ){. *h[le
2e50: 76 65 6c 5d 20 3d 20 70 2d 3e 72 69 67 68 74 3b vel] = p->right;
2e60: 0a 20 20 20 20 20 20 6c 65 76 65 6c 2d 2d 3b 0a . level--;.
2e70: 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20 70 2d }else if( p-
2e80: 3e 72 69 67 68 74 3d 3d 30 20 29 7b 0a 20 20 20 >right==0 ){.
2e90: 20 20 20 2a 68 5b 6c 65 76 65 6c 5d 20 3d 20 70 *h[level] = p
2ea0: 2d 3e 6c 65 66 74 3b 0a 20 20 20 20 20 20 6c 65 ->left;. le
2eb0: 76 65 6c 2d 2d 3b 0a 20 20 20 20 7d 65 6c 73 65 vel--;. }else
2ec0: 7b 0a 20 20 20 20 20 20 54 72 65 65 45 6c 65 6d {. TreeElem
2ed0: 20 2a 78 3b 0a 20 20 20 20 20 20 78 20 3d 20 54 *x;. x = T
2ee0: 72 65 65 44 65 6c 65 74 65 4e 74 68 45 6c 65 6d reeDeleteNthElem
2ef0: 28 26 28 70 2d 3e 72 69 67 68 74 29 2c 30 29 3b (&(p->right),0);
2f00: 0a 20 20 20 20 20 20 78 2d 3e 72 69 67 68 74 20 . x->right
2f10: 3d 20 70 2d 3e 72 69 67 68 74 3b 0a 20 20 20 20 = p->right;.
2f20: 20 20 78 2d 3e 6c 65 66 74 20 3d 20 70 2d 3e 6c x->left = p->l
2f30: 65 66 74 3b 0a 20 20 20 20 20 20 2a 68 5b 6c 65 eft;. *h[le
2f40: 76 65 6c 5d 20 3d 20 78 3b 0a 20 20 20 20 7d 0a vel] = x;. }.
2f50: 20 20 20 20 77 68 69 6c 65 28 20 6c 65 76 65 6c while( level
2f60: 3e 3d 30 20 29 20 54 72 65 65 42 61 6c 61 6e 63 >=0 ) TreeBalanc
2f70: 65 28 68 5b 6c 65 76 65 6c 2d 2d 5d 29 3b 0a 20 e(h[level--]);.
2f80: 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b 0a 7d }. return p;.}
2f90: 0d 0a 0d 0a 6d 79 20 63 5f 66 75 6e 63 74 69 6f ....my c_functio
2fa0: 6e 20 7b 76 6f 69 64 20 2a 54 72 65 65 49 6e 73 n {void *TreeIns
2fb0: 65 72 74 28 54 72 65 65 20 2a 74 72 65 65 2c 20 ert(Tree *tree,
2fc0: 76 6f 69 64 20 2a 6b 65 79 2c 20 76 6f 69 64 20 void *key, void
2fd0: 2a 64 61 74 61 29 7d 20 7b 0a 20 20 2f 2a 20 49 *data)} {. /* I
2fe0: 6e 73 65 72 74 20 6e 65 77 20 64 61 74 61 20 69 nsert new data i
2ff0: 6e 74 6f 20 61 20 6e 6f 64 65 20 6f 66 20 74 68 nto a node of th
3000: 65 20 74 72 65 65 2e 20 20 54 68 65 20 6e 6f 64 e tree. The nod
3010: 65 20 69 73 20 69 64 65 6e 74 69 66 69 65 64 0a e is identified.
3020: 20 20 2a 2a 20 62 79 20 22 6b 65 79 22 2e 0a 20 ** by "key"..
3030: 20 2a 2a 0a 20 20 2a 2a 20 49 66 20 74 68 65 20 **. ** If the
3040: 6e 65 77 20 64 61 74 61 20 69 73 20 4e 55 4c 4c new data is NULL
3050: 2c 20 74 68 65 6e 20 6e 6f 64 65 20 69 73 20 64 , then node is d
3060: 65 6c 65 74 65 64 2e 0a 20 20 2a 2a 0a 20 20 2a eleted.. **. *
3070: 2a 20 49 66 20 74 68 65 20 6e 6f 64 65 20 61 72 * If the node ar
3080: 65 61 64 79 20 65 78 69 73 74 73 2c 20 74 68 65 eady exists, the
3090: 20 6e 65 77 20 64 61 74 61 20 6f 76 65 72 77 72 new data overwr
30a0: 69 74 65 73 20 74 68 65 20 6f 6c 64 20 61 6e 64 ites the old and
30b0: 0a 20 20 2a 2a 20 74 68 65 20 6f 6c 64 20 64 61 . ** the old da
30c0: 74 61 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 ta is returned.
30d0: 20 49 66 20 74 68 65 20 6e 6f 64 65 20 64 6f 65 If the node doe
30e0: 73 6e 27 74 20 61 6c 72 65 61 64 79 20 65 78 69 sn't already exi
30f0: 73 74 2c 20 74 68 65 6e 0a 20 20 2a 2a 20 61 20 st, then. ** a
3100: 6e 65 77 20 6e 6f 64 65 20 69 73 20 63 72 65 61 new node is crea
3110: 74 65 64 20 61 6e 64 20 74 68 65 20 66 75 6e 63 ted and the func
3120: 74 69 6f 6e 20 72 65 74 75 72 6e 73 20 4e 55 4c tion returns NUL
3130: 4c 2e 0a 20 20 2a 2f 0a 0a 20 20 76 6f 69 64 20 L.. */.. void
3140: 2a 6f 6c 64 3b 0a 20 20 69 66 28 20 64 61 74 61 *old;. if( data
3150: 3d 3d 30 20 29 7b 0a 20 20 20 20 54 72 65 65 45 ==0 ){. TreeE
3160: 6c 65 6d 20 2a 65 6c 65 6d 20 3d 20 54 72 65 65 lem *elem = Tree
3170: 44 65 6c 65 74 65 45 6c 65 6d 28 74 72 65 65 2c DeleteElem(tree,
3180: 20 6b 65 79 29 3b 0a 20 20 20 20 69 66 28 20 65 key);. if( e
3190: 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 69 66 28 lem ){. if(
31a0: 20 74 72 65 65 2d 3e 78 46 72 65 65 20 29 7b 0a tree->xFree ){.
31b0: 20 20 20 20 20 20 20 20 74 72 65 65 2d 3e 78 46 tree->xF
31c0: 72 65 65 28 65 6c 65 6d 2d 3e 6b 65 79 29 3b 0a ree(elem->key);.
31d0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 6f 6c }. ol
31e0: 64 20 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a d = elem->data;.
31f0: 20 20 20 20 20 20 54 63 6c 5f 46 72 65 65 28 28 Tcl_Free((
3200: 63 68 61 72 20 2a 29 65 6c 65 6d 29 3b 0a 20 20 char *)elem);.
3210: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6f }else{. o
3220: 6c 64 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 ld = 0;. }.
3230: 7d 65 6c 73 65 7b 0a 20 20 20 20 6f 6c 64 20 3d }else{. old =
3240: 20 54 72 65 65 49 6e 73 65 72 74 45 6c 65 6d 65 TreeInsertEleme
3250: 6e 74 28 74 72 65 65 2c 6b 65 79 2c 64 61 74 61 nt(tree,key,data
3260: 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 );. }. return
3270: 6f 6c 64 3b 0a 7d 0d 0a 0d 0a 6d 79 20 63 5f 66 old;.}....my c_f
3280: 75 6e 63 74 69 6f 6e 20 7b 76 6f 69 64 20 2a 54 unction {void *T
3290: 72 65 65 43 68 61 6e 67 65 4e 74 68 28 54 72 65 reeChangeNth(Tre
32a0: 65 20 2a 74 72 65 65 2c 20 69 6e 74 20 6e 2c 20 e *tree, int n,
32b0: 76 6f 69 64 20 2a 64 61 74 61 29 7d 20 7b 0a 20 void *data)} {.
32c0: 20 2f 2a 20 43 68 61 6e 67 65 20 74 68 65 20 64 /* Change the d
32d0: 61 74 61 20 6f 6e 20 74 68 65 20 6e 2d 74 68 20 ata on the n-th
32e0: 6e 6f 64 65 20 6f 66 20 74 68 65 20 74 72 65 65 node of the tree
32f0: 2e 20 20 54 68 65 20 6f 6c 64 20 64 61 74 61 0a . The old data.
3300: 20 20 2a 2a 20 69 73 20 72 65 74 75 72 6e 65 64 ** is returned
3310: 2e 0a 20 20 2a 2a 0a 20 20 2a 2a 20 49 66 20 64 .. **. ** If d
3320: 61 74 61 3d 3d 4e 55 4c 4c 2c 20 74 68 65 6e 20 ata==NULL, then
3330: 74 68 65 20 6e 2d 74 68 20 6e 6f 64 65 20 6f 66 the n-th node of
3340: 20 74 68 65 20 74 72 65 65 20 69 73 20 64 65 6c the tree is del
3350: 65 74 65 64 2e 20 20 28 54 68 65 0a 20 20 2a 2a eted. (The. **
3360: 20 64 61 74 61 20 61 73 73 6f 63 69 61 74 65 64 data associated
3370: 20 77 69 74 68 20 74 68 61 74 20 6e 6f 64 65 20 with that node
3380: 69 73 20 73 74 69 6c 6c 20 72 65 74 75 72 6e 65 is still returne
3390: 64 2e 29 0a 20 20 2a 2a 0a 20 20 2a 2a 20 49 66 d.). **. ** If
33a0: 20 74 68 65 20 76 61 6c 75 65 20 4e 20 69 73 20 the value N is
33b0: 6f 75 74 2d 6f 66 2d 62 6f 75 6e 64 73 2c 20 74 out-of-bounds, t
33c0: 68 65 6e 20 6e 6f 20 6e 65 77 20 6e 6f 64 65 20 hen no new node
33d0: 69 73 20 63 72 65 61 74 65 64 2e 0a 20 20 2a 2a is created.. **
33e0: 20 49 6e 73 74 65 61 64 2c 20 74 68 65 20 22 64 Instead, the "d
33f0: 61 74 61 22 20 70 61 72 61 6d 65 74 65 72 20 69 ata" parameter i
3400: 73 20 72 65 74 75 72 6e 65 64 2e 0a 20 20 2a 2f s returned.. */
3410: 0a 20 20 76 6f 69 64 20 2a 6f 6c 64 3b 0a 20 20 . void *old;.
3420: 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a 20 if( data==0 ){.
3430: 20 20 20 54 72 65 65 45 6c 65 6d 20 2a 65 6c 65 TreeElem *ele
3440: 6d 20 3d 20 54 72 65 65 44 65 6c 65 74 65 4e 74 m = TreeDeleteNt
3450: 68 45 6c 65 6d 28 26 74 72 65 65 2d 3e 74 6f 70 hElem(&tree->top
3460: 2c 6e 29 3b 0a 20 20 20 20 69 66 28 20 65 6c 65 ,n);. if( ele
3470: 6d 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 74 m ){. if( t
3480: 72 65 65 2d 3e 78 46 72 65 65 20 29 7b 0a 20 20 ree->xFree ){.
3490: 20 20 20 20 20 20 74 72 65 65 2d 3e 78 46 72 65 tree->xFre
34a0: 65 28 65 6c 65 6d 2d 3e 6b 65 79 29 3b 0a 20 20 e(elem->key);.
34b0: 20 20 20 20 7d 0a 20 20 20 20 20 20 6f 6c 64 20 }. old
34c0: 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 = elem->data;.
34d0: 20 20 20 20 54 63 6c 5f 46 72 65 65 28 28 63 68 Tcl_Free((ch
34e0: 61 72 20 2a 29 65 6c 65 6d 29 3b 0a 20 20 20 20 ar *)elem);.
34f0: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6f 6c 64 }else{. old
3500: 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 65 = 0;. }. }e
3510: 6c 73 65 7b 0a 20 20 20 20 54 72 65 65 45 6c 65 lse{. TreeEle
3520: 6d 20 2a 65 6c 65 6d 20 3d 20 54 72 65 65 46 69 m *elem = TreeFi
3530: 6e 64 4e 74 68 45 6c 65 6d 28 74 72 65 65 2c 6e ndNthElem(tree,n
3540: 29 3b 0a 20 20 20 20 69 66 28 20 65 6c 65 6d 20 );. if( elem
3550: 29 7b 0a 20 20 20 20 20 20 6f 6c 64 20 3d 20 65 ){. old = e
3560: 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20 20 20 lem->data;.
3570: 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61 elem->data = da
3580: 74 61 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 ta;. }else{.
3590: 20 20 20 20 20 6f 6c 64 20 3d 20 64 61 74 61 3b old = data;
35a0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 . }. }. ret
35b0: 75 72 6e 20 6f 6c 64 3b 0a 7d 0a urn old;.}.
