C++ AVL树

1.AVL树的概念

  为什么需要产生AVL树，由于二叉树中在某种特殊情况下会出现“一边高”的形状，这对于查找是极为不利的，所以就产生了AVL树。AVL树一棵空树或者具备下列性质的二叉搜索树：左右子树都是AVL树，且左右子树高度差绝对值不超过1。AVL树是一颗高度平衡的二叉搜索树，通过控制高度差来控制平衡。

  AVL树实现需要引用一个平衡因子的概念，每个节点都有一个平衡因子， 任何节点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，保证了左右子树高度差绝对值不超过1。

  AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可以控制在O(logN)。

2.AVL树的实现

2.1AVL树的结构

template<class K,class V>
struct AVLTreenode
{pair<K, V> _kv;AVLTreenode<K, V>* _left;AVLTreenode<K, V>* _right;AVLTreenode<K, V>* _parent;int _bf;AVLTreenode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<class K, class V>
class AVLTree
{typedef AVLTreenode<K, V> Node;
public:private:Node* _root = nullptr;
};

2.2 AVL树的插⼊

2.2.1 AVL树插⼊⼀个值的⼤概过程

1.插入值按照二叉树的规则进行插入

2.新增节点以后只会影响祖先的节点，也就是可能会影响部分祖先的节点，最坏情况下会影响到根节点。

3. 更新平衡因⼦过程中没有出现问题，则插⼊结束。

4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树 的⾼度，不会再影响上⼀层，所以插⼊结束。

2.2.2

平衡因⼦更新

更新原则：

• 平衡因⼦=右⼦树⾼度-左⼦树⾼度

• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。

• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在 parent的左⼦树，parent平衡因⼦--

• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停⽌条件：

• 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前 parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会 影响parent的⽗亲结点的平衡因⼦，更新结束。

• 更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说 明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所 在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向 上更新。

• 更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说 明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼ 了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新，插⼊结束。

如图更新到节点十时，平衡因子为2，10所在子树已经不平衡了，需要旋转处理。

2.3旋转

void RotateL(Node* parent)//左单选{Node* subR = parent->_right;Node* subRL = subR->_left;Node* Pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (Pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* Pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (Pparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}parent->_bf = subL->_bf = 0;}void RotateRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0)//当subRL为新增{subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1)//当subRL右节点为新增{subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1)//当subRL左节点为新增{subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}elseassert(false);}void RotateLR(Node* parent)//左右双旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateR(subL);RotateL(parent);if (bf == 0)//当subLR为新增{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1)//当subLR左节点为新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//当subLR右节点为新增{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}elseassert(false);}bool insert(pair<K, V>kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent) {if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0)break;else if (parent->_bf == 1 || parent->_bf == -1)//继续向上更新{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//需要旋转{if (parent->_bf == 2 && cur->_bf == 1)//同号需要单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//异号需要双旋{RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}elseassert(false);}}}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;}

2.4 AVL树的查找

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;}

测试代码

AVLTree<int, int> t;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e,e });}t.InOrder();