福安做网站最好,网站做301根目录在哪里,网站的程序怎么做,嘉兴外贸网站建前面我们对 map / multimap / set / multiset 进行了简单的介绍#xff0c;可以发现#xff0c;这几个容器有个共同点是#xff1a;其底层都是按照二叉搜索树来实现的。 但是二叉搜索树有其自身的缺陷#xff0c;假如往树中插入的元素有序或者接近有序#xff0c;二叉搜索… 前面我们对 map / multimap / set / multiset 进行了简单的介绍可以发现这几个容器有个共同点是其底层都是按照二叉搜索树来实现的。 但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成 O(N)因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理即采用 平衡树 来实现。 一、AVL树高度平衡二叉搜索树
1、概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 最优情况下有 n 个结点的二叉搜索树为完全二叉树查找效率为O(log₂N)。最差情况下有 n 个结点的二叉搜索树退化为单支树查找效率为O(N)。 因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法当向二叉搜索树中 插入新结点 后如果能 保证每个结点的左右子树高度之差的绝对值不超过 1 需要对树中的结点进行调整即可降低树的高度从而减少平均 搜索长度。 一棵 AVL 树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是 AVL 树。左右子树高度之差简称平衡因子的绝对值不超过 1-1/0/1。 如果一棵二叉搜索树是高度平衡的它就是 AVL 树。如果它有 n 个结点其高度可保持在 O(log₂n)搜索时间复杂度 O(log₂n)。 为什么左右子树高度差不规定成0呢 因为在 2、4 等节点数的情况下不可能做到左右高度相等的情况。 2、AVL 树节点的定义 AVL 树节点的定义 AVL 树节点是一个 三叉链结构除了 指向左右孩子的指针还有一个 指向其父亲的指针数据域是键值对即 pair 对象还引入了平衡因子用来判断是否需要进行平衡操作。 // AVL树节点的定义KV模型
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeT* _left; // 该节点的左孩子AVLTreeNodeT* _right; // 该节点的右孩子AVLTreeNodeT* _parent; // 该节点的双亲指针pairK, V _kv; // 键值对int _bf; // 该节点的平衡因子(balance factor) 右子树高度-左子树高度// 构造函数AVLTreeNode(const pariK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};// AVL树的定义KV模型
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:// 成员函数private:Node* _root;
} 3、AVL树的插入 AVL 树就是在二叉搜索树的基础上引入了平衡因子因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步 按照二叉搜索树的方式插入新节点到 AVL 树中。新节点插入后AVL 树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否破坏了 AVL 树的平衡控制树的平衡旋转操作。 // 插入节点
bool Insert(const pairK, V kv)
{// 如果树为空则直接插入节点if (_root nullptr){_root new Node(kv);return true;}// 如果树不为空找到适合插入节点的空位置Node* parent nullptr; // 记录当前节点的父亲Node* cur _root; // 记录当前节点while (cur) // while循环结束说明找到适合插入节点的空位置了{if(kv.first cur-_kv.first) // 插入节点键值k大于当前节点{parent cur;cur cur-_right;}else if(kv.first cur-_kv.first) // 插入节点键值k小于当前节点{ parent cur;cur cur-_left;}else // 插入节点键值k等于当前节点{return false;}}// 插入新节点cur new Node(kv); // 申请新节点// 判断当前节点是父亲的左孩子还是右孩子if (cur-_kv.first parent-_kv.first){parent-_right cur; }else{parent-_left cur;}cur-_parent parent;// 控制平衡// 1、更新平衡因子// ...return true;
} ⚪更新平衡因子
1插入新节点cur 插入后parent 的平衡因子一定需要调整在插入之前parent 的平衡因子分为三种情况-101分以下两种情况 如果 cur 插入到 新节点父亲parent 的左侧只需给 父亲parent 的平衡因子--_bf--即可。如果 cur 插入到 新节点父亲parent 的右侧只需给 父亲parent 的平衡因子_bf即可。 2新节点父亲的平衡因子更新以后又会分为 3 种情况
此时parent的平衡因子可能有三种情况0正负 1 正负 2。 如果更新以后parent 的平衡因子是 0则说明插入之前 parent 的平衡因子之前一定为 1/-1说明父亲所在子树高度没变因为把矮的那边给填补上了此时满足 AVL 树的性质插入成功不需要继续往上更新。如果更新以后parent 的平衡因子是 1/-1则说明插入之前 parent 的平衡因子 一定为 0说明父亲所在子树高度增加需要继续往上更新。最坏情况往上一直更新到根节点。如果更新以后parent 的平衡因子是 2/-2说明父亲所在子树出现了不平衡需要对其进行旋转处理。 // 插入节点
bool Insert(const pairK, V kv)
{// 控制平衡// 1、更新平衡因子while (parent) // 最坏情况更新到根节点{// 更新双亲的平衡因子if (cur parent-_left) // 新节点插入在父亲的左边parent-_bf--;else // 新节点插入在父亲的右边parent-_bf;// 更新后检测双亲的平衡因子if (0 pParent-_bf){ break;}//else if (1 parent-_bf || -1 parent-_bf)else if (abs(parent-_bf) 1) // 插入前双亲的平衡因子是0插入后双亲的平衡因为为1 或者 -1 说明以双亲为根的二叉树的高度增加了一层因此需要继续向上调整{cur parent;parent cur-_parent;}else if (abs(parent-_bf) 2) // 双亲的平衡因子为正负2违反了AVL树的平衡性需要对以parent为根的树进行旋转处理{// 1、父节点的右边高左边低需要往左旋if (parent-_bf 2 cur-_bf 1) {RotateL(parent); // 左单旋}// 2、父节点的左边高右边低需要往右旋else if ((parent-_bf -2 cur-_bf -1)){RotateR(parent); // 右单旋}// 3、父节点的左边高且父节点左孩子的右边高else if (parent-_bf -2 cur-_bf 1) {RotateLR(parent); // 左右双旋}// 4、父节点的右边高且父节点右孩子的左边高else if (parent-_bf 2 cur-_bf -1){RotateRL(parent); // 右左双旋}break; // 旋转完成树已平衡退出循环}// 除了上述3种情况平衡因子不可能有其它的值报错处理else{assert(false);}}return true;
} 4、AVL树的旋转 如果在一棵原本是平衡的 AVL 树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。 根据节点插入位置的不同AVL 树的旋转分为四种 旋转的本质在遵循二叉搜索树的规则下让左右均衡降低整棵树的高度。
该进行哪种旋转操作 引发旋转的路径是直线就是单旋如果是折线就是双旋。 注意此处看到的树可能是一颗完整的树也可能是一颗子树。 1新节点插入较高左子树的左侧 —— 左左右单旋
将新的节点插入到了 parent 左孩子的左子树上导致的不平衡的情况。 上图在插入前AVL 树是平衡的新节点插入到 30 的左子树注意此处不是左孩子中30 左子树增加了一层导致以 60 为根的二叉树不平衡要让 60 平衡只能将 60 左子树的高度减少一层右子树增加一层即将左子树往上提这样 60 转下来因为 60 比 30 大只能将其放在 30 的右子树而如果 30 有右子树右子树根的值一定大于 30小于 60只能将其放在 60 的左子树旋转完成后更新节点的平衡因子即可。 【引发右单旋的条件】 父亲左边高右边低所以要让父亲往右旋。parent 的平衡因子为 -2parent 左孩子平衡因子为 -1观察发现平衡因子都是负数说明是左边高也说明了引发旋转的路径是一条直线所以我们要右旋操作。 【右单旋操作】 1、让 subL 的右子树 subLR 成为 parent 的左子树因为 subLR 的右子树根节点值 30 60。 2、让 parent 成为 subL 的右子树因为 60 30。 3、让 subL 变成这个子树的根。 这一步操作前需要先判断下parent 是根节点还是一个普通子树 如果是根节点旋转完成后则更新 subL 为新的根节点。如果是普通子树可能是某个节点的左子树也可能是右子树这里作一个判断然后更新 subL 为这个子树的根节点。 4、根据树的结构更新 parent 和 subL 的平衡因子为 0。 在旋转过程中更新双亲指针的指向有以下几种情况需要考虑 30 节点的右孩子可能存在也可能不存在。subL 的右子树 subLR 可能存在也可能为空。当不为空时才更新 subL 右子树 subLR 的双亲指针指向。60 可能是根节点也可能是子树。旋转完成后subL 的双亲节点可能是空也可能是 parent 原先的父节点。所以在更新 subL 的双亲指针前需要判断下。 依次调整 subLR、parent、subL 的位置和双亲指针的指向。
// 右单旋
void _RotateR(Node* parent)
{ Node* subL parent-_left; // subL : parent的左孩子Node* subLR subL-_right; // subLR : parent左孩子的右孩子// 旋转完成之后让subL的右子树subLR成为parent的左子树parent-_left subLR;// 如果subLR存在更新subLR的双亲指针指向parentif (subLR){subLR-_parent parent;}// 因为parent可能是棵子树因此在更新其双亲前必须先保存parent的父节点Node* ppNode parent-_parent;// 让parent成为subL的右子树subL-_right parent;// 更新parent的双亲指针指向subLparent-_parent subL;// 如果parent是根节点根新指向根节点的指针if (_root parent){_root subL; // 更新subL为新的根subL-_parent nullptr; // 更新subL的双亲指针指向空}// parent不是根节点就是一个普通子树else{// 判断parent原先是左孩子还是右孩子if (ppNode-_left parent){ppNode-_left subL; // parent原先的双亲节点接管subLsubL为这个子树的根}else{ppNode-_right subL;}subL-_parent ppNode; // 更新subL的双亲指针}// 根据调整后的结构更新部分节点的平衡因子parent-_bf pSubL-_bf 0;
} 2新节点插入较高右子树的右侧 —— 右右左单旋 【引发左单旋的条件】 父亲右边高左边低所以要让父亲往左旋。parent 的平衡因子为 2parent 左孩子平衡因子为 1观察发现平衡因子都是正数说明是右边高也说明了引发旋转的路径是一条直线所以我们要右旋操作。 【右单旋操作】 1、让 subR 的左子树 subRL 成为 parent 的右子树因为 subRL 的左子树根节点值 30 60。 2、让 parent 成为 subR 的左子树因为 30 60。 3、让 subR 变成这个子树的根。 这一步操作前需要先判断下parent 是根节点还是一个普通子树 如果是根节点旋转完成后则更新 subR 为新的根节点。如果是普通子树可能是某个节点的左子树也可能是右子树这里作一个判断然后更新 subR 为这个子树的根节点。 4、根据树的结构更新 parent 和 subR 的平衡因子为 0。 在旋转过程中更新双亲指针的指向有以下几种情况需要考虑 subR 的左子树 subRL 可能存在也可能为空。当不为空时才更新 subR 左子树 subRL 的双亲指针指向。旋转完成后subR 的双亲节点可能是空也可能是 parent 原先的父节点。所以更新 subR 的双亲指针前需要判断下。 依次调整 subRL、parent、subR 的位置和双亲指针的指向。
// 左单旋
void treeRotateLeft(Node* parent)
{Node* subR parent-_right; // subR父亲的右孩子Node* subRL subR-_left; // subRL父亲的右孩子的左孩子大于父亲小于subR// 让subRL成为父亲的右子树parent-_right subRL;// 如果subRL不为空if (subRL){subRL-_parent parent; // 更新subRL双亲指针指向parent}// 因为parent可能是棵子树因此在更新其双亲前必须先保存parent的父节点Node* ppNode parent-_parent;// 让parent成为subR的左子树subR-_left parent; // 更新parent双亲指针的指向parent-_parent subR;// 判断parent是不是根节点if (parent _root){_root subR; // subR为新的根subR-_parent nullptr; // subR双亲指针指向空}// 不是根节点就是一个普通子树else{// 判断parent原先是左孩子还是右孩子if (ppNode-_left parent){ppNode-_left subR; // parent原先的双亲节点接管subRsubR为这个子树的根}else{ppNode-_right subR;}subR-_parent ppNode; // 更新subR的双亲指针}// 根据树的结构更新parent和subR的平衡因子parent-_bf subR-_bf 0;
}3新节点插入较高左子树的右侧 —— 左右先左单旋再右单旋左右双旋 将新的节点插入到了 parent 左孩子的右子树上导致的不平衡的情况。 这时我们需要的是先对 parent 的右孩子进行一次左旋再对 parent 进行一次右旋。 将双旋变成单旋后再旋转即先对 30 进行左单旋然后再对 90 进行右单旋旋转完成后再考虑平衡因子的更新。 旋转之前60 的平衡因子可能是 -1/0/1旋转完成之后根据情况对其他节点的平衡因子进行调整。 【h 0】 【引发双旋的条件】 引发旋转的路径是直线就是单旋如果是折线就是双旋。 parent 的平衡因子为 -2parent 左孩子的平衡因子为 1观察发现平衡因子是一负一正说明左孩子右边高父亲左边高也说明了引发旋转的路径是一条折线所以我们要先对左孩子进行左旋操作再对父亲进行右旋操作。 左右双旋操作后根据树的结构更新平衡因子时需要注意 插入新节点的位置不同经过左右双旋后得到树的结构也会有所不同平衡因子也会有所不同有以下三种情况 新节点插入到了 parent 左孩子的右子树的左边。新节点插入到了 parent 左孩子的右子树的右边。新节点就是 parent 左孩子的右孩子。 这里可以观察到一个现象根据这个现象就很好推出旋转后的平衡因子 节点 60 的左右子树被分走了左子树最终成为了节点 30 的右子树右子树最终成了节点 90 的左子树。 void _RotateLR(PNode pParent)
{Node* subL parent-_left; // 记录parent的左孩子Node* subLR subL-_right; // 记录parent的左孩子的右孩子// 旋转之前因为插入新节点的位置不同subLR的平衡因子可能是-1/0/1int bf subLR-_bf; // 记录subLR的平衡因子// 先对parent的左孩子进行左单旋RotateL(parent-_left);// 再对parent进行右单旋RotateR(parent);// 旋转完成之后根据情况对其他节点的平衡因子进行调整subLR-_bf 0;if (bf -1){parent-_bf 1;subL-_bf 0;}else if (bf 1){parent-_bf 0;subL-_bf -1;} else if (bf 0){parent-_bf 0;subL-_bf 0;}else{assert(false);}
} 4新节点插入较高右子树的左侧 —— 右左先右单旋再左单旋右左双旋 将新的节点插入到了 parent 右孩子的左子树上导致的不平衡的情况。 这时我们需要的是先对 parent 的右孩子进行一次右旋再对 parent 进行一次左旋。 【h 1】 【引发双旋的条件】 引发旋转的路径是直线就是单旋如果是折线就是双旋。 parent 的平衡因子为 2 parent 右孩子平衡因子为 -1观察发现平衡因子是一正一负说明右孩子左边高父亲右边高也说明了引发旋转的路径是一条折线所以我们要先对右孩子进行右旋操作再对父亲进行左旋操作。 左右双旋操作后根据树的结构更新平衡因子时需要注意 插入新节点的位置不同经过右左双旋后得到树的结构也会有所不同平衡因子也会有所不同有以下三种情况 新节点插入到了 parent 右孩子的左子树的左边。新节点插入到了 parent 右孩子的左子树的右边。新节点就是 parent 右孩子的左孩子。 这里可以观察到一个现象根据这个现象就很好推出旋转后的平衡因子 节点 60 的左右子树被分走了左子树 b 最终成了节点 30 的右子树右子树 c 最终成了节点 90 的左子树。 // 右左双旋
void treeRotateRL(Node* parent)
{Node* subR parent-_right; // 记录parent的右孩子Node* subRL subR-_left; // 记录parent的右孩子的左孩子// 旋转之前因为插入新节点的位置不同subRL的平衡因子可能为-1/0/1int bf subRL-_bf; // 记录subRL的平衡因子RotateR(parent-_right); // 先对parent的右孩子进行右单旋RotateL(parent); // 再对parent进行左单选// 旋转完成之后根据树的结构对其他节点的平衡因子进行调整subRL-_bf 0;if (bf -1){parent-_bf 0;subR-_bf 1;}else if (bf 1){parent-_bf -1;subR-_bf 0;}else if(bf 0){parent-_bf 0;subR-_bf 0;}else{assert(false);}
} 【总结】 假如以 parent 为根的子树不平衡即 parent 的平衡因子为 2/-2分以下情况考虑 1、parent 的平衡因子为 2说明 parent 的右子树高设 parent 的右子树的根为 subR。 当 subR 的平衡因子为 1 时执行左单旋。当 subR 的平衡因子为 -1 时执行右左双旋。 2、parent 的平衡因子为 -2说明 parent 的左子树高设 parent 的左子树的根为 subL。 当 subL 的平衡因子为 -1 时执行右单旋。当 subL 的平衡因子为 1 时执行左右双旋。 旋转完成后原 parent 为根的子树个高度降低已经平衡不需要再向上更新。 5、AVL树的验证 AVL 树是在二叉搜索树的基础上加入了平衡性的限制因此要验证 AVL 树可以分两步 1、验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树。 2、验证其为平衡树 每个节点子树高度差的绝对值不超过 1注意节点中如果没有平衡因子。节点的平衡因子是否计算正确。 1首先写一个计算当前树高度的函数 // 计算当前树的高度
int Height(Node* root)
{// 当前树为空则高度为0if (root nullptr)return 0;// 当前树的高度 左右子树中高度最大的那个加1return max(Height(root-_left), Height(root-_right)) 1;
} 2检查AVL树是否平衡【思路一】自顶向下的暴力解法 bool IsBalance1()
{return _IsBalance(_root);
}bool _IsBalance1(Node* root)
{// 当前树为空说明是平衡的if (root nullptr)return true;// 当前树不为空计算左右子树的高度int leftHT Height(root-_left);int rightHT Height(root-_right);int diff rightHT - leftHT;if (diff ! root-_bf) // 检查当前树的平衡因子是否计算正确{cout root-_kv.first 平衡因子异常 endl;return false;}// 左右子树高度相减的绝对值小于2说明当前树是平衡的则继续往下判断其它子树return abs(diff) 2 _IsBalance(root-_left) _IsBalance(root-_right);
} 3检查AVL树是否平衡【思路二】自底向上的高效解法动态规划前一个子问题的解能够用于后一个问题求解 bool IsBalance2()
{return _IsBalance2(_root) ! -1;
}int _IsBalance2(Node* root)
{// 先判断当前树的左、右子树是否平衡再判断当前树是否平衡// 不平衡返回-1平衡则返回当前树的高度// 当前树为空返回高度0if (root nullptr)return 0;// 当前树不为空分别计算左右子树的高度int leftHeight _IsBalance2(root-_left);int rightHeight _IsBalance2(root-_right);int diff rightHT - leftHT;if (diff ! root-_bf) // 检查当前树的平衡因子是否计算正确{cout 平衡因子异常: root-_kv.first endl;}// 左子树高度等于-1、右子树高度等于-1、左右子树高度差的绝对值大于1说明当前树不平衡if (leftHeight -1 || rightHeight -1 || abs(diff) 1)return -1;// 运行到这里来了说明当前树是平衡的返回当前树的高度return max(leftHeight, rightHeight) 1;
} 4【思路三】 bool _IsBalanceTree3(Node* root)
{// 空树也是AVL树if (nullptr root)return true;// 计算pRoot节点的平衡因子即pRoot左右子树的高度差int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者pRoot平衡因子的绝对值超过1则一定不是AVL树if (diff ! root-_bf || (diff 1 || diff -1))return false;// pRoot的左和右如果都是AVL树则该树一定是AVL树return _IsBalanceTree3(root-_left) _IsBalanceTree3(root-_right);} 3、验证用例 常规场景 1{16, 3, 7, 11, 9, 26, 18, 14, 15}特殊场景 2{4, 2, 6, 1, 3, 5, 15, 7, 16, 14} 6、AVL树的删除了解 因为 AVL 树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不过与删除不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 具体实现可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。 7、AVL 树的性能 AVL 树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过 1这样可以保证查询时高效的时间复杂度即 O(logN)。 但是如果要对 AVL 树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑 AVL 树但一个结构经常修改就不太适合。
