在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文件系统，通过红黑树组织目录项。

find test.0.0/* 这种是很好理解的，先根据通配符匹配（默认匹配顺序是按字母顺序），然后再find。比如*匹配到test.0.0/dict.list 然后再find test.0.0/dict.list 所以是按字母排序的。

find test.0.0/ 这种则涉及到linux中文件名在超级块中的存储方式（spuer_block）：为了快速找到一个文件，我们通常会使用hash算法，和B树算法(二叉树算法)在超级块存储文件名（与inode对应），find就是根据B树遍历查找的。

具判断楼主机子应该是左遍历挂文件名，右遍历查找文件名。附上一张图帮助理解，数字代表遍历的先后1->2->3->4.（关键字：二叉树遍历）

这只是鄙人的浅见。