The range query function's skipped because I haven't decided in what form to return the results.
/**
* Here I present a full impl of a binary search tree ADT in C.
*/
typedef struct BSTNodeStruct {
struct BSTNodeStruct *left;
struct BSTNodeStruct *right;
int key;
int value;
int count;
}*BSTNode;
typedef BSTNode BSTree;
BSTree BSTreeCreate(int key, int val) {
BSTree bst = (BSTree)malloc(sizeof(*bst));
bst->left = bst->right = NULL;
bst->value = val;
bst->key = key;
bst->count = 1;
return bst;
}
void BSTNodeRelease(BSTNode node) { if (node != NULL) free(node); }
void BSTreeRelease(BSTree bst) {
if (bst == NULL) return;
if (bst->left != NULL) BSTreeRelease(bst->left);
if (bst->right != NULL) BSTreeRelease(bst->right);
BSTNodeRelease(bst);
}
int BSTreeCount(BSTree bst) { return bst == NULL ? 0 : bst->count; }
int BSTreeGet(BSTree bst, int key) {
if (bst == NULL) return INT_MIN;
int com = key - bst->key;
if (com < 0) {
return BSTreeGet(bst->left, key);
} else if (com > 0) {
return BSTreeGet(bst->right, key);
} else {
return bst->value;
}
}
BSTree BSTreeSet(BSTree bst, int key, int val) {
if (bst == NULL) return BSTreeCreate(key, val);
int com = key - bst->key;
if (com < 0) {
bst->left = BSTreeSet(bst->left, key, val);
} else if (com > 0) {
bst->right = BSTreeSet(bst->right, key, val);
} else {
bst->value = val;
}
bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
return bst;
}
BSTNode BSTreeMin(BSTree bst) {
if (bst == NULL) return NULL;
if (bst->left == NULL) {
return bst;
} else {
return BSTreeMin(bst->left);
}
}
BSTNode BSTreeMax(BSTree bst) {
if (bst == NULL) return NULL;
if (bst->right == NULL) {
return bst;
} else {
return BSTreeMax(bst->right);
}
}
int BSTreeFloor(BSTree bst, int key) {
if (bst == NULL) return INT_MIN;
int com = key - bst->key;
if (com < 0) {
return BSTreeFloor(bst->left, key);
} else if (com > 0) {
int floor = BSTreeFloor(bst->right, key);
return floor == INT_MIN ? bst->key : floor;
} else {
return bst->key;
}
}
int BSTreeCeiling(BSTree bst, int key) {
if (bst == NULL) return INT_MIN;
int com = key - bst->key;
if (com < 0) {
int ceiling = BSTreeCeiling(bst->left, key);
return ceiling == INT_MIN ? bst->key : ceiling;
} else if (com > 0) {
return BSTreeCeiling(bst->right, key);
} else {
return bst->key;
}
return 0;
}
/**
* The definitions of rank&selection are somewhat confusing...
*/
int BSTreeSelect(BSTree bst, int rank) {
if (bst == NULL) return INT_MIN;
int count = BSTreeCount(bst->left);
if (rank < count) {
return BSTreeSelect(bst->left, rank);
} else if (rank > count) {
return BSTreeSelect(bst->right, rank - 1 - count);
} else {
return bst->key;
}
}
int BSTreeRank(BSTree bst, int key) {
if (bst == NULL) return 0;
int com = key - bst->key;
if (com < 0) {
return BSTreeRank(bst->left, key);
} else if (com > 0) {
return BSTreeRank(bst->right, key) + 1 + (bst->left != NULL ? bst->left->count : 0);
} else {
return bst->left == NULL ? 0 : bst->left->count;
}
}
BSTNode BSTreeDeleteMin(BSTree bst) {
if (bst == NULL) return NULL;
if (bst->left == NULL) {
if (bst->right == NULL) {//last node
free(bst);
return NULL;
} else {
return bst->right;
}
} else {
BSTNode x = bst->left;
bst->left = BSTreeDeleteMin(bst->left);
bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
if (x != bst->left) { BSTNodeRelease(x); }
return bst;
}
}
BSTNode BSTreeDeleteMax(BSTree bst) {
if (bst == NULL) return NULL;
if (bst->right == NULL) {
if (bst->left == NULL) {//last node
free(bst);
return NULL;
} else {
return bst->left;
}
} else {
BSTNode x = bst->right;
bst->right = BSTreeDeleteMax(bst->right);
bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
if (x != bst->right) { BSTNodeRelease(x); }
return bst;
}
}
/**
* The deletion process work by moving the contents of the min node in the right sub bst and delete this min node.
*/
BSTNode BSTreeDelete(BSTree bst, int key) {
if (bst == NULL) return NULL;
if (key < bst->key) {
bst->left = BSTreeDelete(bst->left, key);
} else if (key > bst->key) {
bst->right = BSTreeDelete(bst->right, key);
} else {
if (bst->left == NULL) {
BSTNodeRelease(bst);
return bst->right;
}
if (bst->right == NULL) {
BSTNodeRelease(bst);
return bst->left;
}
//The order of the following instructions can not be changed.
BSTNode t = bst;
bst = BSTreeMin(bst->right);
bst->right = BSTreeDeleteMin(t->right);
bst->left = t->left;
}
bst->count = BSTreeCount(bst->left) + BSTreeCount(bst->right) + 1;
return bst;
}
#define L -1
#define R 1
#define P 0
void BSTreePrintLevel(BSTree bst, int level, int k) {
if (bst == NULL) return;
int i = level;
while (i-- > 0) { printf("-"); }
printf("{%s %i: %i; %i %s}\n", k == L ? "'" : "", bst->key, bst->value, bst->count, k == R ? "'" : "");
if (bst->left != NULL) { BSTreePrintLevel(bst->left, level + 1, L); }
if (bst->right != NULL) { BSTreePrintLevel(bst->right, level + 1, R); }
}
void BSTreePrint(BSTree bst) {
if (bst == NULL) return;
BSTreePrintLevel(bst, 0, P);
}
网友评论