二叉搜索树（BST）

原文： https://www.programiz.com/dsa/binary-search-tree

在本教程中，您将学习二叉搜索树的工作原理。 此外，您还将找到 C，C++ ，Java 和 Python 中的二叉搜索树的工作示例。

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

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

将二叉搜索树与常规二叉树分开的属性是

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

显示了一个树，该树的右子树的值小于根，表明该树不是有效的二叉搜索树

右边的二叉树不是二叉搜索树，因为节点“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，因此遍历 8 的左子树

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

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

找到了 4

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

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

如果在任何子树中找到该值，则将其向上传播，以便最后返回，否则返回null。

如果找不到该值，则最终到达叶节点的左或右子节点，该子节点为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，遍历 8 的左子树

因为4 > 3，遍历 3 的右子树

因为4 < 6，遍历 6 的左子树

插入 4 作为 6 的左子级

我们已经附加了节点，但是我们仍然必须退出该函数，而不会损坏树的其余部分。 这是最后的return node;派上用场的地方。 在NULL的情况下，将返回新创建的节点并将其附加到父节点，否则在返回到根节点之前，将返回相同的节点，而不会进行任何更改。

这可以确保当我们向后移动树时，其他节点连接不会更改。

该图显示了在最后返回根元素的重要性，这样根元素才能在向上递归步骤中不丢失其位置。

删除操作

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

情况一

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

4 将被删除

删除节点

情况二

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

1. 将该节点替换为其子节点。
2. 从其原始位置删除子节点。

6 将被删除

将其子项的值复制到节点并删除该子项

最终的树

情况三

在第三种情况下，要删除的节点有两个子级。 在这种情况下，请执行以下步骤：

1. 获取该节点的有序后继。
2. 将节点替换为有序后继节点。
3. 从原始位置卸下有序后继。

3 将被删除

将有序后继（4）的值复制到节点

删除顺序后继

Python，Java 和 C/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);
}

二叉搜索树的复杂度

时间复杂度

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

空间复杂度

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

二叉搜索树应用

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