searchTree.cc File Reference

#include <stdlib.h>
#include "zlassert.h"
#include "searchTree.h"

Include dependency graph for searchTree.cc:

Go to the source code of this file.

Macros
#define	max(a, b)   ((a>b)? a:b)

Functions
treeNode *	TreeNodeMake (void *key)
void	TreeNodeDeleteSingleNode (treeNode *node)
void	TreeNodeDeleteWholeTree (treeNode *node)
void	TreeNodePrint (treeNode *node, void(*keyPrint)(void *))
int	TreeNodeDepth (treeNode *root)
treeNode *	TreeNodeFind (treeNode *tree, void *key, int(*compkey)(void *, void *))
treeNode *	TreeNodeInsert (treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
treeNode *	TreeNodeDeleteSingleNode (treeNode *tree, treeNode *node)
treeNode *	TreeNodeMinimum (treeNode *node)
treeNode *	TreeNodeMaximum (treeNode *node)
treeNode *	TreeNodeSuccessor (treeNode *node)
treeNode *	TreeNodePredecessor (treeNode *node)

Macro Definition Documentation

max

#define max	(		a,
			b
	)		((a>b)? a:b)

Definition at line 44 of file searchTree.cc.

Function Documentation

TreeNodeDeleteSingleNode() [1/2]

void TreeNodeDeleteSingleNode

(

treeNode *

node

)

Definition at line 57 of file searchTree.cc.

{
  free(node);
}

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.

{
  treeNode* y;
  treeNode* x;
  treeNode* ret;
  if(node==NULL) return tree;
 
  if(node->left == NULL || node->right == NULL) {
 
    y = node;
    if(y->left != NULL) 
      x = y->left;
    else
      x = y->right;
 
    if( x != NULL)
      x->parent = y->parent;
 
    if(y->parent == NULL) /*y is the root which has at most one child x*/
      ret = x;
    else /*y is not the root*/
      {
    if(y == y->parent->left) 
      y->parent->left = x;
    else
      y->parent->right = x;
    ret =  tree;
      }
  }
  else { /*node has two children*/
 
     y = TreeNodeSuccessor(node);
     assert(y->left == NULL);
 
     if(y == node->right) /*y is the right child if node*/
       {
     y->parent = node->parent;
     y->left = node->left;
     node->left->parent = y;
     
       }
     else  /*y != node->right*/
       {
     x = y->right;
     if(x!= NULL)
       x->parent = y->parent;
 
     assert(y->parent != NULL);
     if(y == y->parent->left) 
       y->parent->left = x;
     else
       y->parent->right = x;
     /*move y to the position of node*/
     y->parent = node->parent;
     y->left = node->left;
     y->right = node->right;
     node->left->parent = y;
     node->right->parent = y;
       }
    if(node->parent != NULL) {
      if(node->parent->left == node)
    node->parent->left = y;
      else
    node->parent->right = y;
      ret = tree; /*the root if the tree doesn't change*/
    }
    else /*node->parent is NULL: node is the root*/
      ret = y;    
  }
 
  /*finally free the node, and return the new root*/
  TreeNodeDeleteSingleNode(node);
  return ret;
}

TreeNodeDeleteWholeTree()

void TreeNodeDeleteWholeTree

(

treeNode *

node

)

Definition at line 62 of file searchTree.cc.

{
  if(node == NULL) return;
  TreeNodeDeleteWholeTree(node->left);
  TreeNodeDeleteWholeTree(node->right);
  TreeNodeDeleteSingleNode(node);
}

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

TreeNodeDepth()

int TreeNodeDepth

(

treeNode *

root

)

Definition at line 79 of file searchTree.cc.

{
  if(root == NULL) return 0;
  else{
    int leftdepth = TreeNodeDepth(root->left);
    int rightdepth = TreeNodeDepth(root->right);  
    return 1 + max(leftdepth, rightdepth);
  }
}

