盒子
盒子
文章目录
  1. 1.红黑树简介
  2. 2. 红黑树性质
  3. 3. 为什么这样的树是平衡的
  4. 4. Java8中HashMap链表使用红黑树而不是AVL树
  5. 5. 既然红黑树那么好,为啥hashmap不直接采用红黑树,而是当大于8个的时候才转换红黑树
  6. 6. 红黑树应用实例

浅谈红黑树

1.红黑树简介

红黑树是一种自平衡二叉搜索树,不能保证非常严格的平衡性,但是其平衡性仍然足以确保以O(logN)的时间复杂度进行插入、删除和检索操作。
它需要更少的内存,并且可以更快的进行再平衡,所以它常在树需要被频繁修改的情况下使用。

2. 红黑树性质

1)每个节点要么是红色节点,要么是黑色节点
2)根节点是黑色节点
3)叶节点是空节点,也称为黑色节点
4)每个红色节点必须有两个黑色子节点,也就是说,一个红色节点不可能有红色子节点(虽然黑色节点可以有黑色子节点)
5)每一条从某一节点至叶节点的路径必须包含相同数量的黑色子节点

3. 为什么这样的树是平衡的

根据性质5)假设从某节点(根节点)到叶节点有路径1与路径2,每条路径均有b个黑色节点,最坏情况下,

  • 红色节点最少数量为0,则路径1共有b个节点
  • 红色节点最大数量为b(性质4决定红色节点数不会超过一半), 路径2共有2b个节点
    即使在最极端的情况下,两条路径的长度相差也不会超过一倍,这足以确保在O(logN)的时间复杂度内完成查找和插入操作

4. Java8中HashMap链表使用红黑树而不是AVL树

在ConcurrentHashMap中是加了锁的,实际上是读写锁,如果写冲突就会等待,如果插入时间过长必然等待时间更长,而红黑树相对AVL树插入更快

5. 既然红黑树那么好,为啥hashmap不直接采用红黑树,而是当大于8个的时候才转换红黑树

因为红黑树需要左旋、右旋操作,而单链表不需要
以下都是单链表与红黑树结构对比
如果元素小于8个,查询成本高,新增成本低
如果元素大于8个,查询成本低,新增成本高

6. 红黑树应用实例

JAVA: java.util.TreeMap、java.utils.TreeSet
C++ STL: map、multimap、multiset
Linux内核: 完全公平的调度程序, linux/rbtree.h

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