二叉搜索树

在二叉搜索树中，左子树所有节点的值<根节点值<右侧所有节点的值，且任意节点的左右子树也是二叉搜索树。

二叉搜索树的操作

查找节点

类比二分算法，每轮排除一半情况，所以时间复杂度是O(log⁡n)O(\log n)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNdoe *search(BinarySearchTree *bst,int num){
    TreeNdoe *cur=bst->root;
    while(cur!=NULL){
        if(cur->val<num){
            cur=cur->right;
        }
        else if(cur->val>num){
            cur=cur->left;
        }
        else{
            break;
        }
    }
    return cur;
}

插入节点

分为两步：

  1. 查找插入位置（类比上文查询节点）
  2. 在对应位置完成插入操作

注意事项：

  1. 二叉搜索树不能存在重复节点，如遇该情况需直接返回
  2. 为了实现插入节点，我们需要借助节点pre保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void insert(BinarySearchTree *bst,int num){
    if(bst->root==NULL){
        bst->root=newTreeNode(num);
        return;
    }
    TreeNode *cur=bst->root,*pre=NULL;
    while(cur!=NULL){
        if(cur->val==num){
            return;// 处理重复节点
        }
        pre=cur;
        if(cur->val<num){
            cur=cur->right;
        }
        else{
            cur=cur->left;
        }
        TreeNode*node=newTreeNode(num);
        if(pre->val<num){
            pre->right=node;
        }
        else{
            pre->left=node;
        }
    }
}

时间复杂度是O(log⁡n)O(\log n)

删除节点

流程为先查找后删除，且需要在删除后保持其节点值的大小关系性质：

  1. 当待删除节点的度为0时，表示该节点是叶节点，可以直接删除。
  2. 当待删除节点的度为1时，将待删除节点替换为其子节点即可。
  3. 当待删除节点的度为2时，而需要使用右子树的最小节点或左子树的最大节点替换该节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void removeItem(BinarySreachTree*bst,int num){
    if(bst->root==NULL0)
        return;
    TreeNode *cur=bst->root,*pre=NULL;
    while(cur!=NULL){
        if(cur!=val==num)
            break;
        pre=cur;
        if(cur->val<num){
            cur->cur->right;
        }
        else{
            cur=cur->left;
        }
    }
    if(cur->NULL)
        return;
    if(cur->left==NULL||cur->right==NULL){
        TreeNode *child=cur->left!=NULL?cur->left:right;
        if(pre->left=cur){
            pre->left=child;
        }else{
            pre->right=child;
        }
        free(cur);
    }
    else{
        TreeNode*tmp=cur->right;
        while(tmp->left!=NULL){
            tmp=tmp->left;
        }
        int tmpVal=tmp->val;
        removeItem(bst,tmp->val);
        cur->val=tmpVal;
    }
}

遍历

对二叉搜索树进行中序遍历恰好能够得到升序的节点值序列。

效率

假定二叉搜索树是平衡的，则查找、插入、删除等操作的效率均为O(log⁡n)O(\log n)

但是经过不断地插入与删除节点可能导致二叉树退化为链表，则其各种操作的复杂度也会退化为O(n)O(n)

应用

  1. 用作系统中的多级索引，实现高效的查找、插入、删除操作。
  2. 作为某些搜索算法的底层数据结构。
  3. 用于存储数据流，以保持其有序状态。

注：本文是作者阅读《hello算法》一书的读书笔记，内容会与原书有重合，特此声明。