在linux *** 作系统内核实现里经常使用的红黑树

在linux *** 作系统内核实现里经常使用的红黑树如下：

二叉树，按中序遍历后为一递增数组，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n)。

赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:

Every node is either red or black.

All NIL nodes (figure 1) are considered black.

A red node does not have a red child.

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋 *** 作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

红黑树属于“黑平衡”的二叉树，虽然牺牲了一定的平衡性，但是add、remove *** 作要由优于AVL树也就是说RB-Tree的“统计性能”更佳！Java中TreeSet，TreeMap的底层都是基于RedBlackTree红黑树的；

B+树主要用在文件系统以及数据库做索引。比如磁盘存储、文件系统、MySQL数据库

---