拥抱STL -树的导览
树,一种十分基础的数据结构。
本篇将重点讲一些树的基础知识,作为下一篇《走进STL - 红黑树》的支持。
1、树的导览
先看图啊,看不懂再看下面的文字描述
- 树由节点和边构成,每棵树有最上端一个根节点,每个节点可以有具方向性的边,用来和其他节点相连。
- 在相连节点中,在上者称为父节点,在下者称为子节点,无子节点者称为叶节点。
- 子节点可以存在多个。如果只允许两个子节点,则称为二叉树。
- 不同节点如果拥有相同父节点,则称为兄弟节点。
- 根节点至任何节点之间有唯一路径,路径所经过的边数,称为路径长度(length)。
- 根节点至任一节点的路径长度,称为该节点的深度(depth)。
- 某节点至其最深节点的路径长度,称为该节点的高度(height)。
- 整棵树的高度便以根节点的高度为准。
- 任何节点的大小(size)是指其所有子代(包括自己)的节点总数。
完全二叉树:走进STL - heap,小树芽
2、二叉搜索树
所谓二叉搜索树,可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是:任何节点的键值一定大于去其左子树中的每一个节点的键值,并小于其右子树的每一个节点的键值。
所以在二叉树中找到最大值和最小值是很简单的,比较麻烦的是元素的插入和移除。
插入新元素时,从根节点开始,遇键值较大者就向左,遇键值较小者就向右,一直到尾端,即为插入点。
移除旧元素时,如果它是叶节点,直接拿走就是了;如果它有一个节点,那就把那个节点补上去;如果它有两个节点,那就把它右节点的最小后代节点补上去。
3、平衡二叉搜索树
高低脚的二叉搜索树总归是效率不高的,所以我们就要认为的调整它的高低脚。
平衡的大致意思是:任何两个叶节点的深度差不过1吧。
那我们来看一下调整树的节点使平衡的操作吧:旋转
3.1 单旋转
看图写字,我就不做过多赘述了。
3.2 双旋转
这个图我就要说两句了,有的人可能乍一看会觉得这用上面的单旋转就好了,为什么根节点不是14而是16?为什么这个会要叫双旋转?转着好玩的吗?
其实不然,你可以试着把单旋转做法的图画出来,将会惊奇的发现,还是不平衡,这就很尴尬了。
正确的转法应该是这样的:
双旋转,说白了就是单旋转两次。
红黑树是一个被广泛应用的平衡二叉搜索树,也是SGI STL唯一实现的一种搜索树,作为关联式容器的底部机制所用。
本篇作为即将出炉的《走进STL - 红黑树》的导览,所以不放代码。
文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。
原文链接:lion-wu.blog.csdn.net/article/details/105512100
- 点赞
- 收藏
- 关注作者
评论(0)