数据结构-二叉平衡树
一.平衡二叉树
二叉搜索树插入的次序不同导致不同的深度和平均查找长度ASL
左右子树高度差不超过绝对值1的二叉搜索是二叉平衡树
二.平衡二叉树的调整
在右子树的右子树上的插入做RR插入
把被破坏节点的右子树变成跟节点并把这个右子树的左子树挂载到原来被破坏的结点的右子树，被破坏的节点作为右儿子
插入节点在被破坏者右边的右边是RR
不一定插在某个节点的右边
在左子树的左子树上的插入做LL插入
把被破坏节点的左子树变成跟节点并把这个左子树的右子树挂载到原来被破坏的结点的左子树，被破坏的节点作为左儿子
插入节点在被破坏者左边的左边是LL
两个节点的平衡性被破坏了，只要考虑最下面的节点这个节点平衡了上面节点自然就平衡了
被破坏结点左边的右边插入,叫做LR插入
所以需要关注May,Aug,Mar三个结点将这三个结点的中间值结点变为跟结点,这里的中间结点是Mar所以需要先将提上来，左旋转,然后再进行右旋转
第一次旋转(左旋转)
第二次旋转(右旋转)
RL旋转与LR旋转相似
原文地址：https://blog.csdn.net/wwwwwgery/article/details/143865265
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！