#include <stdlib.h>
#include <stdio.h>
#include "zlassert.h"
#include "searchTree.h"
#define max(a,b) ((a>b)? a:b)
treeNode* TreeNodeMake(void *key)
{
treeNode *ret = (treeNode*) malloc(sizeof(treeNode));
assert(ret);
ret->key = key;
ret->parent = NULL;
ret->left = NULL;
ret->right = NULL;
return ret;
}
void TreeNodeDeleteSingleNode(treeNode* node)
{
free(node);
}
void TreeNodeDeleteWholeTree(treeNode* node)
{
if(node == NULL) return;
TreeNodeDeleteWholeTree(node->left);
TreeNodeDeleteWholeTree(node->right);
TreeNodeDeleteSingleNode(node);
}
void TreeNodePrint(treeNode* node,
void (*keyPrint) (void*))
{
if(node ==NULL) return;
TreeNodePrint(node->left, keyPrint);
keyPrint(node->key);
TreeNodePrint(node->right, keyPrint);
}
int TreeNodeDepth(treeNode* root)
{
if(root == NULL) return 0;
else{
int leftdepth = TreeNodeDepth(root->left);
int rightdepth = TreeNodeDepth(root->right);
return 1 + max(leftdepth, rightdepth);
}
}
treeNode* TreeNodeFind(treeNode* tree, void* key,
int (*compkey) (void*, void*))
{
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);
}
treeNode* TreeNodeInsert(treeNode* root, treeNode* newnode,
int (*compkey) (void *, void *))
{
treeNode *y = NULL;
treeNode *x = root;
while (x != NULL){
y = x;
if(compkey(newnode->key,x->key) < 0)
x = x->left;
else
x = x->right;
}
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;
}
treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node)
{
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)
ret = x;
else
{
if(y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
ret = tree;
}
}
else {
y = TreeNodeSuccessor(node);
assert(y->left == NULL);
if(y == node->right)
{
y->parent = node->parent;
y->left = node->left;
node->left->parent = y;
}
else
{
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;
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;
}
else
ret = y;
}
TreeNodeDeleteSingleNode(node);
return ret;
}
treeNode* TreeNodeMinimum(treeNode* node)
{
treeNode* temp = node;
if(temp == NULL) return NULL;
while(temp->left != NULL) {
temp = temp->left;
}
return temp;
}
treeNode* TreeNodeMaximum(treeNode* node)
{
treeNode* temp = node;
if(temp == NULL) return NULL;
while(temp->right != NULL) {
temp = temp->right;
}
return temp;
}
treeNode* TreeNodeSuccessor(treeNode* node)
{
if(node == NULL) return NULL;
if(node->right != NULL)
return TreeNodeMinimum(node->right);
else{
treeNode *y = node->parent;
treeNode* x = node;
while(y != NULL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
}
treeNode* TreeNodePredecessor(treeNode* node)
{
if(node == NULL) return NULL;
if(node->left != NULL)
return TreeNodeMaximum(node->left);
else{
treeNode *y = node->parent;
treeNode *x = node;
while(y != NULL && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
}