TreeSet与TreeMap的底层实现都是红黑树
1 概念
什么是红黑树？
红黑树（Red Black Tree）是一颗自平衡（self-balancing）的二叉排序树（BST），树上的每一个结点都遵循下面的规则（特别提醒，这里的自平衡和平衡二叉树AVL的高度平衡有别）：
每一个结点都有一个颜色，要么为红色，要么为黑色；
树的根结点为黑色；
树中不存在两个相邻的红色结点（即红色结点的父结点和孩子结点均不能是红色）；
从任意一个结点（包括根结点）到其任何后代 NULL 结点（默认是黑色的）的每条路径都具有相同数量的黑色结点。
2 为什么要有红黑树？
大多数二叉排序树BST的操作（查找、最大值、最小值、插入、删除等等）都是o(h)的时间复杂度，h 为树的高度。但是对于斜树而言（BST极端情况下出现），BST的这些操作的时间复杂度将达到o(n) 。为了保证BST的所有操作的时间复杂度的上限为o(logn) ，就要想办法把一颗BST树的高度一直维持在logn，而红黑树就做到了这一点，红黑树的高度始终都维持在logn，n 为树中的顶点数目。
但是AVL树的高度也始终是logn,为什么还要有红黑树呢。
3 AVL树与红黑树的比较
AVL 树比红黑树更加平衡，但AVL树在插入和删除的时候也会存在大量的旋转操作。所以当你的应用涉及到频繁的插入和删除操作，切记放弃AVL树，选择性能更好的红黑树；当然，如果你的应用中涉及的插入和删除操作并不频繁，而是查找操作相对更频繁，那么就优先选择 AVL 树进行实现
4 红黑树有什么应用呢？
大多数自平衡BST(self-balancing BST) 库函数都是用红黑树实现的，比如C++中的map 和 set （或者 Java 中的 TreeSet 和 TreeMap）。
红黑树也用于实现 Linux 操作系统的 CPU 调度。完全公平调度（Completely Fair Scheduler）使用的就是红黑树。
网友评论