企业官网建设流程全解析

目录

1. AVL的概念​编辑

2. AVL 树的实现

2.1 AVL 树的结构

2.2 AVL 树的插入

2.3 旋转

2.4 AVL 树的查找

2.5 AVL 树的平衡检查

2.6 AVL树的删除

1. AVL的概念

AVL 树由前苏联数学家G.M. Adelson-Velsky（阿德尔森 - 韦尔斯基）和E.M. Landis（兰迪斯）在 1962 年提出并发表论文，它也是世界上第一个自平衡二叉搜索树。

AVL 和普通二叉搜索树（BST）最大区别

AVL 本质上依然是一棵二叉搜索树，保留 BST 的有序性质；额外增加一条平衡约束：树中任意节点，左右子树高度差绝对值不超过 1（平衡因子 ∈ {-1,0,1}）。一旦插入、删除造成失衡，会通过旋转自动调整结构、恢复平衡；普通 BST 没有这个自动平衡机制，树形态完全由插入顺序决定。

AVL 树进步的地方

1. 操作复杂度稳定：查找、插入、删除最坏时间复杂度稳定 \(O(\log n)\)，不会退化成链表，消除了 BST 最坏 \(O(n)\) 的风险。
2. 树高被严格限制，树更 “矮”，查找速度很快，适合读多写少的场景。
3. 自平衡机制：增删后自动旋转修复平衡，不需要人工重构整棵树。

AVL 树的缺点

1. 平衡条件很严格，插入、删除很容易触发旋转，尤其是删除操作，可能需要沿着路径向上多次旋转，调整开销大、写操作代价高。
2. 每个节点需要额外记录子树高度（或者平衡因子），占用额外存储空间。
3. 旋转逻辑多（LL、RR、LR、RL 四种情况），代码实现、调试更复杂。
4. 写密集场景不如红黑树合适，所以工程里 C++ map 等容器底层选用红黑树而不是 AVL。

2. AVL 树的实现

2.1 AVL 树的结构

