LynDocs

外观

树结构 ​

认识树结构 ​

树的特点

  • 树通常有一个根。连接着根的是树干
  • 树干到上面之后会进行分叉成树枝，树枝还会分又成更小的树枝
  • 在树枝的最后是叶子

树的抽象

  • 树可以模拟生活中的很多场景，比如：公司组织架构、家谱、DOM Tree、电脑文件夹架构

优秀的哈希函数（补充）

  • 快速计算：霍纳法则
  • 均匀分布：质数（长度、幂的底）

树结构优点 ​

数据结构对比

数组

  • 优点
    • 数组的主要优点是根据 下标值访问 效率会很高
    • 但是如果我们希望根据元素来查找对应的位置呢？
    • 比较好的方式先对数组进行排序，再进行二分查找
  • 缺点
    • 需要 先对数组进行排序，生成有序数组，才能提高查找效率
    • 另外数组和插入和删除数据时，需要有大量的位移操作（插入到首位或者中间位置的时候）效率很低

链表

  • 优点
    • 链表的插入和删除操作效率都很高
  • 缺点
    • 查找效率很低，需要从头开始依次访问链表中的每个数据项，直到找到
    • 而且即使插入和删除操作操作效率很高，但是如果要插入和删除中间位置的数据，还是需要从头先找到对应的数据

哈希表

  • 优点
    • 哈希表的插入、查询、删除效率都是非常高的
  • 缺点
    • 空间利用率不高，底层使用的数组，并且某些单元是没有被利用的
    • 哈希表中的元素是无序的，不能安装固定的顺序来遍历哈希表中的元素
    • 不能快速的找出哈希表中的 最大值或最小值 这些特殊的值

树

  • 不能说树结构比其他结构都要好，因为 每种数据结构都有自己的特定的应用场景
  • 但是树确实综合了上面的数据结构的优点，并且弥补了上面数据结构的缺点

而且模拟某些场景，我们使用树结构会更加方便

  • 因为数结构的非线性，可以表示一对多的关系
  • 比如：文件的目录结构

树结构术语 ​

不过大部分术语都与真实世界的树相关，或者和家庭关系相关(如父节点和子节点)

树（Tree）：n（n>=0）个节点构成的有限集合

  • 当 n=0 时，称为空树

对于任一颗非空树（n>0），它具备以下性质：

  • 树中有一个称为 "根（Root）" 的特殊节点，用 r 表示
  • 其余节点可分为 m（m>0）个互不相交的有限集 T1、T2...Tm，其中每个集合本身又是一棵树，称为原来数的 "子树（SubTree）"

image-20230831092517176

  1. 节点的度（Degree）：节点的子树个数
  2. 树的度（Degree）：树的所有节点的最大度数
  3. 叶节点（Leaf）：度为 0 的节点（也称为叶子节点）
  4. 父节点（Parent）：有子树节点时其子树的根节点的父节点
  5. 子节点（Child）：若 A 节点是 B 节点的父节点，则称 B 节点是 A 节点的子节点，子节点也称孩子节点
  6. 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点
  7. 路径和路径长度：从节点 n1 到 nk 的路径为一个节点序列 n1、n2...nk
    • ni 是 n(i+1) 的父节点
    • 路径所包含边的个数为路径的长度
  8. 节点的层次（Level）：规定节点在 1 层，其它任一节点的层数是其父节点的层数+1
  9. 树的深度（Depth）：树中所有节点中的最大层次是这棵树的深度

树结构表示方法 ​

image-20230831094324866

image-20230831094358332

所有的数本质上都可以使用二叉树模拟出来

image-20230831095339522

认识二叉树 ​

二叉树分类 ​

如果树中每个节点 最多只能有两个子节点，这样的数就称为 "二叉树"

  • 二叉树可以为空，也就是没有节点
  • 若不为空，则它是由根节点和称为其 左子树TL 和 右子树TR 的两个不相交的二叉树组成

image-20230831095734913

二叉树有几个比较重要的特性，笔试题中比较常见：

  • 一颗二叉树第 i 层的最大节点树为：2^(i-1), i>=1
  • 深度为 k 的二叉树有最大节点总数为：2^k-1, k>=1
  • 对任何非空二叉树 T，若 n0 表示叶子点的个数，n2 是度为 2 的非叶节点个数，那么两者满足关系 n0=n2+1

完美二叉树（Perfect Binary Tree），也称满二叉树（Full Binary Tree）

  • 在二叉树中，除了下一层的叶节点外，每层节点都有 2 个子节点，就构成了满二叉树

image-20230831101407988

完全二叉树（Complete Binary Tree）

  • 除二叉树最后一层外，其它各层的节点个数都达到最大个数
  • 最后一层从左到右的叶节点连续存在，只缺右侧若干节点
  • 完美二叉树是特殊的完全二叉树

image-20230831101851096

二叉树存储方式 ​

二叉树的存储常见的方式是数组和链表

image-20230831102047188

二叉树最常见的方式还是使用链表存储

  • 每个节点封装成一个 Node，Node 中包含存储的数据，左节点的引用，右节点的引用

image-20230831102315370

二叉搜索树 ​

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

二叉搜索树是一颗二叉树，可以为空，如果不为空，满足以下性质：

  • 非空左子树的所有键值小于根节点的键值
  • 非空右子树的所有键值大于其根节点的键值
  • 左、右子树本身也都是二叉搜索树

image-20230831144423346

这种方式就是二分查找的思想：

  • 查找所需的最大次数等于二叉搜索树的深度
  • 插入节点，也利用类似的方法，一层层比较大小，找到新节点合适的位置

认识平衡树 ​

二叉搜索树缺陷 ​

二叉搜索树作为数据存储的结构有重要的优势

  • 可以快速地找到给定关键字的数据项，并且可以快速地插入和删除数据项

但是，二叉搜索树有一个很麻烦的问题：

  • 如果插入的数据是有序的数据，比如下面的情况
  • 有一颗初始化为 9、8、12 的二叉树
  • 插入下面的数据：7、6、5、4、3

非平衡树

  • 比较好的二叉搜索树数据应该是 左右分布均匀 的
  • 但是插入 连续数据 后，分布的不均匀，称这种树为非平衡树
  • 对于一颗平衡二叉树来说，插入/查找等操作的效率是 O(logN)
  • 对于一颗非平衡二叉树，相当于编写了一个链表，查找效率变成了 O(N)

image-20230904171135081

考虑平衡性 ​

为了能以较快的时间 O(log N)来操作一棵树，我们需要保证树总是平衡的

  • 至少大部分是平衡的，那么时间复杂度也是接近 O(logN) 的
  • 也就是说树中 每个节点左边的子孙节点的个数，应该尽可能的等于 右边的子孙节点的个数

AVL 树

  • AVL 树是最早的一种平衡树，它有些办法保证树的平衡（每个节点存储了一个额外的数据）
  • 因为 AVL 树是平衡的，所以时间复杂度也是 O(logN)
  • 但是，每次插入/删除操作相对于红黑树效率都不高，所以整体效率不如红黑树

红黑树

  • 红黑树也通过一些特性来保持树的平衡
  • 因为是平衡树，所以时间复杂度也是 O(logN)
  • 另外插入/删除等操作，红黑树的性能要优于 AVL 树，所以现在平衡树的应用基本都是红黑树

常备不懈，才能有备无患