二叉树的使用场景
AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树
红黑树:平衡二叉树,广泛用在C++的STL中。map和set都是用红黑树实现的。我们熟悉的STL的map容器底层是RBtree,当然指的不是unordered_map,后者是hash。
B/B+树用在磁盘文件组织 数据索引和数据库索引
Trie树 字典树,用在统计和排序大量字符串epoll在内核中的实现,用红黑树管理事件块
nginx中,用红黑树管理timer等
Java的TreeMap实现
著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
B和B+主要用在文件系统以及数据库中做索引等,比如Mysql:B-Tree Index in MySql
trie 树的一个典型应用是前缀匹配,比如下面这个很常见的场景,在我们输入时,搜索引擎会给予提示
还有比如IP选路,也是前缀匹配,一定程度会用到trie跳表:Redis中就使用跳表,而不是红黑树来存储管理其中的元素(应该说的是一级元素-直接的Key,里面的value应该是有不同的数据结构)。