source: trunk/src/fastdep/avl.c@ 3686

Last change on this file since 3686 was 2243, checked in by bird, 17 years ago

*: Updated copyright to 2009 and normalized name & email.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 26.0 KB
Line 
1/* $Id: avl.c 2243 2009-01-10 02:24:02Z bird $
2 *
3 * AVL-Tree (lookalike) implementation.
4 *
5 * Copyright (c) 1999 knut st. osmundsen
6 *
7 * GPL
8 *
9 */
10
11/*******************************************************************************
12* Defined Constants And Macros *
13*******************************************************************************/
14
15/*
16 * AVL helper macros.
17 */
18#define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
19#define max(a,b) (((a) > (b)) ? (a) : (b))
20
21#ifndef INLINE
22# if defined(__IBMC__)
23# define INLINE _Inline
24# elif defined(__IBMCPP__)
25# define INLINE inline
26# elif defined(__WATCOMC__)
27# define INLINE __inline
28# elif defined(__WATCOM_CPLUSPLUS__)
29# define INLINE inline
30# else
31# error message("unknown compiler - inline keyword unknown!")
32# endif
33#endif
34
35
36/*******************************************************************************
37* Internal Functions *
38*******************************************************************************/
39#include <os2.h>
40#include "avl.h"
41#if defined(RING0) || defined(RING3)
42 #include "dev32.h"
43#else
44 #define SSToDS(a) (a)
45#endif
46#include "string.h"
47
48#if defined(__IBMCPP__) || defined(__IBMC__)
49#include <builtin.h>
50#define assert(a) ((a) ? (void)0 : __interrupt(3) )
51#else
52#include <assert.h>
53#endif
54
55
56/*******************************************************************************
57* Structures and Typedefs *
58*******************************************************************************/
59/*
60 * A stack used to avoid recursive calls...
61 */
62typedef struct _AVLStack
63{
64 unsigned cEntries;
65 PPAVLNODECORE aEntries[AVL_MAX_HEIGHT];
66} AVLSTACK, *PAVLSTACK;
67typedef struct _AVLStack2
68{
69 unsigned cEntries;
70 PAVLNODECORE aEntries[AVL_MAX_HEIGHT];
71 char achFlags[AVL_MAX_HEIGHT];
72} AVLSTACK2, *PAVLSTACK2;
73
74
75/*******************************************************************************
76* Internal Functions *
77*******************************************************************************/
78INLINE void AVLRebalance(PAVLSTACK pStack);
79
80
81/**
82 * Inserts a node into the AVL-tree.
83 * @returns TRUE if inserted.
84 * FALSE if node exists in tree.
85 * @param ppTree Pointer to the AVL-tree root node pointer.
86 * @param pNode Pointer to the node which is to be added.
87 * @sketch Find the location of the node (using binary three algorithm.):
88 * LOOP until NULL leaf pointer
89 * BEGIN
90 * Add node pointer pointer to the AVL-stack.
91 * IF new-node-key < node key THEN
92 * left
93 * ELSE
94 * right
95 * END
96 * Fill in leaf node and insert it.
97 * Rebalance the tree.
98 * @status completely implemented.
99 * @author knut st. osmundsen
100 */
101BOOL AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode)
102{
103 AVLSTACK AVLStack;
104 PPAVLNODECORE ppCurNode = ppTree;
105 register AVLKEY Key = pNode->Key;
106 register PAVLNODECORE pCurNode;
107
108 AVLStack.cEntries = 0;
109
110 while ((pCurNode = *ppCurNode) != NULL)
111 {
112 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
113 assert(pNode != pCurNode);
114 AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
115 #ifdef AVL_MAY_TRY_INSERT_EQUAL
116 /* check if equal */
117 if (AVL_E(pCurNode->Key, Key))
118 return FALSE;
119 #endif
120 if (AVL_G(pCurNode->Key, Key))
121 ppCurNode = &pCurNode->pLeft;
122 else
123 ppCurNode = &pCurNode->pRight;
124 }
125
126 pNode->pLeft = pNode->pRight = NULL;
127 pNode->uchHeight = 1;
128 *ppCurNode = pNode;
129
130 AVLRebalance(SSToDS(&AVLStack));
131 return TRUE;
132}
133
134
135/**
136 * Removes a node from the AVL-tree.
137 * @returns Pointer to the node.
138 * @param ppTree Pointer to the AVL-tree root node pointer.
139 * @param Key Key value of the node which is to be removed.
140 * @sketch Find the node which is to be removed:
141 * LOOP until not found
142 * BEGIN
143 * Add node pointer pointer to the AVL-stack.
144 * IF the keys matches THEN break!
145 * IF remove key < node key THEN
146 * left
147 * ELSE
148 * right
149 * END
150 * IF found THEN
151 * BEGIN
152 * IF left node not empty THEN
153 * BEGIN
154 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
155 * Start at left node.
156 * LOOP until right node is empty
157 * BEGIN
158 * Add to stack.
159 * go right.
160 * END
161 * Link out the found node.
162 * Replace the node which is to be removed with the found node.
163 * Correct the stack entry for the pointer to the left tree.
164 * END
165 * ELSE
166 * BEGIN
167 * Move up right node.
168 * Remove last stack entry.
169 * END
170 * Balance tree using stack.
171 * END
172 * return pointer to the removed node (if found).
173 * @status completely implemented.
174 * @author knut st. osmundsen
175 */
176PAVLNODECORE AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key)
177{
178 AVLSTACK AVLStack;
179 PPAVLNODECORE ppDeleteNode = ppTree;
180 register PAVLNODECORE pDeleteNode;
181
182 AVLStack.cEntries = 0;
183
184 while ((pDeleteNode = *ppDeleteNode) != NULL)
185 {
186 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
187 AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
188 #ifndef AVL_CMP
189 if (AVL_E(pDeleteNode->Key, Key))
190 break;
191
192 if (AVL_G(pDeleteNode->Key, Key))
193 ppDeleteNode = &pDeleteNode->pLeft;
194 else
195 ppDeleteNode = &pDeleteNode->pRight;
196 #else
197 {
198 int register iDiff;
199 if ((iDiff = AVL_CMP(pDeleteNode->Key, Key)) == 0)
200 break;
201
202 if (iDiff > 0)
203 ppDeleteNode = &pDeleteNode->pLeft;
204 else
205 ppDeleteNode = &pDeleteNode->pRight;
206 }
207 #endif
208 }
209
210 if (pDeleteNode != NULL)
211 {
212 if (pDeleteNode->pLeft != NULL)
213 {
214 unsigned iStackEntry = AVLStack.cEntries;
215 PPAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
216 register PAVLNODECORE pLeftLeast;
217
218 while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
219 {
220 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
221 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
222 ppLeftLeast = &pLeftLeast->pRight;
223 pLeftLeast = pLeftLeast->pRight;
224 }
225
226 /* link out pLeftLeast */
227 *ppLeftLeast = pLeftLeast->pLeft;
228
229 /* link in place of the delete node. */
230 pLeftLeast->pLeft = pDeleteNode->pLeft;
231 pLeftLeast->pRight = pDeleteNode->pRight;
232 pLeftLeast->uchHeight = pDeleteNode->uchHeight;
233 *ppDeleteNode = pLeftLeast;
234 AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
235 }
236 else
237 {
238 *ppDeleteNode = pDeleteNode->pRight;
239 AVLStack.cEntries--;
240 }
241
242 AVLRebalance(SSToDS(&AVLStack));
243 }
244
245 return pDeleteNode;
246}
247
248
249/**
250 * Gets a node from the tree (does not remove it!)
251 * @returns Pointer to the node holding the given key.
252 * @param ppTree Pointer to the AVL-tree root node pointer.
253 * @param Key Key value of the node which is to be found.
254 * @sketch
255 * @status completely implemented.
256 * @author knut st. osmundsen
257 */
258PAVLNODECORE AVLGet(PPAVLNODECORE ppTree, AVLKEY Key)
259{
260 #ifndef AVL_CMP
261 register PAVLNODECORE pNode = *ppTree;
262
263 while (pNode != NULL && AVL_NE(pNode->Key, Key))
264 {
265 if (AVL_G(pNode->Key, Key))
266 pNode = pNode->pLeft;
267 else
268 pNode = pNode->pRight;
269 }
270
271 #else
272
273 register int iDiff;
274 register PAVLNODECORE pNode = *ppTree;
275
276 while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
277 {
278 if (iDiff > 0)
279 pNode = pNode->pLeft;
280 else
281 pNode = pNode->pRight;
282 }
283
284 #endif
285
286 return pNode;
287}
288
289
290/**
291 * Gets a node from the tree and its parent node (if any) (does not remove any nodes!)
292 * @returns Pointer to the node holding the given key.
293 * @param ppTree Pointer to the AVL-tree root node pointer.
294 * @param ppParent Pointer to a variable which will hold the pointer to the partent node on
295 * return. When no node is found, this will hold the last searched node.
296 * @param Key Key value of the node which is to be found.
297 * @sketch
298 * @status completely implemented.
299 * @author knut st. osmundsen
300 */
301PAVLNODECORE AVLGetWithParent(PPAVLNODECORE ppTree, PPAVLNODECORE ppParent, AVLKEY Key)
302{
303 #ifndef AVL_CMP
304
305 register PAVLNODECORE pNode = *ppTree;
306 register PAVLNODECORE pParent = NULL;
307
308 while (pNode != NULL && AVL_NE(pNode->Key, Key))
309 {
310 pParent = pNode;
311 if (AVL_G(pNode->Key, Key))
312 pNode = pNode->pLeft;
313 else
314 pNode = pNode->pRight;
315 }
316
317 #else
318
319 register PAVLNODECORE pNode = *ppTree;
320 register PAVLNODECORE pParent = NULL;
321 register int iDiff;
322
323 while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
324 {
325 pParent = pNode;
326 if (iDiff > 0)
327 pNode = pNode->pLeft;
328 else
329 pNode = pNode->pRight;
330 }
331
332 #endif
333
334 *ppParent = pParent;
335 return pNode;
336}
337
338
339
340/**
341 * Gets node from the tree (does not remove it!) and it's adjecent (by key value) nodes.
342 * @returns Pointer to the node holding the given key.
343 * @param ppTree Pointer to the AVL-tree root node pointer.
344 * @param Key Key value of the node which is to be found.
345 * @param ppLeft Pointer to left node pointer.
346 * @param ppRight Pointer to right node pointer.
347 * @sketch Find node with the given key, record search path on the stack.
348 * IF found THEN
349 * BEGIN
350 * Find the right-most node in the left subtree.
351 * Find the left-most node in the right subtree.
352 * Rewind the stack while searching for more adjecent nodes.
353 * END
354 * return node with adjecent nodes.
355 * @status completely implemented.
356 * @author knut st. osmundsen
357 */
358PAVLNODECORE AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight)
359{
360 AVLSTACK AVLStack;
361 PPAVLNODECORE ppNode = ppTree;
362 PAVLNODECORE pNode;
363 #ifdef AVL_CMP
364 int iDiff;
365 #endif
366
367 AVLStack.cEntries = 0;
368
369 #ifndef AVL_CMP
370 while ((pNode = *ppNode) != NULL && AVL_NE(pNode->Key, Key))
371 #else
372 while ((pNode = *ppNode) != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
373 #endif
374 {
375 assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
376 AVLStack.aEntries[AVLStack.cEntries++] = ppNode;
377 #ifndef AVL_CMP
378 if (AVL_G(pNode->Key, Key))
379 #else
380 if (iDiff > 0)
381 #endif
382 ppNode = &pNode->pLeft;
383 else
384 ppNode = &pNode->pRight;
385 }
386
387 if (pNode != NULL)
388 {
389 PAVLNODECORE pCurNode;
390
391 /* find rigth-most node in left subtree. */
392 pCurNode = pNode->pLeft;
393 if (pCurNode != NULL)
394 while (pCurNode->pRight != NULL)
395 pCurNode = pCurNode->pRight;
396 *ppLeft = pCurNode;
397
398 /* find left-most node in right subtree. */
399 pCurNode = pNode->pRight;
400 if (pCurNode != NULL)
401 while (pCurNode->pLeft != NULL)
402 pCurNode = pCurNode->pLeft;
403 *ppRight = pCurNode;
404
405 /* rewind stack */
406 while (AVLStack.cEntries-- > 0)
407 {
408 pCurNode = *AVLStack.aEntries[AVLStack.cEntries];
409 #ifndef AVL_CMP
410 if (AVL_L(pCurNode->Key, Key) && (*ppLeft == NULL || AVL_G(pCurNode->Key, (*ppLeft)->Key)))
411 *ppLeft = pCurNode;
412 else if (AVL_G(pCurNode->Key, Key) && (*ppRight == NULL || AVL_L(pCurNode->Key, (*ppRight)->Key)))
413 *ppRight = pCurNode;
414 #else
415 if ((iDiff = AVL_CMP(pCurNode->Key, Key)) < 0 && (*ppLeft == NULL || AVL_G(pCurNode->Key, (*ppLeft)->Key)))
416 *ppLeft = pCurNode;
417 else if (iDiff > 0 && (*ppRight == NULL || AVL_L(pCurNode->Key, (*ppRight)->Key)))
418 *ppRight = pCurNode;
419 #endif
420 }
421 }
422 else
423 *ppLeft = *ppRight = NULL;
424
425 return pNode;
426}
427
428
429/**
430 * Iterates tru all nodes in the given tree.
431 * @returns 0 on success. Return from callback on failiure.
432 * @param ppTree Pointer to the AVL-tree root node pointer.
433 * @param fFromLeft TRUE: Left to right.
434 * FALSE: Right to left.
435 * @param pfnCallBack Pointer to callback function.
436 * @param pvParam Userparameter passed on to the callback function.
437 * @status completely implemented.
438 * @author knut st. osmundsen
439 */
440unsigned AVLDoWithAll(PPAVLNODECORE ppTree, int fFromLeft, PAVLCALLBACK pfnCallBack, void *pvParam)
441{
442 AVLSTACK2 AVLStack;
443 PAVLNODECORE pNode;
444 unsigned rc;
445
446 if (*ppTree == NULL)
447 return 0;
448
449 AVLStack.cEntries = 1;
450 AVLStack.achFlags[0] = 0;
451 AVLStack.aEntries[0] = *ppTree;
452
453 if (fFromLeft)
454 { /* from left */
455 while (AVLStack.cEntries > 0)
456 {
457 pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
458
459 /* left */
460 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
461 {
462 if (pNode->pLeft != NULL)
463 {
464 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
465 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
466 continue;
467 }
468 }
469
470 /* center */
471 rc = pfnCallBack(pNode, pvParam);
472 if (rc != 0)
473 return rc;
474
475 /* right */
476 AVLStack.cEntries--;
477 if (pNode->pRight != NULL)
478 {
479 AVLStack.achFlags[AVLStack.cEntries] = 0;
480 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
481 }
482 } /* while */
483 }
484 else
485 { /* from right */
486 while (AVLStack.cEntries > 0)
487 {
488 pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
489
490
491 /* right */
492 if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
493 {
494 if (pNode->pRight != NULL)
495 {
496 AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
497 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
498 continue;
499 }
500 }
501
502 /* center */
503 rc = pfnCallBack(pNode, pvParam);
504 if (rc != 0)
505 return rc;
506
507 /* left */
508 AVLStack.cEntries--;
509 if (pNode->pLeft != NULL)
510 {
511 AVLStack.achFlags[AVLStack.cEntries] = 0;
512 AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
513 }
514 } /* while */
515 }
516
517 return 0;
518}
519
520
521/**
522 * Starts an enumeration of all nodes in the given AVL tree.
523 * @returns Pointer to the first node in the tree.
524 * @param ppTree Pointer to the AVL-tree root node pointer.
525 * @param pEnumData Pointer to enumeration control data.
526 * @param fFromLeft TRUE: Left to right.
527 * FALSE: Right to left.
528 * @status completely implemented.
529 * @author knut st. osmundsen
530 */
531PAVLNODECORE AVLBeginEnumTree(PPAVLNODECORE ppTree, PAVLENUMDATA pEnumData, int fFromLeft)
532{
533 if (*ppTree != NULL)
534 {
535 pEnumData->fFromLeft = (char)fFromLeft;
536 pEnumData->cEntries = 1;
537 pEnumData->aEntries[0] = *ppTree;
538 pEnumData->achFlags[0] = 0;
539 }
540 else
541 pEnumData->cEntries = 0;
542
543 return AVLGetNextNode(pEnumData);
544}
545
546
547/**
548 * Get the next node in the tree enumeration.
549 * @returns Pointer to the first node in the tree.
550 * @param pEnumData Pointer to enumeration control data.
551 * @status completely implemented.
552 * @author knut st. osmundsen
553 */
554PAVLNODECORE AVLGetNextNode(PAVLENUMDATA pEnumData)
555{
556 PAVLNODECORE pNode;
557
558 if (pEnumData->fFromLeft)
559 { /* from left */
560 while (pEnumData->cEntries > 0)
561 {
562 pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
563
564 /* left */
565 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
566 {
567 pEnumData->achFlags[pEnumData->cEntries - 1]++;
568 if (pNode->pLeft != NULL)
569 {
570 pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
571 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
572 continue;
573 }
574 }
575
576 /* center */
577 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
578 {
579 pEnumData->achFlags[pEnumData->cEntries - 1]++;
580 return pNode;
581 }
582
583 /* right */
584 pEnumData->cEntries--;
585 if (pNode->pRight != NULL)
586 {
587 pEnumData->achFlags[pEnumData->cEntries] = 0;
588 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
589 }
590 } /* while */
591 }
592 else
593 { /* from right */
594 while (pEnumData->cEntries > 0)
595 {
596 pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
597
598
599 /* right */
600 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
601 {
602 pEnumData->achFlags[pEnumData->cEntries - 1]++;
603 if (pNode->pRight != NULL)
604 {
605 pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 right, 1 center, 2 left */
606 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
607 continue;
608 }
609 }
610
611 /* center */
612 if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
613 {
614 pEnumData->achFlags[pEnumData->cEntries - 1]++;
615 return pNode;
616 }
617
618 /* left */
619 pEnumData->cEntries--;
620 if (pNode->pLeft != NULL)
621 {
622 pEnumData->achFlags[pEnumData->cEntries] = 0;
623 pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
624 }
625 } /* while */
626 }
627
628 return NULL;
629
630}
631
632
633
634
635/**
636 * Finds the best fitting node in the tree for the given Key value.
637 * @returns Pointer to the best fitting node found.
638 * @param ppTree Pointer to Pointer to the tree root node.
639 * @param Key The Key of which is to be found a best fitting match for..
640 * @param fAbove TRUE: Returned node is have the closest key to Key from above.
641 * FALSE: Returned node is have the closest key to Key from below.
642 * @status completely implemented.
643 * @sketch The best fitting node is always located in the searchpath above you.
644 * >= (above): The node where you last turned left.
645 * <= (below): the node where you last turned right.
646 * @author knut st. osmundsen
647 */
648PAVLNODECORE AVLGetBestFit(PPAVLNODECORE ppTree, AVLKEY Key, int fAbove)
649{
650 #ifdef AVL_CMP
651 register int iDiff;
652 #endif
653 register PAVLNODECORE pNode = *ppTree;
654 PAVLNODECORE pNodeLast = NULL;
655
656 if (fAbove)
657 { /* pNode->Key >= Key */
658 #ifndef AVL_CMP
659 while (pNode != NULL && AVL_NE(pNode->Key, Key))
660 #else
661 while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
662 #endif
663 {
664 #ifndef AVL_CMP
665 if (AVL_G(pNode->Key, Key))
666 #else
667 if (iDiff > 0)
668 #endif
669 {
670 pNodeLast = pNode;
671 pNode = pNode->pLeft;
672 }
673 else
674 pNode = pNode->pRight;
675 }
676 }
677 else
678 { /* pNode->Key <= Key */
679 #ifndef AVL_CMP
680 while (pNode != NULL && AVL_NE(pNode->Key, Key))
681 #else
682 while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
683 #endif
684 {
685 #ifndef AVL_CMP
686 if (AVL_L(pNode->Key, Key))
687 #else
688 if (iDiff < 0)
689 #endif
690 {
691 pNodeLast = pNode;
692 pNode = pNode->pRight;
693 }
694 else
695 pNode = pNode->pLeft;
696 }
697 }
698
699 return pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */;
700}
701
702
703/**
704 * Rewindes a stack of pointer to pointers to nodes, rebalancing the tree.
705 * @param pStack Pointer to stack to rewind.
706 * @sketch LOOP thru all stack entries
707 * BEGIN
708 * Get pointer to pointer to node (and pointer to node) from stack.
709 * IF 2 higher left subtree than in right subtree THEN
710 * BEGIN
711 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
712 * * n+2|n+3
713 * / \ / \
714 * n+2 n ==> n+1 n+1|n+2
715 * / \ / \
716 * n+1 n|n+1 n|n+1 n
717 *
718 * Or with keys:
719 *
720 * 4 2
721 * / \ / \
722 * 2 5 ==> 1 4
723 * / \ / \
724 * 1 3 3 5
725 *
726 * ELSE
727 * * n+2
728 * / \ / \
729 * n+2 n n+1 n+1
730 * / \ ==> / \ / \
731 * n n+1 n L R n
732 * / \
733 * L R
734 *
735 * Or with keys:
736 * 6 4
737 * / \ / \
738 * 2 7 ==> 2 6
739 * / \ / \ / \
740 * 1 4 1 3 5 7
741 * / \
742 * 3 5
743 * END
744 * ELSE IF 2 higher in right subtree than in left subtree THEN
745 * BEGIN
746 * Same as above but left <==> right. (invert the picture)
747 * ELSE
748 * IF correct height THEN break
749 * ELSE correct height.
750 * END
751 * @status
752 * @author knut st. osmundsen
753 * @remark
754 */
755INLINE void AVLRebalance(PAVLSTACK pStack)
756{
757 while (pStack->cEntries > 0)
758 {
759 PPAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
760 PAVLNODECORE pNode = *ppNode;
761 PAVLNODECORE pLeftNode = pNode->pLeft;
762 unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
763 PAVLNODECORE pRightNode = pNode->pRight;
764 unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
765
766 if (uchRightHeight + 1 < uchLeftHeight)
767 {
768 PAVLNODECORE pLeftLeftNode = pLeftNode->pLeft;
769 PAVLNODECORE pLeftRightNode = pLeftNode->pRight;
770 unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
771
772 if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
773 {
774 pNode->pLeft = pLeftRightNode;
775 pLeftNode->pRight = pNode;
776 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
777 *ppNode = pLeftNode;
778 }
779 else
780 {
781 pLeftNode->pRight = pLeftRightNode->pLeft;
782 pNode->pLeft = pLeftRightNode->pRight;
783 pLeftRightNode->pLeft = pLeftNode;
784 pLeftRightNode->pRight = pNode;
785 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
786 pLeftRightNode->uchHeight = uchLeftHeight;
787 *ppNode = pLeftRightNode;
788 }
789 }
790 else if (uchLeftHeight + 1 < uchRightHeight)
791 {
792 PAVLNODECORE pRightLeftNode = pRightNode->pLeft;
793 unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
794 PAVLNODECORE pRightRightNode = pRightNode->pRight;
795
796 if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
797 {
798 pNode->pRight = pRightLeftNode;
799 pRightNode->pLeft = pNode;
800 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
801 *ppNode = pRightNode;
802 }
803 else
804 {
805 pRightNode->pLeft = pRightLeftNode->pRight;
806 pNode->pRight = pRightLeftNode->pLeft;
807 pRightLeftNode->pRight = pRightNode;
808 pRightLeftNode->pLeft = pNode;
809 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
810 pRightLeftNode->uchHeight = uchRightHeight;
811 *ppNode = pRightLeftNode;
812 }
813 }
814 else
815 {
816 register unsigned char uchHeight = (unsigned char)(max(uchLeftHeight, uchRightHeight) + 1);
817 if (uchHeight == pNode->uchHeight)
818 break;
819 pNode->uchHeight = uchHeight;
820 }
821 }
822}
823
Note: See TracBrowser for help on using the repository browser.