AVL树

AVL树

1.AVL树的概念

二叉搜索树虽然可以缩短查找的效率，但如果有序或接近有序二叉搜索将退化成单支树，查找元素相当于在顺序表中查找元素，效率低下。

AVL树可以很好的解决上一问题，它的本质是一棵平衡二叉树，当向二叉树中插入新结点后，能够保证每个结点的左右子树高度差不超过1。

2.AVL树结点的定义

template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left;//左孩子 AVLTreeNode<K, V>* _right;//右孩子 AVLTreeNode<K, V>* _parent;//双亲 int _bf;//平衡因子 pair<K, V> _kv; AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };

AVL树就是在二叉搜索树的基础上引入了平衡因子，通过平衡因子实现每个结点的左右子树高度差不超过1。

3.AVL树的插入

AVL树的插入可以分为两步：

1.按照二叉搜索树的方式插入新结点。

2.调整结点的平衡因子。

bool Insert(const pair<K, V>& kv) { //1.按二叉搜索的方式插入新结点 if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } //2.调节平衡因子 while (parent) { //如果插入到父亲的右侧，父亲的平衡因子+1 //如果插入到父亲的左侧，父亲的平衡因子-1 if (cur == parent->_right) parent->_bf++; else parent->_bf--; //父亲的平衡因子等于0，停止调节 if (parent->_bf == 0) break; //父亲的平衡因子等于1或-1，继续向上调节 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } //父亲的平衡因子等于2或-2，需要进行选择处理。 else if (parent->_bf == 2 || parent->_bf == -2) {} } return true; }

4.AVL树的旋转

1.新结点插入较高左子树的左侧—右单旋

void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* pparent = parent->_parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } parent->_bf = 0; subL->_bf = 0; }

2.新结点插入较高右子树的右边—左单旋

void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* pparent = parent->_parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } parent->_bf = 0; subR->_bf = 0; }

3.新结点插入较高左子树的右侧—左右双旋

void RotateLR(Node* parent) { Node* subL = parent->_right; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); 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 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } }

4.新结点插入较高右子树的左侧—右左双旋

void RotateLR(Node* parent) { Node* subL = parent->_right; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); 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 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } }

4.AVL树的实现

#pragma once #include<iostream> using namespace std; template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; pair<K, V> _kv; AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } while (parent) { if (cur == parent->_right) 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) { if (cur->_bf == 1) { RotateL(parent); } else if (cur->_bf == -1) { RotateRL(parent); } } else if(parent->_bf == -2) { if (cur->_bf == -1) { RotateR(parent); } else if (cur->_bf == 1) { RotateLR(parent); } } break; } } return true; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* pparent = parent->_parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } parent->_bf = 0; subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* pparent = parent->_parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } parent->_bf = 0; 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 == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == 0) { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } } void RotateLR(Node* parent) { Node* subL = parent->_right; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); 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 if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } void InOrder() { _InOrder(_root); } int Height(Node* root) { if (root == nullptr) return 0; int lefeHeight = Height(root->_left); int rightHeight = Height(root->_right); return lefeHeight > rightHeight ? lefeHeight + 1 : rightHeight + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int lefeHeight = Height(root->_left); int rightHeight = Height(root->_right); return abs(lefeHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } bool IsBalance() { return _IsBalance(_root); } private: Node* _root = nullptr; };