Red–black Tree - tenji/ks GitHub Wiki
红黑树
红黑树是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree），其中每个节点都有一个附加属性：颜色，可以是红色或黑色。这些树的主要目标是在插入和删除期间保持平衡，确保高效的数据检索和操作。
历史
...
红黑树的性质/原则
- 性质1（颜色属性）：节点非黑即红
- 性质2（根属性）：根节点一定是黑色
- 性质3（叶子属性）：叶子节点（NIL）一定是黑色
- 性质4（红色属性）：每个红色节点的两个子节点，都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质5（黑色属性）：从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。
红黑树 vs AVL 树
与红黑树相比，AVL 树更加平衡，但它们在插入和删除过程中可能会导致更多的旋转。红黑树并不追求“完全平衡”，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。因此，如果你的应用程序涉及频繁的插入和删除，那么红黑树应该是首选。如果插入和删除不太频繁，而搜索是更频繁的操作，那么 AVL 树应该优先于红黑树。
更多关于 AVL 树，传送门
基本操作
插入（Insertion）
搜索（Searching）
删除（Deletion）
旋转（Rotation）
再平衡（Rebalancing）
红黑树再平衡最多需要多少次旋转？
红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决。
时间复杂度
- 搜索（Search）：
O(logn) - 插入（Insert）：
O(logn) - 删除（Delete）：
O(logn)
Java 实现
...
红黑树的优点
红黑树的缺点
红黑树的应用
- JDK 1.8开始，HashMap 也引入了红黑树，当冲突的链表长度超过 8 时，自动转为红黑树；（关于 HashMap，传送门）
- 实现 Maps 和 Sets：Java 中，TreeMap、TreeSet 都使用红黑树作为底层数据结构，因为其中高效的搜索、插入和删除至关重要；
- Linux 底层的 Completely Fair Scheduler 进程调度算法中，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
- 多路复用技术的 Epoll 采用红黑树组织管理 sockfd，其核心结构是红黑树 + 双向链表；
- 文件系统：一些文件系统使用红黑树来管理文件和目录结构；
- 图形和游戏开发：红黑树可用于图形和游戏开发中，以完成碰撞检测和寻路等任务。