二叉树

普通二叉树 & 二分查找树

• 二叉查找树， 子左节点比根节点要小， 右子节点比根节点要大

平衡二叉树

• 二叉树左右两个字树的高度差不超过1
• 任意节点的左右两个子树都是一颗平衡二叉树
• 查找值的性能会更好

平衡二叉树-旋转

触发时机

• 当添加一个节点之后， 该树不在是一棵平衡二叉树

左旋

• 右节点的树比左节点的树要多， 则时则往左移
• 就是将根节点的右侧向左拉， 原先的右子节点变成新的父节点，并把多余的左子节点让出，给寂静降级的根节点当右子节点

case1 原：

左移后：

case2 原:

左移后

右旋

• 左树比右树要多， 则时则往右移
• 将根节点的侧向右拉， 原先的左子节点变成新的父节点，并把多余的右子节点让出，给已经降级的根节点当左子节点

红黑树

红黑树是一种自平衡的二叉查找树，

• 平衡二叉B
• 每一个节点可以是红或者黑
• 红黑树不是高度平衡的，它的平衡是通过“自己的红黑规则“进行实现的
• 根节点必须是黑色的
• 如果一个节点没有子节点或者父节点，该节点相应的指针属性为nil这些nil 视为叶节点，每个叶节点(Nil)是黑色的
• 如果某一个节点是红色的， 那么它的子节点必须是黑色的（不能存在两个红色节点的相连的情况）
• 每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

添加节点总结