using namespace std; template<class T> struct AVLTreeNode { AVLTreeNode(const T& data = T()) : _pLeft(nullptr) , _pRight(nullptr) , _pParent(nullptr) , _data(data) , _bf(0) { } AVLTreeNode<T>* _pLeft; AVLTreeNode<T>* _pRight; AVLTreeNode<T>* _pParent; T _data; int _bf; // 节点的平衡因子 }; // 左加 右减 // AVL: 二叉搜索树 + 平衡因子的限制 template<class T> class AVLTree { typedef AVLTreeNode<T> Node; public: // 初始默认构造 AVLTree() : _pRoot(nullptr) { } private: Node* _pRoot; };

2.2 AVL 树的插入

2.2.1 AVL 插入的大概过程

向 AVL 树插入节点时，首先按照普通二叉搜索树规则找到空位插入新节点。插入完成后，从新节点向上回溯，依次更新沿途每个祖先节点的高度，计算平衡因子。

若所有节点平衡因子绝对值都不大于 1，树保持平衡，插入结束。

如果某个节点平衡因子超出范围，说明发生失衡，需要判断失衡类型：LL、RR、LR、RL，对应执行单旋转或者双旋转调整结构，让该子树恢复平衡。旋转完成后，继续向上检查上层节点是否失衡，直到根节点。AVL 依靠旋转保证任意节点左右子树高度差不超过 1，维持树高为对数级别，保证查找效率稳定。

2.2.2 平衡因子的更新

平衡因子 = 左子树高度 − 右子树高度。 插入新节点后，从新节点的父节点开始往根方向回溯：先更新当前节点的高度，再重新计算它的平衡因子。

• 平衡因子绝对值≤1：该节点平衡，继续向上检查祖先；
• 平衡因子绝对值＞1：节点失衡，进行旋转调整；旋转完成后，更新旋转涉及节点的高度与平衡因子，再继续向上判断上层节点。 删除节点时变化更大，删除可能让祖先高度持续变化，需要一路向上更新高度、重算平衡因子，多次触发调整。

size_t _Height(Node* pRoot) { if (pRoot == nullptr) { return 0; } // max 找出两数最大数值 size_t left = _Height(pRoot->_pLeft); size_t right = _Height(pRoot->_pRight); return max(left,right) + 1; } // Bf 调整 void Bf(Node* root) { if (root == nullptr) return; int left = root->_pLeft ? _Height(root->_pLeft) : 0; int right = root->_pRight ? _Height(root->_pRight) : 0; root->_bf = left - right; }

2.2.2 插入节点的更新平衡音系的代码实现

// 在AVL树中插入值为data的节点 bool Insert(const T& data) { if (_pRoot == nullptr) { _pRoot = new Node(data); return true; } else { Node* dest = _pRoot, *cur = nullptr; while (dest) { if (data < dest->_data) { cur = dest; dest = dest->_pLeft; } else if (dest->_data < data) { cur = dest; dest = dest->_pRight; } else { return false; } } dest = new Node(data); if (data < cur->_data) { cur->_pLeft = dest; } else if (cur->_data < data) { cur->_pRight = dest; } dest->_pParent = cur; // 向上调整平衡数 Bf(cur); while (cur != nullptr && abs(cur->_bf) < 2) { cur = cur->_pParent; Bf(cur); } // 如果没有问题直接退出有平衡失衡的情况就进行旋转 if (cur == nullptr) return true; else if (cur->_bf == 2) { if (cur->_pLeft->_bf == 1) { RotateR(cur); } else if(cur->_pLeft->_bf == -1) { RotateLR(cur); } } else if (cur->_bf == -2) { if (cur->_pRight->_bf == 1) { RotateRL(cur); } else if (cur->_pRight->_bf == -1) { RotateL(cur); } } else { assert(false); } return true; } }

2.3 旋转

2.3.1 旋转的原则

旋转核心原则：不破坏二叉搜索树有序性，同时修正失衡，调整子树高度、更新平衡因子。

1. 保持 BST 性质：旋转后依旧满足左子树值 < 根 < 右子树值，中序遍历结果不变。
2. 转移子树：旋转时把中间那棵子树（被挤出来的子树）接到合适位置，避免丢失节点。
3. 优先处理最深失衡节点：从下往上找到第一个失衡节点，以它为旋转中心调整。
4. 旋转完成后，及时更新被改动节点的高度和平衡因子，再继续向上校验。
5. 旋转只改变指针关系，不改变节点相对大小；单旋处理 LL、RR，双旋处理 LR、RL。

2.3.2 右单旋

// 考虑问题: // 1,是否有 Chlid 的 左右节点是否为空(但其实右旋时就R 可能就是为空出现的可能比较小,出现的话就已经被判断需要双旋了) // 2,考虑是否有 GrandParent 有需要进行两线对接，没有就需要进行提上来的 Child 的 Parent 为空 // 右单旋 void RotateR(Node* pParent) { // G G // P C // C -> L P // L R R // // pParent -> P // // 最有可能发生_pRoot 位置就是 P 和 G ，其中 G 改变只是其中个别位置，对_pRoot 没有影响下 // 其中要关注就是 _pRoot 的 P 位置 和 C 位置 Node* Child = pParent->_pLeft;// C Node* Parent = pParent;// P Node* GrandParent = pParent->_pParent;// G // 4 段代码维护 // P->C = P->R Parent->_pLeft = Child->_pRight; // R->P = R->P if (Child->_pRight != nullptr) { Child->_pRight->_pParent = Parent; } // C->R = C->P Child->_pRight = Parent; // P->G = P->C Parent->_pParent = Child; // G->P = G->C if (GrandParent != nullptr) { GrandParent->_pLeft == Parent ? GrandParent->_pLeft = Child : GrandParent->_pRight = Child; // C->P = C->G Child->_pParent = GrandParent; } else { // C->P = C->nullptr Child->_pParent = nullptr; _pRoot = Child; } // 调整平衡 Bf(Parent); Bf(Child); }

2.3.3 左单旋

// 左单旋 void RotateL(Node* pParent) { // G G // P C // C -> P R // L R L // pParent -> P // 最有可能发生_pRoot 位置就是 P 和 G ，其中 G 改变只是其中个别位置，对_pRoot 没有影响下 // 其中要关注就是 _pRoot 的 P 位置 和 C 位置 // 4 段代码维护 // P->C = P->L Node* Child = pParent->_pRight;// C Node* Parent = pParent;// P Node* GrandParent = pParent->_pParent;// G // 4 段代码维护 // P->C = P->L Parent->_pRight = Child->_pLeft; // L->C = L->P if (Child->_pLeft != nullptr) { Child->_pLeft->_pParent = Parent; } // C->L = C->P Child->_pLeft = Parent; // P->G = P->C Parent->_pParent = Child; if (GrandParent != nullptr) { // G->P = G->C GrandParent->_pLeft == Parent ? GrandParent->_pLeft = Child : GrandParent->_pRight = Child; // C->P = C->G Child->_pParent = GrandParent; } else { // C->P = C->nullptr Child->_pParent = nullptr; _pRoot = Child; } // 调整平衡 Bf(Parent); Bf(Child); }

2.3.4 左右双旋

在部分情况种单旋已经没有办法满足了所有需要双旋来满足，第一次旋转是为了结构变成，符合左右单旋的结构。其次双旋可以复用前面的代码，以便于理解也可以不用写太多代码。

// 左右双旋 void RotateLR(Node* pParent) { /* a a c b -> c -> b a c b b->pParent 优先 c 进行 左旋 因为 c 进行 右旋 */ RotateL(pParent->_pLeft); RotateR(pParent); }

2.3.5 右左双旋

// 右左双旋 void RotateRL(Node* pParent) {// pParent -> a /* a a c b -> c -> b a c b b->pParent 优先 c 进行 右旋 因为 c 进行 左旋 */ RotateR(pParent->_pRight); RotateL(pParent); }

2.4 AVL 树的查找

AVL 树的查找过程和普通二叉搜索树查找逻辑一致。从根节点出发，拿目标值和当前节点比较：目标更小就去往左子树查找，目标更大就去往右子树查找，相等则查找成功。如果走到空节点，代表查找失败。 区别在于 AVL 树受平衡约束限制，树高稳定为 logn，查找最坏时间复杂度是 O (log n)，不会像普通 BST 那样退化成 O (n)。查找过程不会修改树结构、不改动高度和平衡因子，也不会触发旋转。

2.5 AVL 树的平衡检查

// AVL树的验证 bool IsAVLTree() { return _IsAVLTree(_pRoot); } private: // 根据AVL树的概念验证pRoot是否为有效的AVL树 bool _IsAVLTree(Node* pRoot) { if (pRoot == nullptr) { return true; } bool put = _IsAVLTree(pRoot->_pLeft); if (put == false || abs(pRoot->_bf) >= 2) { cout << "节点平衡异常" << endl; return false; } put = _IsAVLTree(pRoot->_pRight); return put; }

2.6 AVL树的删除

删除的原理其实与插入的原理一致，由二叉搜索树的删除原理，在加上对应位置旋转操作即可。

AVLTree · 浪子·悠仁/C++ 知识库 - 码云 - 开源中国