基数树
正如你所知道的,Linux内核提供了许多不同的库和函数,它们实现了不同的数据结构和算法。在这部分,我们将研究其中一种数据结构—— 基数树 。在 Linux 内核中,有两个文件与基数树的实现和API相关:
让我们先说说什么是 基数树
吧。基数树是一种 压缩的字典树 ,而字典树是实现了关联数组接口并允许以 键值对
方式存储值的一种数据结构。这里的键通常是字符串,但可以使用任意数据类型。字典树因为它的节点而与 n叉树
不同。字典树的节点不存储键,而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子:
+--++
| |
| |
+--v--+ +-v+ +--+
| | | |
| o | | a |
| | | |
+--+
|
|
+--+
| |
| t |
| |
+
via: <https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md>
作者:[0xAX] 译者:[cposture](https://github.com/cposture) 校对:[Mr小眼儿](https://github.com/tinyeyeser)
本文由 [LCTT](https://github.com/LCTT/TranslateProject) 原创翻译,[Linux中国](http://linux.cn/) 荣誉推出
发表回复