二叉树实际应用场景有哪些?
来源:千锋教育
发布人:xqq
2023-10-21
推荐
在线提问>>
一、二叉树实际应用场景
1、哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为优异二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性，详见《信息论与编码》。
2、海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处， 在处理大批量的动态的数据是比较有用。
3、C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。
4、B-Tree，B+-Tree在文件系统中的目录应用。
5、路由器中的路由搜索引擎。
延伸阅读：
二、什么是哈希值（hash code）
哈希值是一个int类型的整数。每个元素都应该有自己的哈希值，并且这个值是少数的。即满足：
A.如果元素a与元素b相等，则元素a的哈希值与元素b的哈希值相等。
B.如果元素a与元素b不相等，则元素a的哈希值与元素b的哈希值不相等。
通常情况下，对于int,bool,double,string等语言自带的类型都有自己的哈希值，可以用它们的哈希函数来获取，不同语言的哈希函数可能会不同。
如果是用户自己新建的类型，则需要提供计算此类型元素哈希值的哈希函数。
在哈希表中，我们是通过某元素的哈希值来查找、添加或删除元素的。
下一篇数据结构是什么?
