avl.c@ 1043

Last change on this file since 1043 was 7, checked in by bird, 22 years ago
Initial version from odin32.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 26.1 KB

Line
1	/* $Id: avl.c 7 2002-10-15 21:00:40Z bird $
2	*
3	* AVL-Tree (lookalike) implementation.
4	*
5	* Copyright (c) 1999 knut st. osmundsen
6	*
7	* Project Odin Software License can be found in LICENSE.TXT
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	*/
62	typedef struct _AVLStack
63	{
64	unsigned cEntries;
65	PPAVLNODECORE aEntries[AVL_MAX_HEIGHT];
66	} AVLSTACK, *PAVLSTACK;
67	typedef 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	*******************************************************************************/
78	INLINE 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	*/
101	BOOL 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	*/
176	PAVLNODECORE 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	*/
258	PAVLNODECORE 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	*/
301	PAVLNODECORE 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	*/
358	PAVLNODECORE 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	*/
440	unsigned 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	*/
531	PAVLNODECORE 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	*/
554	PAVLNODECORE 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	*/
648	PAVLNODECORE 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	*/
755	INLINE 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.

source: kBuild/trunk/src/fastdep/avl.c@ 1043

Download in other formats: