文章目录

1. 概述2. 操作2.1 搜索Search2.2 最小值Minimum2.3 最大值Maximum2.4 后继Successor2.5 前驱Predecessor2.6 插入Insert2.7 删除Delete 3. C++代码实现4. 自平衡二叉搜索树4.1 左旋Left rotation4.2 Right rotation 5. 参考资料

1. 概述

二叉搜索树是具有以下性质的二叉树：

节点 $x$ 的左子树中的每个节点均小于或等于 $x$，而右子树中的每个节点均大于或等于 $x$。

下图是二叉搜索树的一个示例：

2. 操作

2.1 搜索Search

从根节点开始，然后向下移动，直到找到要搜索的键值 $k$。如果找到该节点，则过程终止，否则返回NIL。

对于我们遇到的每个节点 $x$，我们将键值 $k$ 与 x.key 进行比较。如果两个值相等，则搜索终止。如果 $k$ 小于 x.key，则继续搜索 $x$ 的左子树。同样，如果 $k$ 大于 x.key，则继续搜索 $x$ 的右子树。

以下图为例，我们在二叉搜索树中搜索键为 $25$ 的节点：

下面给出搜索操作的递归算法，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.2 最小值Minimum

给定一个二叉搜索树，其最左节点为最小键，其最右节点为最大键。如下图所示。

下面给出找到具有最小键值的节点的算法，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.3 最大值Maximum

下面给出找到具有最大键值的节点的算法，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.4 后继Successor

如果我们对二叉搜索树进行中序遍历，将会得到一个基于键值的升序序列，则每个节点都是前一个节点的后继节点，每个节点都是下一个节点的前驱节点。

由于二叉搜索树的结构，我们可以在不比较关键字的情况下找到节点的后继和前驱。

为了找到节点 $x$ 的后继，我们执行以下操作：

如果节点 $x$ 的右子树非空，则 $x$ 的后继就是 $x$ 的右子树中的最左侧节点。

如果节点 $x$ 的右子树为空，并且 $x$ 具有后继 $y$，则 $y$ 是 $x$ 的最低祖先，并且 $y$ 的左子节点也是 $x$ 的祖先。

下面给出找到节点 $x$ 的后继 $y$ 的算法，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.5 前驱Predecessor

同样地，为了找到节点 $x$ 的前驱，我们执行以下操作：

如果节点 $x$ 的左子树非空，则 $x$ 的前驱节点就是 $x$ 的左子树中的最右节点。

如果节点 $x$ 的左子树为空，并且 $x$ 具有前驱 $y$，则 $y$ 是 $x$ 的最低祖先，并且 $y$ 的右子节点也是 $x$ 的祖先。

下面给出找到节点 $x$ 的前驱 $y$ 的算法，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.6 插入Insert

如果我们要插入 key，新建一个节点 $z$ 保存 key 值，要在树中插入节点 $z$ 的同时不违反二叉搜索树的性质。我们将 $z$ 与节点 $x$ 从根节点开始进行比较。如果 z.key 小于 x.key，则在 $x$ 的左子树中继续执行该过程，否则将移至 $x$ 的右子树。循环此过程，直到 $x$ 的值为NIL。

为了简化插入操作，我们还需要跟踪 $x$ 的父节点 $y$。当 $x$ 为 NIL 时，我们将 $y$ 的键与 $z$ 的键进行比较，如果 $z$ 的键值小，则 $z$ 作左孩子；反之，$z$ 作右孩子。

以下图为例，我们在二叉搜索树中插入键为 $24$ 的节点：

下面给出插入节点 $z$ 的伪代码，运行时间为 $O(h)$，其中 $h$ 是树的高度。

2.7 删除Delete

删除操作有些棘手，因为删除节点后我们需要保留BST性质。为了保留BST性质，我们可能需要对树进行转换。

如果我们要删除 key，首先找到包含 key 的节点 $x$。为了删除节点 $x$，我们需要处理三种不同的情况。前两种情况很简单，最后一种则有些困难。

