searchTree.cc revision f220fa62 
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
46treeNode* TreeNodeMake(void *key)
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
57void TreeNodeDeleteSingleNode(treeNode* node)
58{
59  free(node);
60}
61
62void TreeNodeDeleteWholeTree(treeNode* node)
63{
64  if(node == NULL) return;
65  TreeNodeDeleteWholeTree(node->left);
66  TreeNodeDeleteWholeTree(node->right);
67  TreeNodeDeleteSingleNode(node);
68}
69
70void TreeNodePrint(treeNode* node,
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
79int TreeNodeDepth(treeNode* root)
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 */
92treeNode* TreeNodeFind(treeNode* tree, void* key,
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
106treeNode* TreeNodeInsert(treeNode* root, treeNode* newnode,
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
142treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node)
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
173     y = TreeNodeSuccessor(node);
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*/
213  TreeNodeDeleteSingleNode(node);
214  return ret;
215}
216
217
218/*the minimum node in the tree rooted by node
219 */
220treeNode* TreeNodeMinimum(treeNode* node)
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 */
232treeNode* TreeNodeMaximum(treeNode* node)
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 */
244treeNode* TreeNodeSuccessor(treeNode* node)
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 */
266treeNode* TreeNodePredecessor(treeNode* node)
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}
283