AVL发生旋转2.2.1

-2或者2的时候就代表这棵树不平衡了就需要进行旋转。

这时候更新也停止了因为要进行旋转了

更新后的parent平衡因子0说明parent所在的子树的高度不变不会再影响祖先不用再继续往上更新

-1说明parent所在的子树的高度发生改变会影响祖先要继续往上更新

-2说明parent所在的子树的高度发生改变且不平衡想办法调整平衡对parent所在子树进行旋转让他平衡

更新到根节点

cur-left比cur小所以cur-left做cur的左没有问题

核心操作

0又分为两种情况插入节点是父节点的左子树或者插入节点是父节点的右子树

2.2.4

_bf;//new一个AVLTreeNode节点的时候就会调用这个构造函数//

pairK,

kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}

};template

kv){//搜索的插入//...控制平衡//新增在左边父节点的平衡因子--

(_root

cur-_left;}else{assert(插入相同的节点);}}//走到这里找到了要插入的位置

将cur插入进去cur

cur;//因为是三叉链所以cur的_parent指针还要指回去cur-_parent

parent;//走到这里插入完成了。

需要检查平衡因子判断是否平衡不平衡要进行旋转while

(parent){//插入的位置是左孩子bf--;插入的位置是右孩子bfif

(cur

parent-_left)parent-_bf--;elseparent-_bf;//接下来要判断根据不同的平衡因子进行不同的更新的情况if

(parent-_bf

//如果插入之后parent的平衡因子等于-1或者1说明还要向上调整{cur

parent;parent

-2){//如果平衡因子走到这里说明要发生旋转了左旋右旋双旋。

if

(parent-_bf

1){//这种情况是左单旋为什么RotateL(parent);}else

(parent-_bf

-1){//左边高还要往左边插入所以要发生右单旋RotateR(parent);}else

(parent-_bf

左右双旋RotateLR(parent);}else{assert(平衡因子出错);}break;}else{assert(平衡因子出错);}}return

true;}void

cur-_left;//1.把curleft给parent的right

parent的_right指向curleftparent-_right

curleft;//判断curleft是否为空如果不为空就curleft的父节点指回去if

parent;}//2.parent的right给cur的left

parent;//3.判断parent是不是当前的根节点,如果是cur的_parent就为空。

如果不是cur的_parent还要指向ppnodeNode*

ppnode

parent-_parent;//4.parent还要往回指因为是三叉链parent-_parent

cur;if

nullptr;}else{//如果不是根节点就要判断是ppnode的左孩子还是右孩子if

(ppnode-_left

cur-_right;//1.让parent的左指向cur的右parent-_left

curright;if

(curright){//第一次往回指curright-_parent

ppnode

parent-_parent;//2.cur的右指向parentcur-_right

cur;if

curright-_bf;RotateL(cur);RotateR(parent);//根据不同的情况修改平衡因子if

(bf

//提前保存下来RotateR(cur);RotateL(parent);if

(bf

//说明插入的位置是curleft的右边{parent-_bf

-1;cur-_bf

Inorder(){_Inorder(_root);}private:void

_Inorder(Node*

nullptr)return;_Inorder(cur-_left);cout

cur-_kv.first

e));}t.IsBalance();t.Inorder();

}int