平衡二叉树以及其拓展 Note

二叉平衡树

http://c.biancheng.net/view/3432.html

https://blog.csdn.net/u014454538/article/details/120103527

平衡二叉树，又称为AVL树，遵循：

• 每棵子树的左子树和右子树深度差不能超过1；
• 二叉树每棵子树都要求是平衡二叉树。

平衡因子

表示左子树深度和右子树深度的差，取值可能为0、1和-1；

情况

LL、RR、LR、RL

右旋

• 将根节点绕左儿子顺时针下压
• 条件： LL：新插入节点在根节点的左儿子的左子树上；

左旋

• 将根节点绕右儿子逆时针下压
• 条件：RR： 新插入节点在根节点的右儿子的右子树上；

LR

• 条件： LR：新插入节点在根节点的左儿子的右子树上；
• 操作：
  • 以左儿子为根节点左旋，再将原根节点右旋；

RL

• 条件： RL：新插入结点在根节点的右儿子的左子树上；
• 操作
  • 以右儿子为根节点右旋，再将原根节点左旋；

红黑树