情况1：当 $x$ 是叶节点时，我们只需删除该节点并相应地更改 $x$ 的父节点的左右指针即可。

情况2：当 $x$ 仅有一个子节点（左或右）时，我们删除节点 $x$，并将 $x$ 的父节点的左或右指针设置为 $x$ 的子节点同时调整 $x$ 的子节点的父指针即可。

情况3：当 $x$ 有两个孩子时，我们将执行以下操作。

我们复制 $x$ 的右子树的最小节点 $y$ 并将其放置在 $x$ 的位置。

删除 $y$。在删除 $y$ 时，我们需要处理情况 1 或情况 2，具体取决于 $y$ 是有一个孩子还是没有任何孩子。

以下图为例，解释情况3。

下面给出删除操作的伪代码：

3. C++代码实现

// Binary search tree implementation in C++ // Author: Algorithm Tutor #include <iostream> using namespace std; // data structure that represents a node in the tree struct Node { int data; // holds the key Node *parent; // pointer to the parent Node *left; // pointer to left child Node *right; // pointer to right child }; typedef Node *NodePtr; // class BST implements the operations in BST class BST { private: NodePtr root; // initializes the nodes with appropirate values // all the pointers are set to point to the null pointer void initializeNode(NodePtr node, int key) { node->data = key; node->parent = nullptr; node->left = nullptr; node->right = nullptr; } void preOrderHelper(NodePtr node) { if (node != nullptr) { cout << node->data << " "; preOrderHelper(node->left); preOrderHelper(node->right); } } void inOrderHelper(NodePtr node) { if (node != nullptr) { inOrderHelper(node->left); cout << node->data << " "; inOrderHelper(node->right); } } void postOrderHelper(NodePtr node) { if (node != nullptr) { postOrderHelper(node->left); postOrderHelper(node->right); cout << node->data << " "; } } NodePtr searchTreeHelper(NodePtr node, int key) { if (node == nullptr || key == node->data) { return node; } if (key < node->data) { return searchTreeHelper(node->left, key); } return searchTreeHelper(node->right, key); } NodePtr deleteNodeHelper(NodePtr node, int key) { // search the key if (node == nullptr) return node; else if (key < node->data) node->left = deleteNodeHelper(node->left, key); else if (key > node->data) node->right = deleteNodeHelper(node->right, key); else { // the key has been found, now delete it // case 1: node is a leaf node if (node->left == nullptr && node->right == nullptr) { delete node; node = nullptr; } // case 2: node has only one child else if (node->left == nullptr) { NodePtr temp = node; node = node->right; delete temp; } else if (node->right == nullptr) { NodePtr temp = node; node = node->left; delete temp; } // case 3: has both children else { NodePtr temp = minimum(node->right); node->data = temp->data; node->right = deleteNodeHelper(node->right, temp->data); } } return node; } void printHelper(NodePtr root, string indent, bool last) { // print the tree structure on the screen if (root != nullptr) { cout << indent; if (last) { cout << "└────"; indent += " "; } else { cout << "├────"; indent += "| "; } cout << root->data << endl; printHelper(root->left, indent, false); printHelper(root->right, indent, true); } } public: BST() { root = nullptr; } void createSampleTree1() { NodePtr node50 = new Node; initializeNode(node50, 50); NodePtr node30 = new Node; initializeNode(node30, 30); NodePtr node70 = new Node; initializeNode(node70, 70); node30->parent = node50; node70->parent = node50; node50->left = node30; node50->right = node70; NodePtr node23 = new Node; initializeNode(node23, 23); NodePtr node35 = new Node; initializeNode(node35, 35); node23->parent = node30; node35->parent = node30; node30->left = node23; node30->right = node35; NodePtr node11 = new Node; initializeNode(node11, 11); NodePtr node25 = new Node; initializeNode(node25, 25); node11->parent = node23; node25->parent = node23; node23->left = node11; node23->right = node25; NodePtr node31 = new Node; initializeNode(node31, 31); NodePtr node42 = new Node; initializeNode(node42, 42); node31->parent = node35; node42->parent = node35; node35->left = node31; node35->right = node42; NodePtr node80 = new Node; initializeNode(node80, 80); node80->parent = node70; node70->right = node80; NodePtr node73 = new Node; initializeNode(node73, 73); NodePtr node85 = new Node; initializeNode(node85, 85); node73->parent = node80; node85->parent = node80; node80->left = node73; node80->right = node85; this->root = node50; } // Pre-Order traversal // Node->Left Subtree->Right Subtree void preorder() { preOrderHelper(this->root); } // In-Order traversal // Left Subtree -> Node -> Right Subtree void inorder() { inOrderHelper(this->root); } // Post-Order traversal // Left Subtree -> Right Subtree -> Node void postorder() { postOrderHelper(this->root); } // search the tree for the key k // and return the corresponding node NodePtr searchTree(int k) { return searchTreeHelper(this->root, k); } // find the node with the minimum key NodePtr minimum(NodePtr node) { while (node->left != nullptr) { node = node->left; } return node; } // find the node with the maximum key NodePtr maximum(NodePtr node) { while (node->right != nullptr) { node = node->right; } return node; } // find the successor of a given node NodePtr successor(NodePtr x) { // if the right subtree is not null, // the successor is the leftmost node in the // right subtree if (x->right != nullptr) { return minimum(x->right); } // else it is the lowest ancestor of x whose // left child is also an ancestor of x. NodePtr y = x->parent; while (y != nullptr && x == y->right) { x = y; y = y->parent; } return y; } // find the predecessor of a given node NodePtr predecessor(NodePtr x) { // if the left subtree is not null, // the predecessor is the rightmost node in the // left subtree if (x->left != nullptr) { return maximum(x->left); } NodePtr y = x->parent; while (y != nullptr && x == y->left) { x = y; y = y->parent; } return y; } // insert the key to the tree in its appropriate position void insert(int key) { NodePtr node = new Node; node->parent = nullptr; node->left = nullptr; node->right = nullptr; node->data = key; NodePtr y = nullptr; NodePtr x = this->root; while (x != nullptr) { y = x; if (node->data < x->data) { x = x->left; } else { x = x->right; } } // y is parent of x node->parent = y; if (y == nullptr) { root = node; } else if (node->data < y->data) { y->left = node; } else { y->right = node; } } NodePtr getRoot(){ return this->root; } // delete the node from the tree NodePtr deleteNode(int data) { return deleteNodeHelper(this->root, data); } // print the tree structure on the screen void prettyPrint() { printHelper(this->root, "", true); } }; int main() { BST bst; bst.createSampleTree1(); bst.prettyPrint(); return 0; }

4. 自平衡二叉搜索树

如下图所示，这些二叉搜索树是不平衡的，等效于链表，因此，普通的二叉搜索树最坏情况下的运行时间为 $O(n)$。

树旋转是一种转换技术，可用于在不更改中序遍历序列的情况下更改二叉搜索树的结构。许多自平衡BST算法都使用此技术在插入和删除操作后维持树的高度。有以下两种类型的树旋转。

4.1 左旋Left rotation

当我们在节点 $x$ 上进行左旋转时，我们假设其右子节点 $y$ 不为 nil。左旋转使 $y$ 成为子树的新根，其中 $x$ 成为 $y$ 的左孩子，$y$ 的左孩子成为 $x$ 的右孩子。

左旋转的伪代码如下：

4.2 Right rotation

右旋转的伪代码如下：

5. 参考资料

[1] https://algorithmtutor.com/Data-Structures/Tree/Binary-Search-Trees/

[2] https://algorithmtutor.com/Data-Structures/Tree/Self-balancing-Binary-Search-Trees/