2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
42 #include "searchTree.h"
44 #define max(a,b) ((a>b)? a:b)
46 treeNode
* TreeNodeMake(void *key
)
48 treeNode
*ret
= (treeNode
*) malloc(sizeof(treeNode
));
57 void TreeNodeDeleteSingleNode(treeNode
* node
)
62 void TreeNodeDeleteWholeTree(treeNode
* node
)
64 if(node
== NULL
) return;
65 TreeNodeDeleteWholeTree(node
->left
);
66 TreeNodeDeleteWholeTree(node
->right
);
67 TreeNodeDeleteSingleNode(node
);
70 void TreeNodePrint(treeNode
* node
,
71 void (*keyPrint
) (void*))
73 if(node
==NULL
) return;
74 TreeNodePrint(node
->left
, keyPrint
);
76 TreeNodePrint(node
->right
, keyPrint
);
79 int TreeNodeDepth(treeNode
* root
)
81 if(root
== NULL
) return 0;
83 int leftdepth
= TreeNodeDepth(root
->left
);
84 int rightdepth
= TreeNodeDepth(root
->right
);
85 return 1 + max(leftdepth
, rightdepth
);
89 /*return the node with the key.
90 *NULL is returned if not found
92 treeNode
* TreeNodeFind(treeNode
* tree
, void* key
,
93 int (*compkey
) (void*, void*))
99 else if(compkey(key
, tree
->key
) < 0)
100 return TreeNodeFind(tree
->left
, key
, compkey
);
102 return TreeNodeFind(tree
->right
, key
, compkey
);
106 treeNode
* TreeNodeInsert(treeNode
* root
, treeNode
* newnode
,
107 int (*compkey
) (void *, void *))
111 /*going down the tree from the root.
112 *x traces the path, y is the parent of x.
116 if(compkey(newnode
->key
,x
->key
) < 0) /*if newnode < x*/
122 /*now y has the property that
123 * if newnode < y, then y->left is NULL
124 * if newnode > y, then y->right is NULL.
125 *So we want to isnert newnode to be the child of y
130 else if( compkey(newnode
->key
, y
->key
) <0)
142 treeNode
* TreeNodeDeleteSingleNode(treeNode
* tree
, treeNode
* node
)
147 if(node
==NULL
) return tree
;
149 if(node
->left
== NULL
|| node
->right
== NULL
) {
158 x
->parent
= y
->parent
;
160 if(y
->parent
== NULL
) /*y is the root which has at most one child x*/
162 else /*y is not the root*/
164 if(y
== y
->parent
->left
)
167 y
->parent
->right
= x
;
171 else { /*node has two children*/
173 y
= TreeNodeSuccessor(node
);
174 assert(y
->left
== NULL
);
176 if(y
== node
->right
) /*y is the right child if node*/
178 y
->parent
= node
->parent
;
179 y
->left
= node
->left
;
180 node
->left
->parent
= y
;
183 else /*y != node->right*/
187 x
->parent
= y
->parent
;
189 assert(y
->parent
!= NULL
);
190 if(y
== y
->parent
->left
)
193 y
->parent
->right
= x
;
194 /*move y to the position of node*/
195 y
->parent
= node
->parent
;
196 y
->left
= node
->left
;
197 y
->right
= node
->right
;
198 node
->left
->parent
= y
;
199 node
->right
->parent
= y
;
201 if(node
->parent
!= NULL
) {
202 if(node
->parent
->left
== node
)
203 node
->parent
->left
= y
;
205 node
->parent
->right
= y
;
206 ret
= tree
; /*the root if the tree doesn't change*/
208 else /*node->parent is NULL: node is the root*/
212 /*finally free the node, and return the new root*/
213 TreeNodeDeleteSingleNode(node
);
218 /*the minimum node in the tree rooted by node
220 treeNode
* TreeNodeMinimum(treeNode
* node
)
222 treeNode
* temp
= node
;
223 if(temp
== NULL
) return NULL
;
224 while(temp
->left
!= NULL
) {
230 /*the maximum node in the tree rooted by node
232 treeNode
* TreeNodeMaximum(treeNode
* node
)
234 treeNode
* temp
= node
;
235 if(temp
== NULL
) return NULL
;
236 while(temp
->right
!= NULL
) {
242 /*return the first node (in sorted order) which is to the right of this node
244 treeNode
* TreeNodeSuccessor(treeNode
* node
)
246 if(node
== NULL
) return NULL
;
247 if(node
->right
!= NULL
)
248 return TreeNodeMinimum(node
->right
);
249 else{ /*node->right is NULL*/
251 /*find the first right-ancestor*/
252 treeNode
*y
= node
->parent
;
254 while(y
!= NULL
&& x
== y
->right
) /*if y is a left parent of x*/
264 /*return the first node (in sorted order) which is to the left of this node
266 treeNode
* TreeNodePredecessor(treeNode
* node
)
268 if(node
== NULL
) return NULL
;
269 if(node
->left
!= NULL
)
270 return TreeNodeMaximum(node
->left
);
271 else{ /*node->left is NULL*/
272 /*find the first left-ancestor*/
273 treeNode
*y
= node
->parent
;
275 while(y
!= NULL
&& x
== y
->left
) /*if y is a right parent of x*/