深圳夫博网站建设有限公司,白人与黑人做爰网站,wordpress代码中文注释,该网站受海外服务器保护AVL树 1. AVL树的概念2. AVL树的实现2.1 节点的定义2.2 插入2.3 是否是AVL树 3. AVL树与红黑树 1. AVL树的概念
AVL树是一棵二叉搜索树#xff0c;但它的每个节点的左右子树的高度差的绝对值不超过1#xff0c;且它的子树也是平衡二叉树。左右子树的高度差也叫平衡因子… AVL树 1. AVL树的概念2. AVL树的实现2.1 节点的定义2.2 插入2.3 是否是AVL树 3. AVL树与红黑树 1. AVL树的概念
AVL树是一棵二叉搜索树但它的每个节点的左右子树的高度差的绝对值不超过1且它的子树也是平衡二叉树。左右子树的高度差也叫平衡因子平衡因子 右子树叶的高度 - 左子树的高度。 将AVL树与满二叉树对比看看AVL的效率如何 2. AVL树的实现
2.1 节点的定义
//节点
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;//平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};2.2 插入
AVL树是二叉搜索树所以首先按照二叉搜索树的规矩插入。插入后再考虑插入节点后AVL树是否平衡。有个例子
1更新后parent的平衡因子如果是1或者-1说明parent所在子树的高度发生变化会影响祖先需要沿着到root的路径往上更新。
2更新后parent的平衡因子如果是0说明parent所在子树的高度不变不用继续沿着到root的路径往上更新。
3更新后parent的平衡因子如果是2或者-2说明parent所在子树的高度变化且不平衡对parent的子树进行旋转使其平衡。 4如果parent是头节点对parent进行旋转后记得更新根节点。
旋转的原理
节点的插入可以分为以下几种情况 1左单旋新节点插入在较高右子树的右侧 2右单旋新节点插入较高左子树的左侧
3双旋新节点插入较高右子树的左侧
4双旋新节点插入较高左子树的右侧 代码
templateclass K, class V
class AVLTree
{
public:typedef AVLTreeNodeK, V Node;bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent 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{return false;}}cur new Node(kv);if (parent-_kv.first cur-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//更新平衡因子while (parent){if (parent-_left cur){--parent-_bf;}else{parent-_bf;}//如果更新完平衡因子为0说明其左右子树等高已经平衡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){//新节点插入较高右子树的右侧需要将parent左旋if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//新节点插入较高左子树的左侧需要将parent右旋else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//新节点插入较高右子树的左侧需要先将cur右旋再将parent左旋else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}//新节点插入较高左子树的右侧需要先将cur左旋再将parent右旋else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else{assert(false);}break;}else{assert(false);}}return true;}//左旋void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;//不要忘记父节点的链接Node* pparent parent-_parent;parent-_parent cur;//要考虑parent的parent是否存在if (pparent){if (pparent-_left parent){pparent-_left cur;}else{pparent-_right cur;}cur-_parent pparent;}else{_root cur;cur-_parent nullptr;}//平衡因子置为0parent-_bf cur-_bf 0;}//右旋void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright){curright-_parent parent;}cur-_right parent;Node* pparent parent-_parent;parent-_parent cur;if (pparent){if (pparent-_left parent){parent-_left cur;}else{parent-_right cur;}cur-_parent pparent;}else{_root cur;cur-_parent nullptr;}parent-_bf cur-_bf 0;}//双旋新节点插入较高右子树的左侧void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;//先右旋再左旋RotateR(cur);RotateL(parent);if (curleft-_bf 0){parent-_bf 0;cur-_bf 0;}else if (curleft-_bf 1){parent-_bf -1;cur-_bf 0;}else if (curleft-_bf -1){parent-_bf 0;cur-_bf 1;}}//双旋新节点插入较高左子树的右侧void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;//先左旋再右旋RotateL(cur);RotateR(parent);//更新平衡因子if (curright-_bf 0){parent-_bf 0;cur-_bf 0;}else if (curright-_bf 1){parent-_bf 0;cur-_bf -1;}else if (curright-_bf -1){parent-_bf 1;cur-_bf 0;}}
private:Node* _root nullptr;
};2.3 是否是AVL树
如果一棵AVL树不平衡那么它的左右子树的高度差的绝对值超过2旋转出现问题。如果要判断一棵树是否是AVL树是否平衡不能通过平衡因子判断因为旋转出现问题那么平衡因子也会出现问题所以只能通过高度来判断。 代码
// 根据AVL树的概念验证pRoot是否为有效的AVL树bool IsAVLTree(){return IsAVLTree(_root);}bool IsAVLTree(Node* pRoot){//不能依赖平衡因子容易监守自盗。如果旋转出现问题平衡因子也会有问题//所以直接通过高度来判断if (pRoot nullptr){return true;}int leftHeight Height(pRoot-_left);int rightHeight Height(pRoot-_right);//abs返回参数的绝对值return abs(leftHeight - rightHeight) 2 IsAVLTree(pRoot-_left) IsAVLTree(pRoot-_right);}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}3. AVL树与红黑树
插入时要维护其绝对平衡旋转的次数比较多如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合
红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优
AVL树和红黑树都是平衡二叉树。在查询效率方面AVL树追求绝对平衡红黑树要求最长路径不超过最短路径的两倍AVL查询数据效率比红黑树高但是对于CPU而言都是属于logN这个量级的。AVL树追求控制严格平衡是需要付出代价的插入和删除已需要进行大量的旋转。红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在插入和删除方面红黑树效率更高。综上红黑书更优实际运用的多。
