二叉树

发表于

二叉树的使用场景

  • 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应该是有不同的数据结构）。