目录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 树进步的地方操作复杂度稳定查找、插入、删除最坏时间复杂度稳定 \(O(\log n)\)不会退化成链表消除了 BST 最坏 \(O(n)\) 的风险。树高被严格限制树更 “矮”查找速度很快适合读多写少的场景。自平衡机制增删后自动旋转修复平衡不需要人工重构整棵树。AVL 树的缺点平衡条件很严格插入、删除很容易触发旋转尤其是删除操作可能需要沿着路径向上多次旋转调整开销大、写操作代价高。每个节点需要额外记录子树高度或者平衡因子占用额外存储空间。旋转逻辑多LL、RR、LR、RL 四种情况代码实现、调试更复杂。写密集场景不如红黑树合适所以工程里 C map 等容器底层选用红黑树而不是 AVL。2. AVL 树的实现2.1 AVL 树的结构using namespace std; templateclass T struct AVLTreeNode { AVLTreeNode(const T data T()) : _pLeft(nullptr) , _pRight(nullptr) , _pParent(nullptr) , _data(data) , _bf(0) { } AVLTreeNodeT* _pLeft; AVLTreeNodeT* _pRight; AVLTreeNodeT* _pParent; T _data; int _bf; // 节点的平衡因子 }; // 左加 右减 // AVL: 二叉搜索树 平衡因子的限制 templateclass T class AVLTree { typedef AVLTreeNodeT 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 旋转的原则旋转核心原则不破坏二叉搜索树有序性同时修正失衡调整子树高度、更新平衡因子。保持 BST 性质旋转后依旧满足左子树值 根 右子树值中序遍历结果不变。转移子树旋转时把中间那棵子树被挤出来的子树接到合适位置避免丢失节点。优先处理最深失衡节点从下往上找到第一个失衡节点以它为旋转中心调整。旋转完成后及时更新被改动节点的高度和平衡因子再继续向上校验。旋转只改变指针关系不改变节点相对大小单旋处理 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 知识库 - 码云 - 开源中国
目录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 树进步的地方操作复杂度稳定查找、插入、删除最坏时间复杂度稳定 \(O(\log n)\)不会退化成链表消除了 BST 最坏 \(O(n)\) 的风险。树高被严格限制树更 “矮”查找速度很快适合读多写少的场景。自平衡机制增删后自动旋转修复平衡不需要人工重构整棵树。AVL 树的缺点平衡条件很严格插入、删除很容易触发旋转尤其是删除操作可能需要沿着路径向上多次旋转调整开销大、写操作代价高。每个节点需要额外记录子树高度或者平衡因子占用额外存储空间。旋转逻辑多LL、RR、LR、RL 四种情况代码实现、调试更复杂。写密集场景不如红黑树合适所以工程里 C map 等容器底层选用红黑树而不是 AVL。2. AVL 树的实现2.1 AVL 树的结构using namespace std; templateclass T struct AVLTreeNode { AVLTreeNode(const T data T()) : _pLeft(nullptr) , _pRight(nullptr) , _pParent(nullptr) , _data(data) , _bf(0) { } AVLTreeNodeT* _pLeft; AVLTreeNodeT* _pRight; AVLTreeNodeT* _pParent; T _data; int _bf; // 节点的平衡因子 }; // 左加 右减 // AVL: 二叉搜索树 平衡因子的限制 templateclass T class AVLTree { typedef AVLTreeNodeT 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 旋转的原则旋转核心原则不破坏二叉搜索树有序性同时修正失衡调整子树高度、更新平衡因子。保持 BST 性质旋转后依旧满足左子树值 根 右子树值中序遍历结果不变。转移子树旋转时把中间那棵子树被挤出来的子树接到合适位置避免丢失节点。优先处理最深失衡节点从下往上找到第一个失衡节点以它为旋转中心调整。旋转完成后及时更新被改动节点的高度和平衡因子再继续向上校验。旋转只改变指针关系不改变节点相对大小单旋处理 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 知识库 - 码云 - 开源中国
