平衡二叉查找树的插入删除

https://www.cnblogs.com/duyy/p/3671176.html

总结:
插入时:
若是RR或者LL插入,则旋转后的根节点(替代失衡结点的结点)就是失衡结点的子节点。
若是RL或者LR插入,则旋转后的根节点(替代失衡结点的结点)就是失衡结点的孙结点(子节点的子节点)
LL
平衡二叉查找树的插入删除
RR
平衡二叉查找树的插入删除
LR
平衡二叉查找树的插入删除
RL
平衡二叉查找树的插入删除

删除时:
删除时,有可能会因为删除一个结点,造成不平衡,且不平衡的状态可能是LL,RR,LR,RL四种。
若不平衡状态只有一种,则按照插入时遇见这种不平衡状态的方式去处理。
但是,删除一个结点,可能会同时出现两种不同的不平衡状态,比如下图删除15结点后,遇到了RR和RL两种不平衡状态。
平衡二叉查找树的插入删除
这时按照RR的不平衡状态去处理。
总结:不平衡状态的优先级:(LL=RR) > (RL=LR)