拥抱STL -树的导览

树,一种十分基础的数据结构。 本篇将重点讲一些树的基础知识,作为下一篇《走进STL - 红黑树》的支持。

1、树的导览

先看图啊,看不懂再看下面的文字描述

  1. 树由节点和边构成,每棵树有最上端一个根节点,每个节点可以有具方向性的边,用来和其他节点相连。
  2. 在相连节点中,在上者称为父节点,在下者称为子节点,无子节点者称为叶节点。
  3. 子节点可以存在多个。如果只允许两个子节点,则称为二叉树。
  4. 不同节点如果拥有相同父节点,则称为兄弟节点。
  5. 根节点至任何节点之间有唯一路径,路径所经过的边数,称为路径长度(length)。
  6. 根节点至任一节点的路径长度,称为该节点的深度(depth)。
  7. 某节点至其最深节点的路径长度,称为该节点的高度(height)。
  8. 整棵树的高度便以根节点的高度为准。
  9. 任何节点的大小(size)是指其所有子代(包括自己)的节点总数。

完全二叉树:走进STL - heap,小树芽

2、二叉搜索树

所谓二叉搜索树,可提供对数时间的元素插入和访问。二叉搜索树的节点放置规则是:任何节点的键值一定大于去其左子树中的每一个节点的键值,并小于其右子树的每一个节点的键值。

所以在二叉树中找到最大值和最小值是很简单的,比较麻烦的是元素的插入和移除。 插入新元素时,从根节点开始,遇键值较大者就向左,遇键值较小者就向右,一直到尾端,即为插入点。 移除旧元素时,如果它是叶节点,直接拿走就是了;如果它有一个节点,那就把那个节点补上去;如果它有两个节点,那就把它右节点的最小后代节点补上去。

3、平衡二叉搜索树

高低脚的二叉搜索树总归是效率不高的,所以我们就要认为的调整它的高低脚。

平衡的大致意思是:任何两个叶节点的深度差不过1吧。

那我们来看一下调整树的节点使平衡的操作吧:旋转

3.1 单旋转

看图写字,我就不做过多赘述了。

3.2 双旋转

这个图我就要说两句了,有的人可能乍一看会觉得这用上面的单旋转就好了,为什么根节点不是14而是16?为什么这个会要叫双旋转?转着好玩的吗?

其实不然,你可以试着把单旋转做法的图画出来,将会惊奇的发现,还是不平衡,这就很尴尬了。

正确的转法应该是这样的:

双旋转,说白了就是单旋转两次。

红黑树是一个被广泛应用的平衡二叉搜索树,也是SGI STL唯一实现的一种搜索树,作为关联式容器的底部机制所用。

本篇作为即将出炉的《走进STL - 红黑树》的导览,所以不放代码。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈多路查找树(B树)

    曾今我不知道多叉树有上面用,所以对于多叉树并没有过多的关注,或者说,基本没关注。 直到我了解到了多路查找树(B树),我知道,是我浅薄了。

    看、未来
  • 【LeetCode】每日一题(8.2)二叉树展开为链表

    具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点(其实就是找左子节点的最...

    看、未来
  • 种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

    树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述现实生活中的很多事物,例如家 谱、单位的组织架构、等等。 树是由n(n>=1)个有限...

    看、未来
  • Linux之HA高可用集群的基础概念总结

    HA(High Availability)高可用集群,其特点为根据实际需求为前端Diretor,后端RS-server,数据库服务器,共享存储等集群节点做一个...

    小小科
  • Zookeeper系列(5) —— Zookeeper 常用的客户端操作命令

    创建节点的命令格式 create [-s] [-e] /path data acl

    求和小熊猫
  • 第15期:索引设计(索引组织方式 B+ 树)

    谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。

    爱可生开源社区
  • 动图展示,让你彻底理解红黑树!

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    业余草
  • 数据结构:堆(Heap)

    堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

    sunsky
  • 动图演示:如何彻底理解红黑树?

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    架构师修炼
  • 使用图进行特征提取:最有用的图特征机器学习模型介绍

    从图中提取特征与从正常数据中提取特征完全不同。图中的每个节点都是相互连接的,这是我们不能忽视的重要信息。幸运的是,许多适合于图的特征提取方法已经创建,这些技术...

    deephub

扫码关注云+社区

领取腾讯云代金券