本文共 538 字,大约阅读时间需要 1 分钟。
在程序的世界里,任何问题或技术的落脚点都是数据结构,所以在学习或研究这些问题或技术时,要注重理解底层或实现过程中所采用的数据结构。本系列会将常用的数据结构进行总结,首先看下树。
一、树
常用的树形数据结构有:搜索二叉树、平衡二叉树、红黑树、完全二叉树;
1.搜索二叉树:父子节点满足大小关系,左子树都小于根节点,根节点都小于右子树,根据这一特性能快速进行查找;典型应用有:全球域名解析服务器的部署、注册表等等;
2.平衡二叉树:搜索二叉树在极端情况下会变成一个链表,从而导致查找性能下降,为此引入了平衡二叉树,以确保左右子树的高度差;典型应用:很少使用,基本上都用红黑树来代替使用。
3.红黑树:平衡二叉树在调整树的平衡性时,需要全树调整,导致调整的代价太大,为此引入了红黑树,在红黑树的节点中加入了一个表示颜色的变量,能够在局部进行调整平衡性而无需整棵树一起调整;典型应用:epoll内部结构。
4.完全二叉树:自身有一些特定的函数关系等式,如父子节点满足根节点为i,则左节点为2*i+1,右节点为2*i+2=左节点+1;最后一个非叶子节点为n-2/2等等,像堆排序就是利用了这些数学关系等式。典型应用:堆排序。
5.B+树:有待进一步学习......。
参考:1.2.
转载地址:http://zbsvi.baihongyu.com/