上海网站开发公司排名,温州专业手机网站制作哪家便宜,广州网站排名优化价格,购物网站建设目标概述AVL树 1. 概念2. AVL节点的定义3. AVL树插入3.1 旋转 4.AVL树的验证 1. 概念
AVL树是一种自平衡二叉搜索树。它的每个节点的左子树和右子树的高度差#xff08;平衡因子#xff0c;我们这里按右子树高度减左子树高度#xff09;的绝对值不超过1。AVL的左子树和右子树都是AV… AVL树 1. 概念2. AVL节点的定义3. AVL树插入3.1 旋转 4.AVL树的验证 1. 概念
AVL树是一种自平衡二叉搜索树。它的每个节点的左子树和右子树的高度差平衡因子我们这里按右子树高度减左子树高度的绝对值不超过1。AVL的左子树和右子树都是AVL树。比起二叉搜索树AVL树可以很好的优化二叉搜索树最坏的情况使查询的效率达到Olog2 N。
2. AVL节点的定义
和搜索二叉树节点相比AVL树节点多了一个父节点和平衡因子不是必要需要维护。
templateclass T
typedef struct AVLTreeNode
{AVLTreeNode(const T data):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_bf(0){};//左节点、右节点、父节点AVLTreeNodeT* _pLeft;AVLTreeNodeT* _pRight;AVLTreeNodeT* _pParent;T _data;//平衡因子int bf;
};3. AVL树插入
和搜索二叉树的插入操作相比较AVL树的插入需要多维护父节点和平衡因子。维护父节点比较简单我们需要学习的是维护平衡因子。
当我们按照搜索二叉树的逻辑插入一个节点后在插入这个节点之前父节点的平衡因子可能是-1/0/1这三种如果该节点插入到父节点的左边需要将平衡因子减1插入到右边则加1。所以插入之后平衡因子有这几种情况±1/0/±2。如果是±1那么需要继续判断上面节点的平衡因子、如果是0那么不需要判断了、如果是±2那么就需要进行旋转操作。
3.1 旋转
我们先说结论1、旋转之后节点所在子树的高度会回到插入之前。2、旋转不会对上面节点平衡因子产生影响。
右单旋 初始情况
// 右单旋void RotateR(Node* pParent){Node* parent pParent-_parent;//变成局部的根Node* pParentL pParent-_left;Node* pParentR pParentL-_right;if (pParent _proot)_proot pParentL;pParent-_left pParentR;if (pParentR)pParentR-_parent pParent;pParentL-_left pParent;pParent-_parent pParentL;pParentL-_parent parent;//只需要修改pParent和pParentL的平衡因子pParent-_bf 0;pParentL-_bf 0;return;}旋转之后情况
左单旋 初始情况
// 左单旋void RotateL(Node* pParent){Node* parent pParent-_parent;//变成局部的根Node* pParentR pParent-_right;Node* pParentL pParentR-_left;//如果pParnet为根则要修改根if (pParent _proot)_proot pParentR;pParent-_right pParentL;if (pParentL)pParentL-_parent pParent;pParentR-_left pParent;pParent-_parent pParentR;pParentR-_parent parent;//只需要修改pParent和pParentR的平衡因子pParent-_bf 0;pParentR-_bf 0;return;}旋转之后的情况
左右双旋 初始情况插入可以插入到左边或右边情况不同平衡因子也会不同
// 左右双旋void RotateLR(Node* pParent){Node* pParentL pParent-_left;Node* pParentLR pParentL-_right;int bf pParentLR-_bf;RotateL(pParentL);RotateR(pParent);if (bf 0){pParent-_bf 0;pParentL-_bf 0;pParentLR-_bf 0;}else if (bf 1){pParentL-_bf -1;pParentLR-_bf 0;pParent-_bf 0;}else if (bf -1){pParentL-_bf 0;pParent-_bf 1;pParentLR-_bf 0;}return;}旋转之后的情况
右左双旋转 初始情况
// 右左双旋void RotateRL(Node* pParent){Node* pParnetR pParent-_right;Node* pParentRL pParnetR-_left;int bf pParentRL-_bf;RotateR(pParnetR);RotateL(pParent);if (bf 0){pParent-_bf 0;pParnetR-_bf 0;pParentRL-_bf 0;}else if (bf -1){pParent-_bf 0;pParnetR-_bf 1;pParentRL-_bf 0;}else if (bf 1){pParent-_bf -1;pParnetR-_bf 0;pParentRL-_bf 0;}return;}旋转之后的情况
4.AVL树的验证
验证为二叉搜索树 中序遍历得到有序的序列就可以证明为二叉搜索树。验证为平衡树 看平衡因子
bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}
