跳到主要内容

二叉搜索树（BST）

提示
  1. 基本特性：二叉搜索树是每个节点最多有两个子节点的数据结构，左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
  2. 搜索效率：二叉搜索树支持高效的搜索操作，平均和最佳情况下的时间复杂度为 O(log n)，最坏情况下为 O(n)。
  3. 广泛应用：二叉搜索树在数据库的多级索引、动态数据排序和Unix内核的虚拟内存管理等领域有广泛应用。

二叉搜索树是一种数据结构，能够快速帮助我们维护一个有序的数字列表。

  • 之所以称为二叉树，是因为每个树节点最多有两个子节点。
  • 之所以称为搜索树，是因为它可以用来在 O(log(n)) 时间内搜索一个数字的存在。

区分二叉搜索树和普通二叉树的特性是

  1. 左子树的所有节点都小于根节点
  2. 右子树的所有节点都大于根节点
  3. 每个节点的两个子树也都是 BSTs，即它们都具有上述两个特性

显示具有一个小于根值的右子树的树，以证明它不是有效的二叉搜索树

右边的二叉树不是二叉搜索树，因为节点“3”的右子树包含一个小于它的值。

你可以在二叉搜索树上执行两个基本操作：

搜索操作​

该算法取决于 BST 的特性，即每个左子树的值都低于根，每个右子树的值都高于根。

如果值低于根，我们可以确定该值不在右子树中；我们只需要在左子树中搜索，如果值高于根，我们可以确定该值不在左子树中；我们只需要在右子树中搜索。

算法：

如果 root == NULL
    返回 NULL;
如果 number == root->data
    返回 root->data;
如果 number < root->data
    返回 search(root->left)
如果 number > root->data
    返回 search(root->right)

让我们通过图表来直观地理解这一点。

4 未找到，因此遍历 8 的左子树

4 未找到，因此遍历 3 的右子树

4 未找到，因此遍历 6 的左子树

找到了 4

如果找到了该值，我们返回该值，以便在每个递归步骤中传播，如下图所示。

如果你注意到了，我们已经调用了四次 return search(struct node*)。当我们返回新节点或 NULL 时，这个值会再次被返回，直到 search(root) 返回最终结果。

如果在任何子树中找到了该值，它会被向上传播，以便最终返回，否则返回 null

如果未找到该值，我们最终会到达叶节点的左或右子节点，这些节点为 NULL，并且会被传播并返回。

插入操作​

将一个值插入到正确的位置类似于搜索，因为我们试图维护左子树小于根，右子树大于根的规则。

我们根据值的大小不断地向右子树或左子树移动，当我们到达一个左子树或右子树为 null 的点时，我们在那里放置新节点。

算法：

如果 node == NULL
    返回 createNode(data)
如果 (data < node->data)
    node->left  = insert(node->left, data);
否则如果 (data > node->data)
    node->right = insert(node->right, data);
返回 node;

这个算法看起来并不简单。让我们尝试通过图形化来理解我们如何将一个数字添加到现有的 BST 中。

4&lt;8 所以，遍历 8 的左子节点

4&gt;3 所以，遍历 4 的右子节点

4&lt;6 所以，遍历 6 的左子节点

将 4 插入为 6 的左子节点

我们已经附加了节点，但我们仍然需要在不对树的其他部分造成任何损害的情况下退出函数。这就是最后的 return node; 发挥作用的地方。在 NULL 的情况下，新创建的节点被返回并附加到父节点上，否则在我们返回到根的过程中，相同的节点被返回而没有任何改变。

这确保了我们在树向上移动时，其他节点的连接不会改变。

显示在向上递归步骤中返回根元素的重要性，以便在返回过程中元素不会失去位置的图片。

删除操作​

从二叉搜索树中删除节点有三种情况。

情况 I​

在第一种情况下，要删除的节点是叶节点。在这种情况下，简单地从树中删除该节点。

要删除 4

删除节点

情况 II在第二种情况下，需要删除的节点只有一个子节点。在这种情况下，请按照以下步骤操作：​

  1. 用它的子节点替换该节点。
  2. 将子节点从其原始位置移除。

6 要被删除

复制其子节点的值到该节点

最终的树

情况三​

在第三种情况下，需要删除的节点有两个子节点。在这种情况下，请按照以下步骤操作：

  1. 获取该节点的中序后继。
  2. 用中序后继替换该节点。
  3. 将中序后继从其原始位置移除。

3 要被删除

复制中序后继（4）的值到该节点

删除中序后继

Python、Java 和 C/C++ 示例​

Python Java C C++

# Python 中的二叉搜索树操作


# 创建一个节点
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


# 中序遍历
def inorder(root):
    if root is not None:
        # 遍历左侧
        inorder(root.left)

        # 遍历根
        print(str(root.key) + "->", end=' ')

        # 遍历右侧
        inorder(root.right)


# 插入一个节点
def insert(node, key):

    # 如果树为空，返回一个新节点
    if node is None:
        return Node(key)

    # 导航到正确的位置并插入节点
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    return node


# 查找中序后继
def minValueNode(node):
    current = node

    # 查找最左侧的叶子
    while(current.left is not None):
        current = current.left

    return current


# 删除一个节点
def deleteNode(root, key):

    # 如果树为空，返回
    if root is None:
        return root

    # 查找要删除的节点
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
    else:
        # 如果节点只有一个子节点或没有子节点
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # 如果节点有两个子节点，
        # 将中序后继放在要删除的节点的位置
        temp = minValueNode(root.right)

        root.key = temp.key

        # 删除中序后继
        root.right = deleteNode(root.right, temp.key)

    return root


