企业官网建设流程全解析

1. 引言

二叉搜索树（Binary Search Tree，BST）和平衡二叉搜索树（Balanced Binary Search Tree）是数据结构与算法中的核心内容，广泛应用于查找、插入、删除等动态数据操作场景。本文将从基本概念出发，结合C++代码，详细讲解二叉搜索树的定义、操作实现，以及平衡二叉搜索树（以AVL树为例）的旋转原理与代码实现。

2. 二叉搜索树（BST）

2.1 什么是二叉搜索树

二叉搜索树是一棵二叉树，它满足以下性质：

• 左子树性质：任意节点的左子树中所有节点的值都小于该节点的值。
• 右子树性质：任意节点的右子树中所有节点的值都大于该节点的值。
• 递归性质：左子树和右子树本身也分别是二叉搜索树。

基于上述性质，二叉搜索树的中序遍历结果是一个递增的有序序列，这使得它非常适合用于快速查找和排序相关操作。

2.2 二叉搜索树的节点定义

在C++中，我们通常使用结构体或类来定义二叉搜索树的节点。每个节点包含一个键值（key）以及指向左孩子和右孩子的指针。

struct TreeNode { int val; // 节点存储的值 TreeNode* left; // 左孩子指针 TreeNode* right; // 右孩子指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

2.3 二叉搜索树的查找操作

查找操作是二叉搜索树最基础的操作。从根节点开始，将目标值与当前节点值比较：若相等则查找成功；若目标值小于当前节点值，则递归地在左子树中查找；否则递归地在右子树中查找。由于每次比较都能排除一半的子树，查找的时间复杂度在理想情况下为 O(log n)。

// 在二叉搜索树中查找值为 target 的节点 TreeNode* searchBST(TreeNode* root, int target) { // 当前节点为空，说明查找失败 if (root == nullptr) { return nullptr; } // 找到目标值，返回当前节点 if (root->val == target) { return root; } // 目标值小于当前节点值，去左子树查找 if (target < root->val) { return searchBST(root->left, target); } // 目标值大于当前节点值，去右子树查找 return searchBST(root->right, target); }

2.4 二叉搜索树的插入操作

插入操作同样从根节点开始，按照查找的规则找到合适的空位置，将新节点作为叶子节点插入。插入后，二叉搜索树的性质依然保持。

// 向二叉搜索树中插入一个新节点，返回插入后的根节点 TreeNode* insertBST(TreeNode* root, int val) { // 找到空位置，创建新节点 if (root == nullptr) { return new TreeNode(val); } // 待插入值小于当前节点值，插入到左子树 if (val < root->val) { root->left = insertBST(root->left, val); } // 待插入值大于当前节点值，插入到右子树 else if (val > root->val) { root->right = insertBST(root->right, val); } // 值相等时，根据需求决定是否处理重复值，这里选择忽略 return root; }

2.5 二叉搜索树的删除操作

删除操作相对复杂，需要分三种情况讨论：

• 情况一：待删除节点是叶子节点，直接删除即可。
• 情况二：待删除节点只有一个孩子，用其孩子节点替代它。
• 情况三：待删除节点有两个孩子，通常用其左子树中的最大值节点或右子树中的最小值节点来替代它，然后删除那个被替代的节点。

// 找到以 root 为根的子树中的最小值节点 TreeNode* findMin(TreeNode* root) { while (root->left != nullptr) { root = root->left; } return root; } // 从二叉搜索树中删除值为 val 的节点，返回删除后的根节点 TreeNode* deleteBST(TreeNode* root, int val) { if (root == nullptr) { return nullptr; } // 待删除值小于当前节点值，去左子树删除 if (val < root->val) { root->left = deleteBST(root->left, val); } // 待删除值大于当前节点值，去右子树删除 else if (val > root->val) { root->right = deleteBST(root->right, val); } // 找到待删除节点 else { // 情况一：叶子节点或只有一个右孩子 if (root->left == nullptr) { TreeNode* temp = root->right; delete root; return temp; } // 情况二：只有一个左孩子 if (root->right == nullptr) { TreeNode* temp = root->left; delete root; return temp; } // 情况三：有两个孩子，用右子树中的最小值节点替代 TreeNode* minNode = findMin(root->right); root->val = minNode->val; root->right = deleteBST(root->right, minNode->val); } return root; }

2.6 二叉搜索树的性能瓶颈

二叉搜索树的查找、插入和删除操作的时间复杂度与树的高度密切相关。在理想情况下，树是平衡的，高度为 O(log n)，操作效率很高。但是，如果插入的数据本身是有序的（例如依次插入 1、2、3、4、5），二叉搜索树会退化成一条链表，树的高度变为 O(n)，此时各种操作的时间复杂度也退化为 O(n)，性能大幅下降。为了解决这个问题，平衡二叉搜索树应运而生。

3. 平衡二叉搜索树（以AVL树为例）

3.1 什么是平衡二叉搜索树

平衡二叉搜索树是一种在插入和删除操作后能够自动保持树高度平衡的二叉搜索树。它通过限制左右子树的高度差，确保树的高度始终维持在 O(log n) 级别，从而保证查找、插入、删除操作的时间复杂度稳定在 O(log n)。常见的平衡二叉搜索树包括 AVL 树、红黑树等。本文以 AVL 树为例进行讲解。

3.2 AVL树的定义与平衡因子

AVL 树是最早被发明的自平衡二叉搜索树。它在每个节点上维护一个平衡因子（Balance Factor），定义为左子树高度减去右子树高度。AVL 树要求任意节点的平衡因子的绝对值不超过 1，即平衡因子只能取 -1、0 或 1。当插入或删除操作导致某个节点的平衡因子绝对值大于 1 时，就需要通过旋转操作来恢复平衡。

struct AVLNode { int val; // 节点存储的值 int height; // 以该节点为根的子树高度 AVLNode* left; // 左孩子指针 AVLNode* right; // 右孩子指针 AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {} }; // 获取节点高度，空节点高度为 0 int getHeight(AVLNode* node) { return node == nullptr ? 0 : node->height; } // 获取节点的平衡因子（左子树高度 - 右子树高度） int getBalanceFactor(AVLNode* node) { return node == nullptr ? 0 : getHeight(node->left) - getHeight(node->right); } // 更新节点高度 void updateHeight(AVLNode* node) { node->height = 1 + std::max(getHeight(node->left), getHeight(node->right)); }

3.3 AVL树的旋转操作

当插入或删除节点导致树失去平衡时，需要通过旋转操作来恢复平衡。旋转分为四种基本类型：左旋、右旋、左右旋和右左旋。

右旋（LL型失衡的修复）：当某个节点的左子树过高，且左孩子的左子树也过高时，执行右旋操作。

// 右旋操作 AVLNode* rotateRight(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; // 执行旋转 x->right = y; y->left = T2; // 更新高度 updateHeight(y); updateHeight(x); // 返回新的根节点 return x; }

左旋（RR型失衡的修复）：当某个节点的右子树过高，且右孩子的右子树也过高时，执行左旋操作。

// 左旋操作 AVLNode* rotateLeft(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; // 执行旋转 y->left = x; x->right = T2; // 更新高度 updateHeight(x); updateHeight(y); // 返回新的根节点 return y; }

左右旋（LR型失衡的修复）：当某个节点的左子树过高，但左孩子的右子树过高时，先对左孩子执行左旋，再对当前节点执行右旋。

// 左右旋操作 AVLNode* rotateLeftRight(AVLNode* node) { node->left = rotateLeft(node->left); return rotateRight(node); }

右左旋（RL型失衡的修复）：当某个节点的右子树过高，但右孩子的左子树过高时，先对右孩子执行右旋，再对当前节点执行左旋。

// 右左旋操作 AVLNode* rotateRightLeft(AVLNode* node) { node->right = rotateRight(node->right); return rotateLeft(node); }

3.4 AVL树的插入操作

AVL 树的插入操作分为两步：第一步，按照普通二叉搜索树的规则插入新节点；第二步，从插入位置向上回溯，更新节点高度并检查平衡因子，若失衡则进行相应的旋转修复。

// 向AVL树中插入新节点，返回插入后的根节点 AVLNode* insertAVL(AVLNode* root, int val) { // 1. 执行普通BST插入 if (root == nullptr) { return new AVLNode(val); } if (val < root->val) { root->left = insertAVL(root->left, val); } else if (val > root->val) { root->right = insertAVL(root->right, val); } else { // 值已存在，不重复插入 return root; } // 2. 更新当前节点高度 updateHeight(root); // 3. 获取平衡因子，判断是否失衡 int balance = getBalanceFactor(root); // 4. 根据失衡类型进行旋转修复 // 左左型（LL）：左子树过高，且左孩子的左子树过高 if (balance > 1 && val < root->left->val) { return rotateRight(root); } // 右右型（RR）：右子树过高，且右孩子的右子树过高 if (balance < -1 && val > root->right->val) { return rotateLeft(root); } // 左右型（LR）：左子树过高，但左孩子的右子树过高 if (balance > 1 && val > root->left->val) { return rotateLeftRight(root); } // 右左型（RL）：右子树过高，但右孩子的左子树过高 if (balance < -1 && val < root->right->val) { return rotateRightLeft(root); } // 未失衡，直接返回当前节点 return root; }

3.5 AVL树的删除操作

AVL 树的删除操作同样分为两步：第一步，按照普通二叉搜索树的规则删除节点；第二步，从删除位置向上回溯，更新高度并检查平衡因子，必要时进行旋转修复。

// 从AVL树中删除值为 val 的节点，返回删除后的根节点 AVLNode* deleteAVL(AVLNode* root, int val) { // 1. 执行普通BST删除 if (root == nullptr) { return nullptr; } if (val < root->val) { root->left = deleteAVL(root->left, val); } else if (val > root->val) { root->right = deleteAVL(root->right, val); } else { // 找到待删除节点 if (root->left == nullptr || root->right == nullptr) { AVLNode* temp = root->left != nullptr ? root->left : root->right; if (temp == nullptr) { // 叶子节点 temp = root; root = nullptr; } else { // 只有一个孩子 *root = *temp; } delete temp; } else { // 有两个孩子，用右子树中的最小值节点替代 AVLNode* minNode = root->right; while (minNode->left != nullptr) { minNode = minNode->left; } root->val = minNode->val; root->right = deleteAVL(root->right, minNode->val); } } // 如果树为空，直接返回 if (root == nullptr) { return nullptr; } // 2. 更新当前节点高度 updateHeight(root); // 3. 获取平衡因子 int balance = getBalanceFactor(root); // 4. 根据失衡类型进行旋转修复 // 左左型（LL） if (balance > 1 && getBalanceFactor(root->left) >= 0) { return rotateRight(root); } // 左右型（LR） if (balance > 1 && getBalanceFactor(root->left) < 0) { return rotateLeftRight(root); } // 右右型（RR） if (balance < -1 && getBalanceFactor(root->right) <= 0) { return rotateLeft(root); } // 右左型（RL） if (balance < -1 && getBalanceFactor(root->right) > 0) { return rotateRightLeft(root); } return root; }

3.6 AVL树的遍历与验证

为了验证 AVL 树的正确性，我们可以实现中序遍历来检查输出是否有序，并实现一个检查函数来验证每个节点的平衡因子是否满足 AVL 性质。

// 中序遍历（输出有序序列） void inorderTraversal(AVLNode* root) { if (root == nullptr) { return; } inorderTraversal(root->left); std::cout << root->val << " "; inorderTraversal(root->right); } // 检查是否为合法的AVL树 bool isAVL(AVLNode* root) { if (root == nullptr) { return true; } int balance = getBalanceFactor(root); // 平衡因子绝对值

4. 总结

4.1 核心要点回顾

二叉搜索树（BST）通过左小右大的节点组织方式，使得查找、插入和删除操作在理想情况下都能达到 O(log n) 的时间复杂度，其中序遍历结果天然有序。然而，当插入数据本身有序时，BST 会退化为链表，操作复杂度恶化到 O(n)。

平衡二叉搜索树（以 AVL 树为例）通过维护每个节点的平衡因子（左子树高度减右子树高度，绝对值不超过 1），在插入和删除后自动执行旋转操作恢复平衡，从而保证树的高度始终维持在 O(log n) 级别，使各项操作的时间复杂度稳定在 O(log n)。

4.2 适用场景对比

4.3 选择建议

• 学习与入门：优先掌握普通 BST 和 AVL 树，理解平衡因子的含义与四种旋转（LL、RR、LR、RL）的触发条件。
• 查找密集型应用：若查询操作远多于插入删除，选择 AVL 树可获得最稳定的查找性能。
• 写操作密集型应用：若插入删除频繁，红黑树因旋转次数更少而整体性能更优，这也是 C++ STL 中 map 和 set 采用红黑树的原因。
• 工程实践：多数标准库已内置平衡树实现，优先复用成熟容器，仅在特殊需求下自行实现。