企业官网建设流程全解析

平衡因子

(左子树高度 - 右子树高度)的绝对值 <= 1

旋转操作

左旋：向左旋转，冲突的左孩变右孩

冲突的左孩变成了右孩，两个中序遍历是一致的，说明它俩是等价的。

右旋：向右旋转，重推的右孩变左孩

冲突的右孩变左孩

什么时候左旋，什么时候右旋

LL型

失衡节点：平衡因子 = 2

失衡节点左孩子：平衡因子 = 1

向右旋转，冲突的右孩变左孩

RR型

失衡节点：平衡因子 = -2

失衡节点左孩子：平衡因子 = -1

向右旋转，冲突的左孩变右孩

LR型

失衡节点：平衡因子 = 2

失衡节点左孩子：平衡因子 = -1

左旋左孩子，然后右旋

RL型

失衡节点：平衡因子 = -2

失衡节点左孩子：平衡因子 = 1

右旋右孩子，然后左旋

平衡二叉树插入

插入节点后如果导致多个祖先节点失衡，只需调整距离插入节点最近的失衡节点，其它失衡点会自然平衡