- 正确答案：手搓平衡二叉树通常指的是手动实现一种自平衡的二叉搜索树，最常见的是AVL树。AVL树是一种二叉搜索树，它通过维护每个节点的左右子树高度差不超过1来保证树的平衡，从而确保查找、插入和删除操作的时间复杂度始终保持在O(log n)。 - 解答思路： 1. 明确AVL树的基本性质：二叉搜索树性质（左子树所有节点值小于根节点，右子树所有节点值大于根节点） + 平衡条件（任意节点的左右子树高度差不超过1）。 2. 设计节点结构，包含值、左右孩子指针、高度信息。 3. 实现二叉搜索树的基本操作（插入、删除、查找），但在插入和删除后需要检查并恢复平衡。 4. 当发现不平衡时，通过四种旋转操作（左旋、右旋、左右双旋、右左双旋）进行调整。 5. 每次修改树结构后更新节点高度，并递归向上回溯检查祖先节点是否仍保持平衡。 - 深度知识讲解： AVL树的核心在于“平衡因子”（Balance Factor）的概念，定义为：某节点的左子树高度减去右子树高度。AVL树要求每个节点的平衡因子只能是 -1、0 或 1。插入或删除节点可能导致某个节点的平衡因子变为 ±2，此时必须通过旋转操作恢复平衡。旋转分为四种情况： 1. 左左型（LL）：在左子树的左子树插入导致失衡 → 对该节点进行右旋。 2. 右右型（RR）：在右子树的右子树插入导致失衡 → 对该节点进行左旋。 3. 左右型（LR）：在左子树的右子树插入导致失衡 → 先对左孩子左旋，再对该节点右旋。 4. 右左型（RL）：在右子树的左子树插入导致失衡 → 先对右孩子右旋，再对该节点左旋。旋转操作是局部操作，只改变几个指针，不影响整棵树的结构，且能有效降低高度，维持O(log n)性能。高度的维护：每个节点存储其子树的高度，插入/删除后从下往上更新高度。高度计算公式为： height(node) = 1 + max(height(left), height(right)) 时间复杂度分析： - 查找：O(log n) - 插入：O(log n)（包括遍历路径+最多一次旋转） - 删除：O(log n)（可能沿路径回溯并多次旋转）空间复杂度：O(n)，每个节点额外存储高度信息。与红黑树对比： - AVL树更严格平衡，查找更快，适合读多写少场景。 - 红黑树平衡条件宽松，旋转少，插入删除更快，适合动态频繁修改的场景。 - 代码示例（C++风格伪代码）： ``` struct TreeNode { int val; TreeNode* left; TreeNode* right; int height; TreeNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {} }; int getHeight(TreeNode* node) { if (node == nullptr) return 0; return node->height; } int getBalance(TreeNode* node) { if (node == nullptr) return 0; return getHeight(node->left) - getHeight(node->right); } void updateHeight(TreeNode* node) { if (node != nullptr) { node->height = 1 + max(getHeight(node->left), getHeight(node->right)); } } TreeNode* rotateRight(TreeNode* y) { TreeNode* x = y->left; TreeNode* T2 = x->right; x->right = y; y->left = T2; updateHeight(y); updateHeight(x); return x; } TreeNode* rotateLeft(TreeNode* x) { TreeNode* y = x->right; TreeNode* T2 = y->left; y->left = x; x->right = T2; updateHeight(x); updateHeight(y); return y; } TreeNode* insert(TreeNode* root, int val) { // 1. 执行标准BST插入 if (root == nullptr) { return new TreeNode(val); } if (val < root->val) { root->left = insert(root->left, val); } else if (val > root->val) { root->right = insert(root->right, val); } else { return root; // 不允许重复值 } // 2. 更新当前节点高度 updateHeight(root); // 3. 获取平衡因子 int balance = getBalance(root); // 4. 如果失衡，进行四种情况处理 // Left Left Case if (balance > 1 && val < root->left->val) { return rotateRight(root); } // Right Right Case if (balance < -1 && val > root->right->val) { return rotateLeft(root); } // Left Right Case if (balance > 1 && val > root->left->val) { root->left = rotateLeft(root->left); return rotateRight(root); } // Right Left Case if (balance < -1 && val < root->right->val) { root->right = rotateRight(root->right); return rotateLeft(root); } return root; } TreeNode* minValueNode(TreeNode* node) { TreeNode* current = node; while (current->left != nullptr) current = current->left; return current; } TreeNode* deleteNode(TreeNode* root, int val) { if (root == nullptr) return root; if (val < root->val) { root->left = deleteNode(root->left, val); } else if (val > root->val) { root->right = deleteNode(root->right, val); } else { // 找到要删除的节点 if (root->left == nullptr || root->right == nullptr) { TreeNode* temp = root->left ? root->left : root->right; if (temp == nullptr) { temp = root; root = nullptr; } else { *root = *temp; } delete temp; } else { TreeNode* temp = minValueNode(root->right); root->val = temp->val; root->right = deleteNode(root->right, temp->val); } } if (root == nullptr) return root; updateHeight(root); int balance = getBalance(root); // 四种失衡情况处理（与插入类似） // Left Left if (balance > 1 && getBalance(root->left) >= 0) { return rotateRight(root); } // Left Right if (balance > 1 && getBalance(root->left) < 0) { root->left = rotateLeft(root->left); return rotateRight(root); } // Right Right if (balance < -1 && getBalance(root->right) <= 0) { return rotateLeft(root); } // Right Left if (balance < -1 && getBalance(root->right) > 0) { root->right = rotateRight(root->right); return rotateLeft(root); } return root; } ``` - 扩展知识点： 1. AVL树适用于对查询效率要求极高的场景，如数据库索引、字典实现等。 2. 实际工程中更多使用红黑树（如C++ STL中的map/set），因为其旋转次数更少，综合性能更好。 3. B树、B+树是多路平衡树，用于磁盘存储系统（如文件系统、数据库），减少I/O次数。 4. Splay树是一种自调整二叉搜索树，将最近访问的节点移到根部，具有良好的局部性访问性能。 5. Treap（Tree + Heap）结合二叉搜索树和堆的性质，用随机优先级维持平衡，实现简单且期望平衡。掌握AVL树的实现不仅有助于理解自平衡机制，也为学习更复杂的树结构打下坚实基础。在面试中，能完整写出插入操作并解释旋转逻辑，通常就能获得较高评价。

百度三面太逆天了

全站热榜

创作者周榜