root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)

print("中序遍历: ", end=' ')
inorder(root)

print("\n删除 10")
root = deleteNode(root, 10)
print("中序遍历: ", end=' ')
inorder(root)
// 用 Java 实现的二叉搜索树操作

class BinarySearchTree {
  class Node {
    int key;
    Node left, right;

    public Node(int item) {
      key = item;
      left = right = null;
    }
  }

  Node root;

  BinarySearchTree() {
    root = null;
  }

  void insert(int key) {
    root = insertKey(root, key);
  }

  // 在树中插入键
  Node insertKey(Node root, int key) {
    // 如果树为空，则返回一个新节点
    if (root == null) {
      root = new Node(key);
      return root;
    }

    // 遍历到正确的位置并插入节点
    if (key < root.key)
      root.left = insertKey(root.left, key);
    else if (key > root.key)
      root.right = insertKey(root.right, key);

    return root;
  }

  void inorder() {
    inorderRec(root);
  }

  // 中序遍历
  void inorderRec(Node root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.print(root.key + " -> ");
      inorderRec(root.right);
    }
  }

  void deleteKey(int key) {
    root = deleteRec(root, key);
  }

  Node deleteRec(Node root, int key) {
    // 如果树为空则直接返回
    if (root == null)
      return root;

    // 找到要删除的节点
    if (key < root.key)
      root.left = deleteRec(root.left, key);
    else if (key > root.key)
      root.right = deleteRec(root.right, key);
    else {
      // 如果节点只有一个孩子或没有孩子
      if (root.left == null)
        return root.right;
      else if (root.right == null)
        return root.left;

      // 如果节点有两个孩子
      // 将中序后继者放在要删除的节点的位置
      root.key = minValue(root.right);

      // 删除中序后继者
      root.right = deleteRec(root.right, root.key);
    }

    return root;
  }

  // 查找中序后继者
  int minValue(Node root) {
    int minv = root.key;
    while (root.left != null) {
      minv = root.left.key;
      root = root.left;
    }
    return minv;
  }

  // 测试上述功能的驱动程序
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();

    tree.insert(8);
    tree.insert(3);
    tree.insert(1);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(14);
    tree.insert(4);

    System.out.print("中序遍历: ");
    tree.inorder();

    System.out.println("\n\n删除 10 后");
    tree.deleteKey(10);
    System.out.print("中序遍历: ");
    tree.inorder();
  }
}
// 用 C 语言实现的二叉搜索树操作

#include <stdio.h>
#include <stdlib.h>

struct node {
  int key;
  struct node *left, *right;
};

// 创建节点
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// 中序遍历
void inorder(struct node *root) {
  if (root != NULL) {
    // 遍历左子树
    inorder(root->left);

    // 遍历根节点
    printf("%d -> ", root->key);

    // 遍历右子树
    inorder(root->right);
  }
}

// 插入节点
struct node *insert(struct node *node, int key) {
  // 如果树为空，则返回一个新节点
  if (node == NULL) return newNode(key);

  // 遍历到正确的位置并插入节点
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// 查找中序后继者
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // 查找最左侧的叶子节点
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// 删除节点
struct node *deleteNode(struct node *root, int key) {
  // 如果树为空则直接返回
  if (root == NULL) return root;

  // 找到要删除的节点
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // 如果节点只有一个孩子或没有孩子
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // 如果节点有两个孩子
    struct node *temp = minValueNode(root->right);

    // 将中序后继者放在要删除的节点的位置
    root->key = temp->key;

    // 删除中序后继者
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// 驱动代码
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  printf("中序遍历: ");
  inorder(root);

  printf("\n删除 10 之后\n");
  root = deleteNode(root, 10);
  printf("中序遍历: ");
  inorder(root);
}
// C++ 中的二叉搜索树操作

#include <iostream>
using namespace std;

struct node {
  int key;
  struct node *left, *right;
};

// 创建一个节点
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// 中序遍历
void inorder(struct node *root) {
  if (root != NULL) {
    // 遍历左侧
    inorder(root->left);

    // 遍历根
    cout << root->key << " -> ";

    // 遍历右侧
    inorder(root->right);
  }
}

// 插入一个节点
struct node *insert(struct node *node, int key) {
  // 如果树为空，返回一个新节点
  if (node == NULL) return newNode(key);

  // 导航到正确的位置并插入节点
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// 查找中序后继
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // 查找最左侧的叶子
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// 删除一个节点
struct node *deleteNode(struct node *root, int key) {
  // 如果树为空，返回
  if (root == NULL) return root;

  // 查找要删除的节点
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    // 如果节点只有一个子节点或没有子节点
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // 如果节点有两个子节点
    struct node *temp = minValueNode(root->right);

    // 将中序后继放在要删除的节点的位置
    root->key = temp->key;

    // 删除中序后继
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// 驱动代码
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  cout << "中序遍历: ";
  inorder(root);

  cout << "\n删除 10 后\n";
  root = deleteNode(root, 10);
  cout << "中序遍历: ";
  inorder(root);
}

二叉搜索树的复杂度​

时间复杂度​

操作最佳情况复杂度平均情况复杂度最坏情况复杂度
搜索O(log n)O(log n)O(n)
插入O(log n)O(log n)O(n)
删除O(log n)O(log n)O(n)

这里的 n 指的是树中的节点数。

空间复杂度​

所有操作的空间复杂度均为 O(n)。

二叉搜索树的应用​

  1. 在数据库中的多级索引
  2. 用于动态排序
  3. 用于管理 Unix 内核中的虚拟内存区域
最后于 更新