数据结构中树结构算是比较难,性能也相对比较好的结构了,一个平衡的树结构,通常在查找,修改和删除处理上都有着极好的效率! 以链表为例,插入数据很简单,就是将最后节点的next指向新节点,时间算法为O(1)常数级,但是查找的时候需要挨个遍历比较,通常为O(N)级别! 而一颗平衡树,查找和插入都是O(log2N)级,O(N)和O(lon2N)在数据量十分巨大的时候有着天壤之别的效率差异,比如N为65536(2的16次方)的时候,链表查找平均查找是3万多次,而平衡树只需要16次,效率相差很大! 树结构通常包括:二叉树,二叉查找树,红黑树,2-3树,带B的树(B,B-,B+,B*),字典树等。 回到题目中来,数据结构中的树结构有哪些实际用例呢? ①,红黑树:JAVA8中的hashMap满足一定的阈值,自动扩容时会变为红黑树,treeMap,linux中的epoll模型,nginx中的Timer管理等。 ②,B,B+树:广泛用于数据库(mysql,oracle等)的索引。 ③,字典树:用于海量文本词频统计,查询效率比哈希表还高。 ④,生活中的树状结构有公司职级关系,国家省市区级联,族谱等等都有树结构形式! 可以说,树形结构是学习数据结构的路上不可或缺的一环,掌握树形结构的原理,设计能对我们的高性能设计理念有着举足轻重的作用,还有更多的技术分享,敬请关注。。。 |
|
来自: 昵称11935121 > 《未命名》