//return the maxest node of tree
BST *bst_maxinum(BST *root)
{
if(root == NULL)
return NULL;
while(root->right!=NULL)
root = root->right;
return root;
}
注，以上两个算法的时间复杂度都是O(logn) (n为输得节点的个数)

节点的前驱和后继
给定一棵二叉搜索树的一个节点，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个节点x的后继是大于x.key的最小关键字的节点。
查找前驱过程分为两部分：1. 如果x的右子树非空，那么x的后继则是x右子树的最左节点；2. 如果x的右子树为空且有一个后继节点y，那么y就是最底层祖先并且其左孩子也是一个祖先。为了找到y，只需从x开始沿树而上知道遇到一个其双亲有左孩子的节点
查找节点的前驱则先判断x节点的左子树是否为空，非空则前驱就是左子树的最右节点，空则从x沿树而上直到遇到一个其双亲都有右孩子的节点，那么该节点就是x的前驱结点
下面为实现代码
[cpp]
BST *bst_successor(BST *node)
{
if(node == NULL)
return NULL;
if(node->right!=NULL) //find successor in the leftest of the right subtree
return bst_mininum(node->right);
//else find it a node leftSubTree from his parent
BST *y = node->parent;
while(y!=NULL && node==y->right)
{
node = y;
y = y->parent;
}
return y;
}

BST *bst_predecessor(BST *node)
{
if(node == NULL)
return NULL;
if(node->left!=NULL)
return bst_maxinum(node->left);
BST *y = node->parent;
while(y!=NULL && node==y->left)
{
node = y;
y = y->parent;
}
return y;
}

BST *bst_successor(BST *node)
{
if(node == NULL)
return NULL;
if(node->right!=NULL) //find successor in the leftest of the right subtree
return bst_mininum(node->right);
//else find it a node leftSubTree from his parent
BST *y = node->parent;
while(y!=NULL && node==y->right)
{
node = y;
y = y->parent;
}
return y;
}

BST *bst_predecessor(BST *node)
{
if(node == NULL)
return NULL;
if(node->left!=NULL)
return bst_maxinum(node->left);
BST *y = node->parent;
while(y!=NULL && node==y->left)
{
node = y;
y = y->parent;
}
return y;
}
树的插入与删除
树的插入与删除操作会引起二叉搜索树表示的动态集合的变化，一定要修改数据结构来反映这个变化，但修改要保持二叉树搜索树的性质的成立
插入
要将一个新值插入到一棵二叉搜索树T中，需要调用bst_insert。该函数以关键字v作为输入，在函数构造节点node，并将node->left=NULL,node->right=NULL
插入过程为：从树根开始，指针node记录一条向下的简单路锦，并查找要替换新节点insert的NULL，该遍历保持tmo作为node的双亲
[cpp]
//insert a node into a binary-search-tree
BST *bst_insert(BST *root, data_t data)
{
BST *insert = NULL, *node = NULL, *tmp = NULL;
insert = bst_newnode(data); //make a node to insert

node = root;
while(node) //find pos to insert
{
tmp = node;
if(data < node->data)
node = node->left;
else
node = node->right;
}

insert->parent = tmp;
if(tmp==NULL) //tree root is empty
root = insert;
else
{
if(data < tmp->data)
tmp->left = insert;
else
tmp->right = insert;
}

return root;
}

//insert a node into a binary-search-tree
BST *bst_insert(BST *root, data_t data)
{
BST *insert = NULL, *node = NULL, *tmp = NULL;
insert = bst_newnode(data); //make a node to insert

node = root;
while(node) //find pos to insert
{
tmp = node;
if(data < node->data)
node = node->left;
else
node = node->right;
}

insert->parent = tmp;
if(tmp==NULL) //tree root is empty
root = insert;
else
{
if(data < tmp->data)
tmp->left = insert;
else
tmp->right = insert;
}

return root;
}