Referenced by TreeNodeDepth().

TreeNodeFind()

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

Definition at line 92 of file searchTree.cc.

{
  if(tree == NULL) 
    return NULL;
  if(key == tree->key)
    return tree;
  else if(compkey(key, tree->key) < 0)
    return TreeNodeFind(tree->left, key, compkey);
  else 
    return TreeNodeFind(tree->right, key, compkey);    
}

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

TreeNodeInsert()

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

Definition at line 106 of file searchTree.cc.

{
  treeNode *y = NULL;
  treeNode *x = root;
  /*going down the tree from the root.
   *x traces the path, y is the parent of x.
   */
  while (x != NULL){
    y = x;
    if(compkey(newnode->key,x->key) < 0) /*if newnode < x*/
      x = x->left;
    else 
      x = x->right;
  }
 
  /*now y has the property that 
   * if newnode < y, then y->left is NULL
   * if newnode > y, then y->right is NULL.
   *So we want to isnert newnode to be the child of y
   */
  newnode->parent = y;
  if(y == NULL) 
    return newnode;
  else if( compkey(newnode->key, y->key) <0)
    {
      y->left = newnode;
    }
  else
    {
      y->right = newnode;
    }
 
  return root;
}

Referenced by MC_sweepY(), and sweepY().

TreeNodeMake()

treeNode * TreeNodeMake

(

void *

key

)

Definition at line 46 of file searchTree.cc.

{
  treeNode *ret = (treeNode*) malloc(sizeof(treeNode));
  assert(ret);
  ret->key = key;
  ret->parent = NULL;
  ret->left = NULL;
  ret->right = NULL;
  return ret;
}

Referenced by MC_sweepY(), and sweepY().

TreeNodeMaximum()

treeNode * TreeNodeMaximum

(

treeNode *

node

)

Definition at line 232 of file searchTree.cc.

{
  treeNode* temp = node;
  if(temp == NULL) return NULL;
  while(temp->right != NULL) {
    temp = temp->right;
  }
  return temp;
}

Referenced by TreeNodePredecessor().

TreeNodeMinimum()

treeNode * TreeNodeMinimum

(

treeNode *

node

)

Definition at line 220 of file searchTree.cc.

{
  treeNode* temp = node;
  if(temp == NULL) return NULL;
  while(temp->left != NULL) {
    temp = temp->left;
  }
  return temp;
}

Referenced by TreeNodeSuccessor().

TreeNodePredecessor()

treeNode * TreeNodePredecessor

(

treeNode *

node

)

Definition at line 266 of file searchTree.cc.

{
  if(node == NULL) return NULL;
  if(node->left != NULL)
    return TreeNodeMaximum(node->left);
  else{ /*node->left is NULL*/
    /*find the first left-ancestor*/
    treeNode *y = node->parent;
    treeNode *x = node;
    while(y != NULL && x == y->left) /*if y is a right parent of x*/
      {
    x = y;
    y = y->parent;
      }
    return y;
  }
}

Referenced by MC_sweepY(), and sweepY().

TreeNodePrint()

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

Definition at line 70 of file searchTree.cc.

{
  if(node ==NULL) return;
  TreeNodePrint(node->left, keyPrint);
  keyPrint(node->key);
  TreeNodePrint(node->right, keyPrint);  
}

Referenced by TreeNodePrint().

TreeNodeSuccessor()

treeNode * TreeNodeSuccessor

(

treeNode *

node

)

Definition at line 244 of file searchTree.cc.

{
  if(node == NULL) return NULL;
  if(node->right != NULL)
    return TreeNodeMinimum(node->right);
  else{ /*node->right is NULL*/
 
    /*find the first right-ancestor*/
    treeNode *y = node->parent;
    treeNode* x = node;
    while(y != NULL && x == y->right) /*if y is a left parent of x*/
      {
 
    x = y;
    y = y->parent;
      }
    return y;
  }
}

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