ReactOS  0.4.13-dev-39-g8b6696f
searchTree.cc
Go to the documentation of this file.
1 /*
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:
9 **
10 ** http://oss.sgi.com/projects/FreeB
11 **
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.
17 **
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.
23 **
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.
33 **
34 */
35 /*
36 */
37 
38 #include <stdlib.h>
39 //#include <stdio.h>
40 #include "zlassert.h"
41 
42 #include "searchTree.h"
43 
44 #define max(a,b) ((a>b)? a:b)
45 
47 {
48  treeNode *ret = (treeNode*) malloc(sizeof(treeNode));
49  assert(ret);
50  ret->key = key;
51  ret->parent = NULL;
52  ret->left = NULL;
53  ret->right = NULL;
54  return ret;
55 }
56 
58 {
59  free(node);
60 }
61 
63 {
64  if(node == NULL) return;
68 }
69 
71  void (*keyPrint) (void*))
72 {
73  if(node ==NULL) return;
74  TreeNodePrint(node->left, keyPrint);
75  keyPrint(node->key);
76  TreeNodePrint(node->right, keyPrint);
77 }
78 
80 {
81  if(root == NULL) return 0;
82  else{
83  int leftdepth = TreeNodeDepth(root->left);
84  int rightdepth = TreeNodeDepth(root->right);
85  return 1 + max(leftdepth, rightdepth);
86  }
87 }
88 
89 /*return the node with the key.
90  *NULL is returned if not found
91  */
93  int (*compkey) (void*, void*))
94 {
95  if(tree == NULL)
96  return NULL;
97  if(key == tree->key)
98  return tree;
99  else if(compkey(key, tree->key) < 0)
100  return TreeNodeFind(tree->left, key, compkey);
101  else
102  return TreeNodeFind(tree->right, key, compkey);
103 }
104 
105 
107  int (*compkey) (void *, void *))
108 {
109  treeNode *y = NULL;
110  treeNode *x = root;
111  /*going down the tree from the root.
112  *x traces the path, y is the parent of x.
113  */
114  while (x != NULL){
115  y = x;
116  if(compkey(newnode->key,x->key) < 0) /*if newnode < x*/
117  x = x->left;
118  else
119  x = x->right;
120  }
121 
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
126  */
127  newnode->parent = y;
128  if(y == NULL)
129  return newnode;
130  else if( compkey(newnode->key, y->key) <0)
131  {
132  y->left = newnode;
133  }
134  else
135  {
136  y->right = newnode;
137  }
138 
139  return root;
140 }
141 
143 {
144  treeNode* y;
145  treeNode* x;
146  treeNode* ret;
147  if(node==NULL) return tree;
148 
149  if(node->left == NULL || node->right == NULL) {
150 
151  y = node;
152  if(y->left != NULL)
153  x = y->left;
154  else
155  x = y->right;
156 
157  if( x != NULL)
158  x->parent = y->parent;
159 
160  if(y->parent == NULL) /*y is the root which has at most one child x*/
161  ret = x;
162  else /*y is not the root*/
163  {
164  if(y == y->parent->left)
165  y->parent->left = x;
166  else
167  y->parent->right = x;
168  ret = tree;
169  }
170  }
171  else { /*node has two children*/
172 
174  assert(y->left == NULL);
175 
176  if(y == node->right) /*y is the right child if node*/
177  {
178  y->parent = node->parent;
179  y->left = node->left;
180  node->left->parent = y;
181 
182  }
183  else /*y != node->right*/
184  {
185  x = y->right;
186  if(x!= NULL)
187  x->parent = y->parent;
188 
189  assert(y->parent != NULL);
190  if(y == y->parent->left)
191  y->parent->left = x;
192  else
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;
200  }
201  if(node->parent != NULL) {
202  if(node->parent->left == node)
203  node->parent->left = y;
204  else
205  node->parent->right = y;
206  ret = tree; /*the root if the tree doesn't change*/
207  }
208  else /*node->parent is NULL: node is the root*/
209  ret = y;
210  }
211 
212  /*finally free the node, and return the new root*/
214  return ret;
215 }
216 
217 
218 /*the minimum node in the tree rooted by node
219  */
221 {
222  treeNode* temp = node;
223  if(temp == NULL) return NULL;
224  while(temp->left != NULL) {
225  temp = temp->left;
226  }
227  return temp;
228 }
229 
230 /*the maximum node in the tree rooted by node
231  */
233 {
234  treeNode* temp = node;
235  if(temp == NULL) return NULL;
236  while(temp->right != NULL) {
237  temp = temp->right;
238  }
239  return temp;
240 }
241 
242 /*return the first node (in sorted order) which is to the right of this node
243  */
245 {
246  if(node == NULL) return NULL;
247  if(node->right != NULL)
248  return TreeNodeMinimum(node->right);
249  else{ /*node->right is NULL*/
250 
251  /*find the first right-ancestor*/
252  treeNode *y = node->parent;
253  treeNode* x = node;
254  while(y != NULL && x == y->right) /*if y is a left parent of x*/
255  {
256 
257  x = y;
258  y = y->parent;
259  }
260  return y;
261  }
262 }
263 
264 /*return the first node (in sorted order) which is to the left of this node
265  */
267 {
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;
274  treeNode *x = node;
275  while(y != NULL && x == y->left) /*if y is a right parent of x*/
276  {
277  x = y;
278  y = y->parent;
279  }
280  return y;
281  }
282 }
treeNode * TreeNodeMake(void *key)
Definition: searchTree.cc:46
struct treeNode * left
Definition: searchTree.h:39
treeNode * TreeNodeMaximum(treeNode *node)
Definition: searchTree.cc:232
struct treeNode * right
Definition: searchTree.h:40
struct _tree tree
int TreeNodeDepth(treeNode *root)
Definition: searchTree.cc:79
#define free
Definition: debug_ros.c:5
struct _root root
#define assert(x)
Definition: debug.h:53
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
struct node node
smooth NULL
Definition: ftsmooth.c:416
void * key
Definition: searchTree.h:37
treeNode * TreeNodePredecessor(treeNode *node)
Definition: searchTree.cc:266
int ret
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
HKEY key
Definition: reg.c:42
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
treeNode * TreeNodeMinimum(treeNode *node)
Definition: searchTree.cc:220
#define max(a, b)
Definition: searchTree.cc:44
static calc_node_t temp
Definition: rpn_ieee.c:38
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
struct treeNode * parent
Definition: searchTree.h:38
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
#define malloc
Definition: debug_ros.c:4
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
treeNode * TreeNodeInsert(treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
Definition: searchTree.cc:106
void TreeNodePrint(treeNode *node, void(*keyPrint)(void *))
Definition: searchTree.cc:70
Definition: path.c:42
Definition: dlist.c:348