二叉搜索树 (BST)

二叉搜索树是一种数据结构，可以快速地维护一个排序的数字列表。

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

将二叉搜索树与普通二叉树分开的属性是：

左子树的所有节点都小于根节点
右子树的所有节点都大于根节点
每个节点的两个子树也都是 BST，即它们也具有上述两个属性。

A tree having a right subtree with one value smaller than the root is shown to demonstrate that it is not a valid binary search tree — 展示一个右子树中有一个值小于根的树，以证明它不是有效的二叉搜索树。

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

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

搜索操作

该算法依赖于 BST 的属性，即每个左子树的值都低于根，而每个右子树的值都高于根。

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

算法

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

让我们用图来形象地说明一下。

4 is not found so, traverse through the left subtree of 8 — 未找到 4，因此遍历 8 的左子树。

4 is not found so, traverse through the right subtree of 3 — 未找到 4，因此遍历 3 的右子树。

4 is not found so, traverse through the left subtree of 6 — 未找到 4，因此遍历 6 的左子树。

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

如果您注意到，我们调用了四次 return search(struct node*)。当我们返回新节点或 NULL 时，该值会一次又一次地返回，直到 search(root) 返回最终结果。

if the value is found in any of the subtrees, it is propagated up so that in the end it is returned, otherwise null is returned — 如果在一个子树中找到了该值，它就会被向上传播，最终被返回；否则返回 null。

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

插入操作

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

我们根据值继续前往右子树或左子树，当到达某个点左子树或右子树为空时，我们就将新节点放在那里。

算法

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

该算法并不像看起来那么简单。让我们尝试可视化一下如何将一个数字添加到现有的 BST 中。

4<8 so, transverse through the left child of 8 — 4 < 8，因此遍历 8 的左子节点。

4>3 so, transverse through the right child of 4 — 4 > 3，因此遍历 8 的右子节点。

4<6 so, transverse through the left child of 6 — 4 < 6，因此遍历 6 的左子节点。

Insert 4 as a left child of 6 — 将 4 作为 6 的左子节点插入。

我们已经连接了节点，但仍然需要退出函数，而不会对树的其他部分造成任何损坏。这就是末尾的 return node; 派上用场的地方。在 NULL 的情况下，新创建的节点被返回并附加到父节点，否则，在返回到根之前，相同的节点会在不进行任何更改的情况下被返回。

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

Image showing the importance of returning the root element at the end so that the elements don't lose their position during the upward recursion step. — 图片显示了在向上递归步骤中返回根元素的重要性，以确保元素不会丢失其位置。

删除操作

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

情况 I

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

情况 II

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

用其子节点替换该节点。
从其原始位置删除子节点。

copy the value of its child to the node — 将子节点的值复制到该节点并删除子节点。

情况 III

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

获取该节点的按中序遍历的后继节点。
用按中序遍历的后继节点替换该节点。
从其原始位置删除按中序遍历的后继节点。

Copy the value of the inorder successor (4) to the node — 将按中序遍历的后继节点（4）的值复制到该节点。

delete the inorder successor — 删除按中序遍历的后继节点。

Python、Java 和 C/C++ 示例

Python

Java

C++

# Binary Search Tree operations in Python


# Create a node
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


# Inorder traversal
def inorder(root):
    if root is not None:
        # Traverse left
        inorder(root.left)

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

        # Traverse right
        inorder(root.right)


# Insert a node
def insert(node, key):

    # Return a new node if the tree is empty
    if node is None:
        return Node(key)

    # Traverse to the right place and insert the node
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    return node


# Find the inorder successor
def minValueNode(node):
    current = node

    # Find the leftmost leaf
    while(current.left is not None):
        current = current.left

    return current


# Deleting a node
def deleteNode(root, key):

    # Return if the tree is empty
    if root is None:
        return root

    # Find the node to be deleted
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
    else:
        # If the node is with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp

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

        # If the node has two children,
        # place the inorder successor in position of the node to be deleted
        temp = minValueNode(root.right)

        root.key = temp.key

        # Delete the inorder successor
        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("Inorder traversal: ", end=' ')
inorder(root)

print("\nDelete 10")
root = deleteNode(root, 10)
print("Inorder traversal: ", end=' ')
inorder(root)

// Binary Search Tree operations in 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);
  }

  // Insert key in the tree
  Node insertKey(Node root, int key) {
    // Return a new node if the tree is empty
    if (root == null) {
      root = new Node(key);
      return root;
    }

    // Traverse to the right place and insert the node
    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);
  }

  // Inorder Traversal
  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) {
    // Return if the tree is empty
    if (root == null)
      return root;

    // Find the node to be deleted
    if (key < root.key)
      root.left = deleteRec(root.left, key);
    else if (key > root.key)
      root.right = deleteRec(root.right, key);
    else {
      // If the node is with only one child or no child
      if (root.left == null)
        return root.right;
      else if (root.right == null)
        return root.left;

      // If the node has two children
      // Place the inorder successor in position of the node to be deleted
      root.key = minValue(root.right);

      // Delete the inorder successor
      root.right = deleteRec(root.right, root.key);
    }

    return root;
  }

  // Find the inorder successor
  int minValue(Node root) {
    int minv = root.key;
    while (root.left != null) {
      minv = root.left.key;
      root = root.left;
    }
    return minv;
  }

  // Driver Program to test above functions
  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("Inorder traversal: ");
    tree.inorder();

    System.out.println("\n\nAfter deleting 10");
    tree.deleteKey(10);
    System.out.print("Inorder traversal: ");
    tree.inorder();
  }
}

// Binary Search Tree operations in C

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

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

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->key);

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // If the node is with only one child or no child
    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;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
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 traversal: ");
  inorder(root);

  printf("\nAfter deleting 10\n");
  root = deleteNode(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

// Binary Search Tree operations in C++

#include <iostream>
using namespace std;

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

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    cout << root->key << " -> ";

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    // If the node is with only one child or no child
    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;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
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 traversal: ";
  inorder(root);

  cout << "\nAfter deleting 10\n";
  root = deleteNode(root, 10);
  cout << "Inorder traversal: ";
  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)。

二叉搜索树应用

在数据库的多级索引中
用于动态排序
用于管理 Unix 内核中的虚拟内存区域

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python
程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

二叉搜索树 (BST)

搜索操作

插入操作

删除操作

情况 I

情况 II

情况 III

Python、Java 和 C/C++ 示例

二叉搜索树复杂度

时间复杂度

空间复杂度

二叉搜索树应用

目录

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

DSA 教程

二叉搜索树 (BST)

搜索操作

插入操作

删除操作

情况 I

情况 II

情况 III

Python、Java 和 C/C++ 示例

二叉搜索树复杂度

时间复杂度

空间复杂度

二叉搜索树应用

目录

相关教程

成为一名认证的 Python
程序员。