红黑树

目录

• 平衡二叉树
• 什么是红黑树
• 红黑树特点
• 实现一棵红黑树

自平衡二叉查找树

• 定义，任意节点左右子树高度相差不大于1
• 价值，解决普通二叉查找树出现复杂度退化问题

实现方案

• 红黑树，近似平衡（最流行）
• AVL树，绝对平衡
• SplayTree(伸展树)
• Treap（树堆）

红黑树

红黑树特点

• 近似平衡树
• 高度比AVL树多1倍
• 性能很好

红黑树要求

• 每个节点或是黑色、或是红色；
• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点；
  叶子节点只能是数据位null 的节点
• 如果一个节点时红色，则它的子节点必须是黑色的；
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
  确保没有一条路径会比其他路径长出两倍，因此红黑树是近似平衡。

Java中应用

• TreeSet，TreeMap
• Jdk1.8+的HashMap桶内链表>8时转变为红黑树

实现一棵红黑树

红黑树，总是通过旋转和变色达到自平衡。

• 左旋，以某个节点作为支点，
  • 其右节点变为旋转节点的父节点
       - 其右节点的右节点变为旋转节点的右子节点
       - 其右节点的左子节点保持不变
• 右旋，以某个节点作为支点，
  • 其左节点变为旋转节点的父节点
       - 其左节点的右子节点变为旋转节点的左子节点
       - 其左节点的左子节点不变
• 变色，修改节点的颜色

查找

类似于二叉查找树

• 根节点开始，把根节点设置为当前节点；
• 若当前节点为空，返回null
• 若 等于当前节点，返回当前节点；
• 若 大于当前节点，把当前节点的右节点设置为当前节点；
• 若 小于当前节点，把当前节点的左节点设置为当前节点；

插入

主要分2步骤：

• 找到插入的位置
• 插入后进行自平衡

细节

• 插入的节点必须为红色
• 插入
  
• 着色
  

删除

分2步：

• 查找目标节点
• 删除节点后自平衡；

细节