AVL树,红黑树,B树,B+树,Trie树都分别应用在哪些现实场景中?

关注者
5957
被浏览
172559

24 个回答

AVL树: 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

红黑树: 平衡二叉树,广泛用在C++的STL中。如map和set都是用红黑树实现的。

B/B+树: 用在磁盘文件组织 数据索引和数据库索引。

Trie树(字典树): 用在统计和排序大量字符串,如自动机。

AVL是一种高度平衡的二叉树,所以通常的结果是,维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果场景中对插入删除不频繁,只是对查找特别有要求,AVL还是优于红黑的。

红黑树的应用就很多了,除了上面同学提到的STL,还有
  • 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
  • epoll在内核中的实现,用红黑树管理事件块
  • nginx中,用红黑树管理timer等
  • Java的TreeMap实现

B和B+主要用在文件系统以及数据库中做索引等,比如Mysql:B-Tree Index in MySql

trie 树的一个典型应用是前缀匹配,比如下面这个很常见的场景,在我们输入时,搜索引擎会给予提示



还有比如IP选路,也是前缀匹配,一定程度会用到trie