数据结构--树(笔记)
文章目录
- 1. 含义及术语
- 2. 应用
- 3. 常见二叉树种类
- ① 二叉树(Binary tree)
- 一般树和二叉树的区别
- ② 完美二叉树(Perfect Binary tree)
- ③ 完全二叉树(Complete Binary tree)
- ④ 满二叉树(Full Binary tree)
- 完美二叉树、完全二叉树和满二叉树
- ⑤ 平衡二叉树(Balanced Binary tree)
- 二叉树与二叉搜索树
- 平衡树
- 平衡二叉搜索树
- AVL树
- 4. 二叉搜索树CRUD时间复杂度O(logn)
- 5. 其它常见树
- 6. 面试
- 7. 内容出处
1. 含义及术语
① 树：类似于一个家谱(或者说一颗大树)。 树结构用来表示一种层级关系
② Root ：根节点。可以理解为一个大家族的祖先
③ Edge：可以理解为连接前后辈的纽带(今后看到边就可以知道它下面一定有子节点)
④ Key：可以理解为家庭成员的姓名
⑤ Siblings：兄弟节点
⑥ Subtree：子树。可以理解为后辈又组建了自己的小家庭
⑦ Leaf nodes：叶节点。这个大家族到今天为止最新的一代人(G、H、I、J）
⑧ 树的深度(这个家族目前有几代人)：由上往下(从A往下数)
⑨ 数的高度(这个家族目前有几代人)：由下往上(从J这一辈往上数)
⑩ 如何衡量树的深度和高度？ 数边数、数行数(或者说level–等级)
2. 应用
① 公司职位等级表
(图片来源：百度)
② Windows文件系统中的文件路径设计(怎么设计其实是软件工程的问题0
在此电脑里查询某个应用时也是一个文件夹一个文件夹往下查
③ Linux文件系统中的文件路径设计
/ – 根目录
其他目录 – 子目录
/home/aria/Documents – 一个文件路径
注：
1> 文件系统为什么使用树状结构？
因为它可以对文件和目录进行有效的组织和管理，还可以定位或者说访问特定的文件目录(只需提供文件路径)
2> vscode：终端输入tree命令可以查看当前文件夹的树结构
④ 计算机语言设计学(以HTML为例)：head可以看作祖先
⑤ 搜索引擎(BING、百度等)中存储网页的结构信息
⑥ IDE(像vscode等大型编译器)中的语法分析：表述语法树
⑦ 决策树：表述决策过程
⑧ 画图等软件的菜单栏
3. 常见二叉树种类
在不同领域、不同范围内不同研究方向内会有不同的树，这里只列举一些常见的树。
① 二叉树(Binary tree)
特点：每一个父节点最多拥有2个子节点。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
(图片来源：wiki)
注：
三叉树：每一个父节点最多拥有3个子节点。
k叉树(英文写法：k - ary tree)：每一个父节点最多拥有k个子节点。
一般树和二叉树的区别
【数据结构】树与二叉树的区别
(图片来源：wiki)
② 完美二叉树(Perfect Binary tree)
特点：每个父节点都有2个子节点且最年轻的那代人都是同一个辈分或者说同一个等级的
(图片来源：百度)
③ 完全二叉树(Complete Binary tree)
特点：跟完美二叉树很类似(almost perfect， 近乎完美)，区别在于它最新一代不一定是同一辈(例如：此时最新一代的5就和上一代的5、6、7产生了一个深度差)且最后一代人必须靠左对齐。
(图片来源：wiki)
反例(不是完全二叉树)：
④ 满二叉树(Full Binary tree)
特点：有0个子节点或者2个子节点
完美二叉树、完全二叉树和满二叉树
完美二叉树, 完全二叉树和完满二叉树
⑤ 平衡二叉树(Balanced Binary tree)
特点：每个节点的左右子树深度差(或者说)高度差都不超过1的二叉树。
下述所有截图均来自wiki百科
二叉树与二叉搜索树
平衡树
特点：每个节点的左右子树深度差(或者说)高度差都不超过1
上述第一个不是平衡树的原因在于：9、76、54这些节点左右子树的高度差大于1
平衡二叉搜索树
AVL树
此动画演示了不断将节点插入AVL树时的情况，并且演示了左旋（Left Rotation）、右旋（Right Rotation）、右左旋转（Right-Left Rotation）、左右旋转（Left-Right Rotation）以及带子树的右旋（Right Rotation with children）。
4. 二叉搜索树CRUD时间复杂度O(logn)
问：如何更直观的得出O(logn)的结论？
答： 数学运算：更直观一点
如何直观的理解 O(logn) 时间复杂度的神奇之处
注：
①树的时间复杂度有的跟节点数有关，有的跟边数有关。通常情况下都跟节点数有关。
② 堆也是O(logn)。堆有最大堆和最小堆之分
5. 其它常见树
① 线段树( 二叉搜索树)：区间查询 O(logn)
② 字典树 (Trie树)： O(M) m是键的长度
③ 图(邻接表、邻接矩阵)：单源最短路径算法 O(nm)或者O(n*n)
④ 红黑树(图片来源：wiki)
6. 面试
一般就是问我们对于某个树的理解(时间复杂度如何分析、常见应用等方面)，通常情况下二叉树、平衡二叉树比较常见，红黑树也有可能。就算让让分析指定的树且比较复杂，面试官也一定会先介绍一下这种树，然后再问我们如何理解。
算法岗位另说。算法岗位需要对树这个数据结构有很多的了解，因此面试时可能还会让列举一些其它的树，再让谈一下对它们的理解。
7. 内容出处
数据结构