键盘敲烂,月薪过万作业不做,等于没学
当前系列: 数据结构和算法 修改讲义

当年飞哥准备软考,弄了一个视频,一开始就给我讲“树”,让我那个懵逼哟……不明觉厉!


树(tree)

不像?倒过来看!

关键的关键,是和树一样有分叉。


基本概念

节点(node)

  • 根(root):没有其他节点指向
  • 叶子(leaf):不指向任何其他节点
  • 枝(branch):其他节点

叉:二叉/三叉/n叉……。为了教学方便,一般都使用二叉树:一个节点最大只有两个“分叉”

关系:父/子/兄弟/祖先/后代

  • 祖先:包含父节点的节点,以及一直往上的所有父节点
  • 父:直接包含自己的节点
  • 自己:
  • 兄弟:父节点下除自己以外的其他节点
  • 子:自己的直接包含的节点
  • 后代:子节点包含的节点,以及一直往下的所有子节点

深度:从根到叶子的层级数

子树:一个树有可以被分为多个子树


和链表的关系

树可以认为是一种链表,他们都是通过“指针”进行组织

  • 链表:线性,没有分叉
  • 树:非线性,节点的指针会形成“岔路


现实映射

其实现实生活中,“树”无处不在,比如:企业/部队/政府/家族……,只要有分类、目录、层级关系存在的地方,就有“树”。

为什么需要树?@想一想@:为什么需要文件夹?

磁盘上有成千上万个文件,如何才能快速的找到其中某一个文件?(地址同理)

树的最大作用是便于查找


添加约束

排序二叉树

特点/定义:

  • 左子树上所有结点(的值)均小于它的根结点(的值)(若左子树不空);
  • 右子树上所有结点(的值)均大于它的根结点(的值)(若右子树不空);
  • 左、右子树也分别为二叉排序树;


@想一想@:为什么需要“排序”二叉树?便于查找。(演示)

平衡排序二叉树(AVL树)

在排序二叉树的基础上增加“平衡”:

任何一个子树,左右两边叶子节点的深度差距不大于1


为什么需要平衡?将算法时间复杂度始终控制在O(log(n))


对比二分查找

有些同学会瞬间联想到:这不就是二分查找么?为什么不直接顺序排列,然后用二分?

问题是:用什么装数据?尤其是当数据插入/更改/删除的时候:

  • 数组:大小固定,位置固定,重新排序是不是很麻烦?
  • 链表:如何快速定位到要插入的位置?

#体会#:数据结构是算法的基础,一定是先有数据结构,然后才有算法……


堆:完全二叉树


树的构建(选

这里的树,专指排序平衡二叉树。

如何实现?常规方法是:在排序二叉树的基础上进行平衡调整。

排序

第一个节点为根节点。

第二个节点和第一个节点比较:

  • 大于第一个节点,放右边
  • 小于第一个节点,放左边

第三个节点,以此类推

PPT演示……

平衡

每一次排序完成,检查是否平衡。如果没有,利用左旋转/右旋转 及其 组合进行调整。

  1. 一次旋转实现

  2. 两次旋转实现,即先做成1的样子(会有切断/连接的过程),再按1进行处理


更复杂树仍然使用这个套路,先调整不平衡子树,再依次往上调整直到根节点,总之:

  • 对树结构只有最小的影响,以提高性能
  • 使用固定套路,方便分支/循环的代码编写
PPT演示:……

延伸:一个可以动画显示树操作的网站


图和其他

如果把树搞得再“乱”一点,就可以形成

其实也有点像(互联)“网”:

  • 树是有层级结构的,图没有;
  • 树总是从根节点出发的,图不一定,大多数时候都没有根节点这个概念
  • 到达树的某一节点,路径是固定的;而图是不固定/单一的 —— 图的路径(最短最快)是研究的重点

图的应用以前还很神秘,现在烂大街了。@想一想@:百度/高德地图、滴滴打车,是不是都要用到图?

其他算法

我们所学的算法其实都是皮毛,^_^

有兴趣的同学可以继续学习:

  • 最短路径/电梯调度/背包……问题
  • 分支/动态规划/贪心……算法

但因为在实际的(企业级应用)开发中用不到,我们就不多讲了……

好吧,我承认,我也不会,ʅ(‾◡◝)ʃ

学习笔记
源栈学历
键盘敲烂,月薪过万作业不做,等于没学

作业

觉得很 ,不要忘记分享哟!

任何问题,都可以直接加 QQ群:273534701

在当前系列 数据结构和算法 中继续学习:

下一课: 已经是最后一课了……

多快好省!前端后端,线上线下,名师精讲

  • 先学习,后付费;
  • 不满意,不要钱。
  • 编程培训班,我就选源栈

更多了解 加:

QQ群:273534701

答疑解惑,远程debug……

B站 源栈-小九 的直播间

写代码要保持微笑 (๑•̀ㅂ•́)و✧

公众号:源栈一起帮

二维码