目录
树
树的遍历方式
平衡二叉树
旋转机制
左旋
右旋
旋转实例
左左
左右
右右
右左
总结
红黑树
树
相关概念
节点的内部结构如下
二叉树与二叉查找树的定义如下
树的遍历方式
前序遍历：当前节点，左子节点，右子结点
中序遍历：左子节点，当前节点，右子结点
后序遍历：左子节点，右子结点，当前节点
序遍历：一层一层的遍历
平衡二叉树
定义：树的任意节点左右子树高度差不超过1。
旋转机制
平衡二叉树拥有左旋和右旋两种机制。当添加一个节点之后，若该树不再满足平衡二叉树的定义，则会触发旋转机制。
左旋
普通情况
复杂情况
右旋
普通情况 
复杂情况 
旋转实例
左左
左右
右右
右左
总结
① 左左：一次右旋
② 左右：先局部左旋，再整体右旋
③ 右右：一次左旋
④ 右左：先局部右旋，再整体左旋
红黑树
