二叉搜索樹（BST） · Programiz 中文系列教程

# 二叉搜索樹（BST） > 原文： [https://www.programiz.com/dsa/binary-search-tree](https://www.programiz.com/dsa/binary-search-tree) #### 在本教程中，您將學習二叉搜索樹的工作原理。此外，您還將找到 C，C++ ，Java 和 Python 中的二叉搜索樹的工作示例。二叉搜索樹是一種數據結構，可快速使我們維護一個排序的數字列表。 * 之所以稱為二叉樹，是因為每個樹節點最多有兩個子節點。 * 之所以稱為搜索樹，是因為它可用于在`O(log(n))`時間中搜索數字的存在。將二叉搜索樹與常規[二叉樹](/data-structures/trees)分開的屬性是 1. 左子樹的所有節點均小于根節點 2. 右子樹的所有節點均大于根節點 3. 每個節點的兩個子樹也是 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](https://img.kancloud.cn/1d/90/1d904bddc43d34718398f65ba1b22604_1460x896.png "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](https://img.kancloud.cn/57/2e/572e252b1ad1235806f38f71f5546c6c_1460x768.png "Searching on a Binary Search Tree ") 找不到 4，因此遍歷 8 的左子樹 ![4 is not found so, traverse through the right subtree of 3](https://img.kancloud.cn/74/b9/74b9c86a5718987409be4da86cb70c0e_1460x768.png "Searching on a Binary Search Tree ") 找不到 4，因此遍歷 3 的右子樹 ![4 is not found so, traverse through the left subtree of 6](https://img.kancloud.cn/f2/dc/f2dca772479e59350cfb730bcfdb29f7_1460x768.png "Searching on a Binary Search Tree ") 找不到 4，因此遍歷 6 的左子樹 ![4 is found](https://img.kancloud.cn/57/2e/572e252b1ad1235806f38f71f5546c6c_1460x768.png "Searching on a Binary Search Tree ") 找到了 4 如果找到該值，則返回該值，以便在每個遞歸步驟中將其傳播，如下圖所示。如果您可能已經注意到，我們已經四次調用`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](https://img.kancloud.cn/89/43/8943b9ddbcba4085239ec8e28592ed8d_1460x768.png "Search operation in BST") 如果在任何子樹中找到該值，則將其向上傳播，以便最后返回，否則返回`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 so, transverse through the left child of 8](https://img.kancloud.cn/7d/36/7d3670e3ba08782ef5b2b7e3c79ac269_1460x768.png "Insertion operation on a BST") 因為`4 < 8`，遍歷 8 的左子樹 ![4>3 so, transverse through the right child of 4](https://img.kancloud.cn/a6/db/a6dbd2e92481c4b07139d7699975a37a_1460x768.png "Insertion operation on a BST") 因為`4 > 3`，遍歷 3 的右子樹 ![4<6 so, transverse through the left child of 6](https://img.kancloud.cn/ce/9e/ce9ed203f249fc5de5fead732cd60bac_1460x768.png "Insertion operation on a BST") 因為`4 < 6`，遍歷 6 的左子樹 ![Insert 4 as a left child of 6](https://img.kancloud.cn/8d/73/8d73e64fe8750f59c4eca8a0bf26cfaf_1460x768.png "Insertion operation on a BST") 插入 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.](https://img.kancloud.cn/08/69/0869aee63bc7becb12a810b5d7b66d20_1460x768.png "Insertion operation on a BST") 該圖顯示了在最后返回根元素的重要性，這樣根元素才能在向上遞歸步驟中不丟失其位置。 * * * ## 刪除操作從二叉搜索樹中刪除節點的情況有三種。 ### 情況一在第一種情況下，要刪除的節點是葉節點。在這種情況下，只需從樹中刪除該節點即可。 ![4 is to be deleted](https://img.kancloud.cn/ef/32/ef32fd15d02b18b7cf3753c8cb84bfb1_1460x752.png "Deletion operation on a BST") 4 將被刪除 ![Delete the node](https://img.kancloud.cn/3c/96/3c96015385ffa14b1ef50dba28ee0df4_1460x752.png "Deletion operation on a BST") 刪除節點 ### 情況二在第二種情況下，要刪除的節點只有一個子節點。在這種情況下，請執行以下步驟： 1. 將該節點替換為其子節點。 2. 從其原始位置刪除子節點。 ![6 is to be deleted](https://img.kancloud.cn/25/dc/25dcfc456befe7e208ca1d6ae4b3576c_1460x752.png "Deletion operation on a BST") 6 將被刪除 ![copy the value of its child to the node](https://img.kancloud.cn/1f/5e/1f5e121a7682dc340856236bfedf17c6_1460x752.png "Deletion operation on a BST") 將其子項的值復制到節點并刪除該子項 ![Final tree](https://img.kancloud.cn/af/80/af803b2c4d9fcbc2eaa9329f2f62b91c_1460x584.png "Deletion operation on a BST") 最終的樹 ### 情況三在第三種情況下，要刪除的節點有兩個子級。在這種情況下，請執行以下步驟： 1. 獲取該節點的有序后繼。 2. 將節點替換為有序后繼節點。 3. 從原始位置卸下有序后繼。 ![3 is to be deleted](https://img.kancloud.cn/8d/19/8d193e76a4f8dfa59c5a66cf878177c4_1460x752.png "Deletion operation on a BST") 3 將被刪除 ![Copy the value of the inorder successor (4) to the node](https://img.kancloud.cn/8d/19/8d193e76a4f8dfa59c5a66cf878177c4_1460x752.png "Deletion operation on a BST") 將有序后繼（4）的值復制到節點 ![delete the inorder successor](https://img.kancloud.cn/f8/62/f862c71f1e25bff974eaaf4691749e28_1460x752.png "Deletion operation on a BST") 刪除順序后繼 * * * ## Python，Java 和 C/C++ 示例 ```py # 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) ``` ```java // 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(); } } ``` ```c // 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); } ``` ```cpp // 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)`。 * * * ## 二叉搜索樹應用 1. 在數據庫中進行多級索引 2. 用于動態排序 3. 用于管理 Unix 內核中的虛擬內存區域