ReactOS  0.4.13-dev-92-gf251225
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 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
int ret
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
Definition: dlist.c:348

◆ TreeNodeDeleteWholeTree()

void TreeNodeDeleteWholeTree ( treeNode node)

Definition at line 62 of file searchTree.cc.

63 {
64  if(node == NULL) return;
68 }
smooth NULL
Definition: ftsmooth.c:416
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
Definition: dlist.c:348

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
smooth NULL
Definition: ftsmooth.c:416
#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 }
struct _tree tree
smooth NULL
Definition: ftsmooth.c:416
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
Definition: path.c:42

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 treeNode * left
Definition: searchTree.h:39
struct treeNode * right
Definition: searchTree.h:40
struct _root root
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
smooth NULL
Definition: ftsmooth.c:416
void * key
Definition: searchTree.h:37
struct treeNode * parent
Definition: searchTree.h:38
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548

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 assert(x)
Definition: debug.h:53
smooth NULL
Definition: ftsmooth.c:416
int ret
HKEY key
Definition: reg.c:42
#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 }
struct node node
smooth NULL
Definition: ftsmooth.c:416
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 }
struct node node
smooth NULL
Definition: ftsmooth.c:416
static calc_node_t temp
Definition: rpn_ieee.c:38

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
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
struct node node
smooth NULL
Definition: ftsmooth.c:416
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
Definition: dlist.c:348

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 }
smooth NULL
Definition: ftsmooth.c:416
void TreeNodePrint(treeNode *node, void(*keyPrint)(void *))
Definition: searchTree.cc:70
Definition: dlist.c:348

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 }
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
struct node node
smooth NULL
Definition: ftsmooth.c:416
treeNode * TreeNodeMinimum(treeNode *node)
Definition: searchTree.cc:220
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
Definition: dlist.c:348

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