红黑树

特性

1.实际上是平衡二叉树的变种。
2.对比AVL树，AVL树查询性能比红黑树高，因为AVL树高度平衡，而增删改红黑树性能高些。

成树规则

  1. 根节点是黑色节点
  2. 红色节点的子节点是黑色节点
  3. 从根节点到叶子节点任意路径的黑色节点数一致
  4. 节点是黑色或者红色的
  5. 叶子节点都是黑色的空节点

如何调整树平衡

  1. 变色
  2. 左右旋转

应用

HashMap，当链表长度大于8时，会将链表结构转换为红黑树结构。以提升查询效率。

其他

参考自

漫画：什么是红黑树