二叉搜索树

定义

二叉查找树(Binary Search Tree)，又叫二叉排序树或二叉搜索树，它或者是一棵空树，或者是具有以下性质的二叉树：

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树。

二叉排序树

操作

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. 删除节点非叶子节点，且仅有左孩子
3. 删除节点非叶子节点，且仅有右孩子
4. 删除节点非叶子节点，且既有左孩子又有右孩子

• 对于情况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与大(小)顶堆的区别在于，后者的根节点小于左右孩子，但是并不要求左子树中的节点都小于右子树的所有节点。