数据结构树和二叉树的实际应用是什么？

全部展开

一个单位有10个部门，每个部门有一个电话，但是整个单位只有一个外线. 来电时，转接器将转接到内部线路. 众所周知，每个部门都使用外线，频率为（次/天）

5 20 10 12 8 4 3 5 6 9

请问如何设计内部电话号码数据结构 二叉树，以便操作员可以拨打最少的电话？

这是霍夫曼树的应用.

用于存储和处理树状数据（例如家谱）的数据结构.

应用非常广泛，因为根据数据结构的理论，任何复杂的树都可以转换为二进制并进行处理.

对于二叉树重新排序，搜索和数据索引，有许多应用程序.

二叉树排序是简单算法排序中最快的.

树的一大类是自平衡BST树，并且有很多变体: RB树是每个节点e68a84e8a2ad3231313335323631343130323136353331333365646262是红色或黑色，彩色世代遗传AVL树是每个节点都包含平衡因子相等Splay树的左上角到右上角是一个指针，每个节点都有一个父节点. Treap是每个节点的随机优先级数字，父优先级> =子优先级.

自平衡的二进制搜索树经常出现在访谈中，但是很少使用编写网页的Internet代码农夫. 如果将它们用作地图，则通常比直接使用哈希表要好. 如果将它们用于排序，则最好直接使用排序算法...但是也有一些有用的时间，例如查找数字的上下限.

树的另一大类是Trie，它具有字典顺序，用于存储字典的高空间压缩率以及前缀搜索的功能. 它可以用于常规匹配，数据压缩和索引构建. Trie还具有许多变体: Double Array-Trie的经典实现.

每个节点可以存储一串字符，但不限于一个字符. Judy Array基于256元基数树数据结构 二叉树，使用20种压缩方法，非常复杂. Burst Trie-如树足够小，请使用二进制堆存储.

但是，压缩效果通常是HAT Trie-压缩率高并且不容易出现CPU高速缓存未命中，搜索速度接近哈希表，并且内存消耗少得多. 该节点可以是以下三种类型之一: 数组哈希，序列化存储桶，传统Trie节点MARISA Trie-最高压缩率，支持mmap加载，也是使用多种压缩技术的复杂实现. 构建需要花费更多时间，并且无法动态更新.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-222714-1.html