简介

二叉查找树（Binar Search Tree），又名二叉搜索树，是指一颗空树或具有下列性质的二叉树：

对于树上任意一个节点，满足

  • 若其左子树不为空，则其左子树所有节点的值均小于该节点的值。
  • 若其右子树不为空，则其右子树所有节点的值均大于该节点的值。
  • 其左右子树均为二叉查找树。

二叉查找树的中序遍历是一个有序序列。

image.png

基本操作

查找

查找值为x，从根节点root出发：

  • 若root == NULL，查找失败。
  • 若x == root->data，查找成功。
  • 若x < root->data，则搜索其左子树，令root=root->left。
  • 若x > root->data，则搜索其右子树，令root=root->right。

插入

插入节点为s，从根节点root出发：

  • 若root == NULL，x作为root插入。
  • 若s->data == root->data，则不需要插入，直接返回。
  • 若s->data < root->data，则搜索其左子树，令root=root->left。
  • 若s->data > root->data，则搜索其右子树，令root=root->right。

image.png

删除

删除节点p分三种情况讨论：

  1. 若删除叶子节点，即节点p没有左右儿子，删去之后不会破坏二叉搜索树的结构，直接删去即可。
    image.png
  2. 若节点p只有左儿子或只有右儿子，同样直接删去，令p的儿子替代p。
    image.png
  3. 若节点p既有左儿子，又有右儿子，有两种做法：
    • 令右儿子接在左子树最右下的节点（中序遍历最后一个节点），成为其右子树，让左儿子替代p。同理反过来也可以。
    • 让节点p的前驱（后继）替代p，然后删去节点p的前驱（后继）。
    • 图有问题，忽略节点7
      image.png
      image.png

前驱节点为值小于该节点，且值最大的节点。
后继节点为值大于该节点，且值最小的节点。
即为二叉查找树中序遍历的前一个或后一个节点。

复杂度分析

很容易发现二叉查找树的性能取决于树的深度。

最优情况下查询，插入，删除的复杂度为O(log_n)。

最坏情况下插入序列为一个有序序列，此时二叉树退化成了一条链，每次操作的复杂度达到了O(n)。

那么我们为了实现更高效的查询，会在插入的时候平衡左右子树的高度，具体实现可以看AVL树，红黑树。