红黑树及 linux内核红黑树探讨

2023-11-06 10:56:52

红黑树相信大家有一定的了解，红黑树是一种应用很广泛的数据结构，详情点这里。

比如在linux内核，nginx等众多开源软件中有应用。

红黑树的关键点就是节点的插入删除。

插入节点的关键是:
    插入新节点总是红色节点
    如果插入节点的父节点是黑色, 能维持性质
    如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质

删除节点的关键是:
如果删除的是红色节点, 不破坏性质
如果删除的是黑色节点, 那么这个路径上就会少一个黑色节点, 破坏了性质. 故删除算法就是通过重新着色或旋转, 来维持性质

通过google可以发现有很多文章已经把红黑树分析的很好了，现在罗列一下，供以后学习。

红黑树

Linux 内核红黑树的实现代码位于：

lib/rbtree.c，同时头文件在include/linux/rbtree.h 中，内核中很多模块都使用了红黑树，详细介绍参见内核文档 Documentation/rbtree.txt。

等