定义
二叉查找树(Binary Search Tree)，又叫二叉排序树或二叉搜索树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左右子树也分别为二叉排序树。
二叉排序树
操作
BST的节点结构和普通二叉树没有区别
class Node {
int data; // 数据域
Node left; // 左孩子
Node right; // 右孩子
}
插入
向一颗BST中插入节点p，如果是一颗空树，则p就是树的根节点，否则判断根节点的数据域与p的数据域，如果p的数据域大，则在根节点的右子树中插入节点p，否则在根节点的左子树中插入节点p，递归执行上述流程，直至p插入完成。
伪代码
function insertNode(root, p) {
if root is null:
root = p;
return;
if root.data > p.data:
root = root.left;
else:
root = root.right;
insertNode(root, p);
}
查找
查找操作类似二分查找，先判断根节点，若根节点为空，则返回false，如果根节点的数据域等于p的数据域，则返回true，如果根节点的数据域大于p的数据域，则在根的左子树中查找，否则在根的右子树中查找。
伪代码
function searchNode(root, key){
if root is null:
return null;
if root.data = key:
return root;
else if root.data > key:
searchNode(root->left, key);
else :
searchNode(root->right, key);
}
前驱、后继节点
- 前驱节点指小于给定节点p的节点中最大的节点，一般情况下，前驱节点是节点p的左子树的最右节点，若左子树为空，则是p的右孩子。
- 后继节点指大于给定节点p的节点中最小的节点，一般情况下，后继节点是节点p的右子树的最左节点，若右子树为空，则是p的左孩子。
后继节点伪代码
function nextNode(root, key) {
if root->right is null:
return root->left;
root = root->right;
while(root->left is not null):
root = root->left;
return root;
}
删除
删除节点操作相对于插入和查找操作来说要复杂很多，要分不同的情况进行讨论：
- 删除节点是叶子节点
- 删除节点非叶子节点，且仅有左孩子
- 删除节点非叶子节点，且仅有右孩子
- 删除节点非叶子节点，且既有左孩子又有右孩子
- 对于情况1，则直接删除节点即可。
- 对于情况2，将p的左孩子代替p即可。
- 对于情况3，将p的右孩子代替p即可。
- 对于情况4，需要先找到p的后继节点n，使用n代替p即可。
function deleteNode(root, p){
if p->left is null and p->right is null:
delete p from parent(p)
else if p->left is not null and p->right is null:
parent(p) link to p->left
delete p
else if p->left is null and p->right is not null:
parent(p) link to p->right
delete p
else:
n = nextNode(root, p)
parent(n) link to n->right
parent(p) link to n
delete p
}
总结分析
- BST的中序遍历结果就是根据大小排好序的。
- BST中的数据不能重复。
- 使用BST查询数据时，比较次数与树的高度有关
- 在好的情况下，查询时间复杂度为O(log(N))
- 在最坏情况下的时间复杂度为O(N)，此时二叉树退化成单链表
- 相对于顺序数组的二分查找，无需开辟连续内存空间，最好时间复杂度都是O(N)。
- 如何解决最坏情况下退化成链表的问题呢，这就需要使用二叉平衡树、红黑树等有限制的二叉排序树了。
- BST与大(小)顶堆的区别在于，后者的根节点小于左右孩子，但是并不要求左子树中的节点都小于右子树的所有节点。
