ReactOS 0.4.15-dev-8138-g1e75ea8
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}
struct _root root
struct _tree tree
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
static calc_node_t temp
Definition: rpn_ieee.c:38
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
treeNode * TreeNodeMaximum(treeNode *node)
Definition: searchTree.cc:232
treeNode * TreeNodePredecessor(treeNode *node)
Definition: searchTree.cc:266
treeNode * TreeNodeMinimum(treeNode *node)
Definition: searchTree.cc:220
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
treeNode * TreeNodeMake(void *key)
Definition: searchTree.cc:46
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
treeNode * TreeNodeInsert(treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
Definition: searchTree.cc:106
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
void TreeNodePrint(treeNode *node, void(*keyPrint)(void *))
Definition: searchTree.cc:70
int TreeNodeDepth(treeNode *root)
Definition: searchTree.cc:79
#define max(a, b)
Definition: searchTree.cc:44
Definition: copy.c:22
struct treeNode * right
Definition: searchTree.h:40
struct treeNode * parent
Definition: searchTree.h:38
void * key
Definition: searchTree.h:37
struct treeNode * left
Definition: searchTree.h:39
Definition: dlist.c:348
int ret