各类树的应用

各类树的应用
AVL树：最早的平衡二叉树之一，是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多。windows对进程地址空间的管理用到了AVL树。

红黑树:平衡二叉树，广泛用在C++的STL中。map和set都是用红黑树实现的。还有epoll在内核中的实现，用红黑树管理事件块
nginx中，用红黑树管理timer等
Java的TreeMap实现
著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块

B/B+树：用在文件系统、数据索引和数据库索引，如Mysql。

trie 树：的一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示，还有比如IP选路，也是前缀匹配，一定程度会用到trie。

哈夫曼树：哈夫曼编码