赞
踩
二叉搜索树中,如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,如何解决?
AVL树具有以下性质:
如果一棵二叉搜索树是高度平衡的,它就是AVL树
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; // balance factor AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} };
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->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // 控制平衡 // 1.更新平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (abs(parent->_bf) == 1) { parent = parent->_parent; // 继续向上更新 cur = cur->_parent; } else if(abs(parent->_bf) == 2) { // parent所在子树已经失衡,旋转调整 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) { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); // 理论不会走到这 } break; } else { assert(false); // 理论不会走到这 } } return true; }
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* grandParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (grandParent->_left == parent) { grandParent->_left = subL; } else { grandParent->_right = subL; } subL->_parent = grandParent; } subL->_bf = parent->_bf = 0; }
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) // 防止subRL本来就为空,对空指针访问 { subRL->_parent = parent; } // 用于判断原来的parent是否是子树 Node* grandParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (grandParent->_left == parent) { grandParent->_left = subR; } else { grandParent->_right = subR; } subR->_parent = grandParent; } subR->_bf = parent->_bf = 0; }
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); subLR->_bf = 0; if (bf == 1) { parent->_bf = 0; subL->_bf = -1; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; } else if (bf == 0) // 原来的树/子树只有这三个节点 { parent->_bf = 0; subL->_bf = 0; } else { assert(false); // 理论不会走到这 } }
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); subRL->_bf = 0; if (bf == 1) { parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else if (bf == 0) { parent->_bf = subR->_bf = 0; } else { assert(false); // 理论不会走到这 } }
void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { return _IsBalance(_root); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } bool _IsBalance(Node* root) { if (root == nullptr) { return true; } int leftHeight = Height(root->_left); int rightHeight = Height(root->_right); int diff = rightHeight - leftHeight; if (diff != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return abs(diff) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } int Height(Node* root) { if (root == nullptr) { return 0; } return max(Height(root->_left), Height(root->_right)) + 1; //统计高度为后序 }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。