type
status
date
slug
summary
tags
category
icon
password

1. 树

1.1 树定义

树由节点及连接点的边构成, 树有下列属性
  • 有一个根节点(没有父节点的节点)
  • 除根节点外，其他每个节点都与其唯一的父节点相连
  • 从根节点到其他每个节点都有且仅有一条路径
  • 如果每个节点最多有两个子节点，我们就称这样的树为二叉树
notion image

1.2 种类

  • 无序树： 树中任意节点的子节点之间没有顺序关系，这种树为无序树也称自由树。
  • 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树
    • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树
    • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树
    • 第一阶段，整合数据，建立数仓，解决数据孤岛，
    • 第二阶段，画像，给人打标签
    • 第三阶段，智能推荐-Ai

2. 二叉树

2.1 概念

二叉树 （binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。
每个节点都有两个引用（指针），分别指向「左子节点 left‑child node」和「右子节点 right‑child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。
notion image

2.2 二叉树相关术语

二叉树的常用术语有：
  • 「根节点 root node」：位于二叉树顶层的节点，没有父节点。
  • 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向 None 。
  • 「边 edge」：连接两个节点的线段，即节点引用（指针）
  • 节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。
  • 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
  • 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量
  • 节点的「深度 depth」：从根节点到该节点所经过的边的数量
  • 节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量。
notion image
请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“通过的节点的数量”。在这种情况下，高度和深度都需要加1

2.3 二叉树及相关方法实现

2.3.1 相关方法

  • BinaryTree() 创建一个二叉树实例。
  • get_left_child() 返回当前节点的左子节点所对应的二叉树。
  • get_right_child() 返回当前节点的右子节点所对应的二叉树。
  • set_node_value(val) 在当前节点中存储参数 val 中的对象
  • get_node_value() 返回当前节点存储的对象
  • insert_left(val) 新建一棵二叉树，并将其作为当前节点的左子节点。
  • insert_right(val) 新建一棵二叉树，并将其作为当前节点的右子节点

2.3.2 数组实现（了解）

在列表之列表的树中， 我们将根节点的值作为列表的第一个元素；第二个元素是代表左子树的列表；第三个元素是代表右子树的列表。
notion image

2.3.3 链表实现

  • 插入左（右）节点：
    • 如果当前左节点为空， 表示当前节点无左节点直接插入即可
    • 如果当前左节点不为空， 表示当前节点有左节点，需要将新节点的左节点指向之前那个节点

2.4 常见二叉树类型

2.4.1 完美二叉树 perfect binary tree

完美二叉树（又叫满二叉树）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树的高度为 ℎ ，则节点总数为 2ℎ+1 - 1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
notion image

2.4.2 完全二叉树 complete binary tree

完全二叉树只有最底层的节点未被填满，且最底层节点尽量靠左填充。
notion image

2.4.3 完满二叉树 full binary tree

完满二叉树出了叶子节点之外，其余所有节点都有两个子节点
notion image

2.4.4 平衡二叉树 balanced binary tree

平衡二叉树中任意节点的左子树和右子树的高度之差的绝对值不超过1.
notion image

2. 二叉树遍历

二叉树的遍历分深度优先遍历（DFS）和广度优先遍历（BFS）。

2.1 深度优先遍历

深度优先遍历又分为先序遍历，中序遍历，后序遍历，它体现了一种“先走到尽头，再回溯继续”的遍历方式。
  • 前序遍历(根 左 右)：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
  • 中序遍历(左 根 右)：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
  • 后序遍历(左 右 根)：先递归地后序遍历右子树，然后递归地后序遍历左子树，最后访问根节点。
notion image

2.1.1 代码实现

深度优先遍历通常是基于递归来实现的。

2.1.2 复杂度分析

  • 时间复杂度：O(n)，所有节点被访问一次，使用O(n)时间，其中n为节点个数
  • 空间复杂度：O(n)，在最差情况下，即树退化为链表时，递归深度达到n，系统占用O(n)栈帧空间

2.2 广度优先遍历

广度优先遍历从顶部到底部逐层遍历二叉树，并在每一层按照从左到右顺序遍历，它体现了一种“一圈一圈向外拓展”的逐层遍历方式。
notion image

2.2.1 代码实现

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：

2.2.2 复杂度分析

  • 时间复杂度：O(n)，所有节点被访问一次，使用O(n)时间，其中n为节点个数
  • 空间复杂度：O(n)，在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在(n+1)/2个节点，占用O(n)空间
 

3. 二叉搜索树 binary search tree

我们已经学习了两种行集合中获取键-值对的方法。回想一下，我们讨论过映射抽象数据类型的两种实现，它们分别是列表二分搜索和哈希表。本节讨论的二叉搜索树是映射的另一种实现类型。我们感兴趣的不是元素在树中的确切位置，而是如何利用二叉树结构提供高效搜索。

3.1 概念

二叉搜索树满足以下条件：
  1. 对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值
  1. 任意节点的左右子树也是二叉搜索树，即满足上面1条件
  1. 不存在重复的节点值
notion image

3.2 相关操作及实现

  • insert() 插入元素
  • delete() 删除元素
  • lookup() 查找元素
  • minValueNode() 查找最小元素值
  • printTree() 中序打印元素（升序遍历）

3.3 二叉搜索树的效率

给定一组数，我们考虑使用数组或二叉搜索树存储，二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能。只有在高频添加、低频查找删除数据的场景，数组比二叉搜索树的效率更高。
ㅤ
无序数组
二叉搜索树
查找元素
O(n)
O(logn)
插入元素
O(1)
O(logn)
删除元素
O(n)
O(logn)

3.4 二叉搜索树的常见应用

  • 用作系统中的多级索引，失效高效的查找，插入、删除操作。
  • 作为某些搜索算法的底层数据结构
  • 用于存储数据流，以保持其有序状态
 
上一篇
第五章 哈希表（空）
下一篇
第七章 图算法（空）