【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（二）https://developer.aliyun.com/article/1617412
七、AVLTree.h
#pragma once #include <assert.h> #include <iostream> using namespace std; //设置默认权限为公用的结构体 template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; //主要类型 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: Node* Find(const K& key) { //按照搜索树 Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { //返回当前节点的指针 return cur; } } return nullptr; } bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } //也是查找需要插入的地方，进行插入 Node* parent = nullptr; Node* cur = _root; //目的就是让cur走到合适的空位置 while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { assert(!cur); } } //需要将这个节点连接起来 cur = new Node(kv); cur->_parent = parent; if (parent->kv.first > cur->_kv.first) { parent->_left = cur; } else if (parent->kv.first < cur->_kv.first) { parent->_right = cur; } //上述完成了插入的逻辑，调正平衡因子 while (parent) { //平衡因子的规则 if (parent->_left == cur) { parent->_bf--; } else if (parent->_right == cur) { parent->_bf++; } //判断是否回到父亲节点改动 if (parent->_bf == 0) { //没有啥问题，可以跳出程序 break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } //出现问题,这种情况是由情况二变化过来的，那么就是说，cur和parent向上移动了 else if (parent->_bf == 2 || parent->_bf == -2) { //这里根据规律，去固定改变平衡因子 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //双旋 if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } break; } else { assert(false); } } } void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; parent->_left = SubLR; if (SubLR) SubLR->_parent = parent; SubL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = SubL; if (parent == _root) { SubL = _root; SubL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = SubL; } else if (ppNode->_right == parent) { ppNode->_right = SubL; } SubL->_parant = ppNode; } SubL->_bf = 0; parent->_bf = 0; } void RotateL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; parent->_right = SubRL; if (SubRL) SubR->_parent = parent; SubR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = SubR; if (parent == _root) { SubR = _root; SubR->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = SubR; } else if (ppNode->_right == parent) { ppNode->_right = SubR; } SubR->_parant = ppNode; } SubR->_bf = 0; parent->_bf = 0; } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); subRL->_bf = 0; if (bf == 1) { subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else { parent->_bf = 0; subR->_bf = 0; } } void RotateLR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; int _bf = SubLR->_bf; RotateL(parent->_left); RotateR(parent); if (_bf == 0) { parent->_bf = 0; SubL->_bf = 0; SubLR->_bf = 0; } else if (_bf == 1) { parent->_bf = 0; SubL->_bf = -1; SubLR->_bf = 0; } else if (_bf == -1) { parent->_bf = 1; SubL->_bf = 0; SubLR->_bf = 0; } else { assert(false); } } void InOder() { _InOder(_root); cout << endl; } bool IsBalance() { return _IsBalance(_root); } int Height() { return _Height(_root); } int Size() { return _Size(_root); } private: int _Size(Node* root) { return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1; } int _Height(Node* root) { if (root == nullptr) return 0; return max(_Height(root->_left), _Height(root->_right)) + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); // 不平衡 if (abs(leftHeight - rightHeight) >= 2) { cout << root->_kv.first << endl; return false; } // 顺便检查一下平衡因子是否正确 if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << endl; return false; } return _IsBalance(root->_left) && _IsBalance(root->_right); } void _InOder(Node* _root) { if (_root == nullptr) { return; } InOder(_root->_left); cout << _root->_kv.first << " " << _root->_kv.second << endl; InOder(_root->_right); } private: Node* _root = nullptr; }; void AVLTest1() { AVLTree<int, int> at; }
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是高阶数据结构笔记，希望对你在学习高阶数据结构旅途中有所帮助！
