ReactOS 0.4.15-dev-8339-g4028de8
searchTree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  treeNode
 

Typedefs

typedef struct treeNode treeNode
 

Functions

treeNodeTreeNodeMake (void *key)
 
void TreeNodeDeleteSingleNode (treeNode *node)
 
void TreeNodeDeleteWholeTree (treeNode *node)
 
void TreeNodePrint (treeNode *node, void(*keyPrint)(void *))
 
int TreeNodeDepth (treeNode *root)
 
treeNodeTreeNodeMinimum (treeNode *node)
 
treeNodeTreeNodeMaximum (treeNode *node)
 
treeNodeTreeNodePredecessor (treeNode *node)
 
treeNodeTreeNodeSuccessor (treeNode *node)
 
treeNodeTreeNodeFind (treeNode *tree, void *key, int(*compkey)(void *, void *))
 
treeNodeTreeNodeInsert (treeNode *root, treeNode *newnode, int(*comp)(void *, void *))
 
treeNodeTreeNodeDeleteSingleNode (treeNode *tree, treeNode *node)
 

Typedef Documentation

◆ treeNode

Function Documentation

◆ TreeNodeDeleteSingleNode() [1/2]

void TreeNodeDeleteSingleNode ( treeNode node)

Definition at line 57 of file searchTree.cc.

58{
59 free(node);
60}
#define free
Definition: debug_ros.c:5
Definition: dlist.c:348

Referenced by MC_sweepY(), sweepY(), TreeNodeDeleteSingleNode(), and TreeNodeDeleteWholeTree().

◆ TreeNodeDeleteSingleNode() [2/2]

treeNode * TreeNodeDeleteSingleNode ( treeNode tree,
treeNode node 
)

Definition at line 142 of file searchTree.cc.

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}
struct _tree tree
#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
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
int ret

◆ TreeNodeDeleteWholeTree()

void TreeNodeDeleteWholeTree ( treeNode node)

Definition at line 62 of file searchTree.cc.

63{
64 if(node == NULL) return;
68}
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62

Referenced by MC_sweepY(), sweepY(), and TreeNodeDeleteWholeTree().

◆ TreeNodeDepth()

int TreeNodeDepth ( treeNode root)

Definition at line 79 of file searchTree.cc.

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}
int TreeNodeDepth(treeNode *root)
Definition: searchTree.cc:79
#define max(a, b)
Definition: searchTree.cc:44

Referenced by TreeNodeDepth().

◆ TreeNodeFind()

treeNode * TreeNodeFind ( treeNode tree,
void key,
int(*)(void *, void *)  compkey 
)

Definition at line 92 of file searchTree.cc.

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}
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
Definition: copy.c:22

Referenced by MC_sweepY(), sweepY(), and TreeNodeFind().

◆ TreeNodeInsert()

treeNode * TreeNodeInsert ( treeNode root,
treeNode newnode,
int(*)(void *, void *)  comp 
)

Definition at line 106 of file searchTree.cc.

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}
struct _root root
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

Referenced by MC_sweepY(), and sweepY().

◆ TreeNodeMake()

treeNode * TreeNodeMake ( void key)

Definition at line 46 of file searchTree.cc.

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}
#define malloc
Definition: debug_ros.c:4

Referenced by MC_sweepY(), and sweepY().

◆ TreeNodeMaximum()

treeNode * TreeNodeMaximum ( treeNode node)

Definition at line 232 of file searchTree.cc.

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}
static calc_node_t temp
Definition: rpn_ieee.c:38

Referenced by TreeNodePredecessor().

◆ TreeNodeMinimum()

treeNode * TreeNodeMinimum ( treeNode node)

Definition at line 220 of file searchTree.cc.

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}

Referenced by TreeNodeSuccessor().

◆ TreeNodePredecessor()

treeNode * TreeNodePredecessor ( treeNode node)

Definition at line 266 of file searchTree.cc.

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 * TreeNodeMaximum(treeNode *node)
Definition: searchTree.cc:232

Referenced by MC_sweepY(), and sweepY().

◆ TreeNodePrint()

void TreeNodePrint ( treeNode node,
void(*)(void *)  keyPrint 
)

Definition at line 70 of file searchTree.cc.

72{
73 if(node ==NULL) return;
74 TreeNodePrint(node->left, keyPrint);
75 keyPrint(node->key);
76 TreeNodePrint(node->right, keyPrint);
77}
void TreeNodePrint(treeNode *node, void(*keyPrint)(void *))
Definition: searchTree.cc:70

Referenced by TreeNodePrint().

◆ TreeNodeSuccessor()

treeNode * TreeNodeSuccessor ( treeNode node)

Definition at line 244 of file searchTree.cc.

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}
treeNode * TreeNodeMinimum(treeNode *node)
Definition: searchTree.cc:220

Referenced by MC_sweepY(), sweepY(), and TreeNodeDeleteSingleNode().