Zxy's Blog

小结 重点回顾 二叉树是一种非线性数据结构，体现“一分为二”的分治逻辑。每个二叉树节点包含一个值以及两个指针，分别指向其左子节点和右子节点。 对于二叉树中的某个节点，其左（右）子节点及其以下形成的树被称为该节点的左（右）子树。 二叉树的相关术语包括根节点、叶节点、层、度、边、高度和深度等。 二叉树的初始化、节点插入和节点删除操作与链表操作方法类似。 常见的二叉树类型有完美二叉树、完全二叉树、完满二叉树和平衡二叉树。完美二叉树是最理想的状态，而链表是退化后的最差状态。 二叉树可以用数组表示，方法是将节点值和空位按层序遍历顺序排列，并根据父节点与子节点之间的索引映射关系来实现指针。 二叉树的层序遍历是一种广度优先搜索方法，它体现了“一圈一圈向外扩展”的逐层遍历方式，通常通过队列来实现。 前序、中序、后序遍历皆属于深度优先搜索，它们体现了“先走到尽头，再回溯继续”的遍历方式，通常使用递归来实现。 二叉搜索树是一种高效的元素查找数据结构，其查找、插入和删除操作的时间复杂度均为 O(log⁡n)O(\log n)O(logn) 。当二叉搜索树退化为链表时，各项时间复杂度会劣化至...

AVL 树 * 在“二叉搜索树”章节中我们提到，在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从 O(log⁡n)O(\log n)O(logn) 劣化为 O(n)O(n)O(n) 。 如下图所示，经过两次删除节点操作，这棵二叉搜索树便会退化为链表。 再例如，在下图所示的完美二叉树中插入两个节点后，树将严重向左倾斜，查找操作的时间复杂度也随之劣化。 1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出了 AVL 树。论文中详细描述了一系列操作，确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在 O(log⁡n)O(\log n)O(logn) 级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值。 AVL 树常见术语 AVL...

二叉搜索树 如下图所示，二叉搜索树（binary search tree）满足以下条件。 对于根节点，左子树中所有节点的值 <<< 根节点的值 <<< 右子树中所有节点的值。 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。 二叉搜索树的操作 我们将二叉搜索树封装为一个类 BinarySearchTree ，并声明一个成员变量 root ，指向树的根节点。 查找节点 给定目标节点值 num ，可以根据二叉搜索树的性质来查找。如下图所示，我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。 若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。 若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。 若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点。 二叉搜索树查找节点示例 tab 1tab 2tab...

二叉树数组表示 在链表表示下，二叉树的存储单元为节点 TreeNode ，节点之间通过指针相连接。上一节介绍了链表表示下的二叉树的各项基本操作。 那么，我们能否用数组来表示二叉树呢？答案是肯定的。 表示完美二叉树 先分析一个简单案例。给定一棵完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。 根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的“映射公式”：若某节点的索引为 iii ，则该节点的左子节点索引为 2i+12i + 12i+1 ，右子节点索引为 2i+22i + 22i+2 。下图展示了各个节点索引之间的映射关系。 映射公式的角色相当于链表中的节点引用（指针）。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点。 表示任意二叉树 完美二叉树是一个特例，在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ，因此我们无法仅凭该序列来推测 None...

二叉树遍历 从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。 二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。 层序遍历 如下图所示，层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。 层序遍历本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（breadth-first search, BFS），它体现了一种“一圈一圈向外扩展”的逐层遍历方式。 代码实现 广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下： 123456789101112131415def level_order(root: TreeNode | None) -> list[int]: ...

二叉树 二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。 123456class TreeNode: """二叉树节点类""" def __init__(self, val: int): self.val: int = val # 节点值 self.left: TreeNode | None = None # 左子节点引用 self.right: TreeNode | None = None # 右子节点引用 每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent...

小结 重点回顾 输入 key ，哈希表能够在 O(1)O(1)O(1) 时间内查询到 value ，效率非常高。 常见的哈希表操作包括查询、添加键值对、删除键值对和遍历哈希表等。 哈希函数将 key 映射为数组索引，从而访问对应桶并获取 value 。 两个不同的 key 可能在经过哈希函数后得到相同的数组索引，导致查询结果出错，这种现象被称为哈希冲突。 哈希表容量越大，哈希冲突的概率就越低。因此可以通过扩容哈希表来缓解哈希冲突。与数组扩容类似，哈希表扩容操作的开销很大。 负载因子定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件。 链式地址通过将单个元素转化为链表，将所有冲突元素存储在同一个链表中。然而，链表过长会降低查询效率，可以通过进一步将链表转换为红黑树来提高效率。 开放寻址通过多次探测来处理哈希冲突。线性探测使用固定步长，缺点是不能删除元素，且容易产生聚集。多次哈希使用多个哈希函数进行探测，相较线性探测更不易产生聚集，但多个哈希函数增加了计算量。 不同编程语言采取了不同的哈希表实现。例如，Java 的 HashMap...

哈希算法 前两节介绍了哈希表的工作原理和哈希冲突的处理方法。然而无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生。 如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。如下图所示，对于链式地址哈希表，理想情况下键值对均匀分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都存储到同一个桶中，时间复杂度退化至 O(n)O(n)O(n) 。 键值对的分布情况由哈希函数决定。回忆哈希函数的计算步骤，先计算哈希值，再对数组长度取模： 1index = hash(key) % capacity 观察以上公式，当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值，进而决定了键值对在哈希表中的分布情况。 这意味着，为了降低哈希冲突的发生概率，我们应当将注意力集中在哈希算法 hash()...

哈希冲突 上一节提到，通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。比如，输入空间为全体整数，输出空间为数组容量大小，则必然有多个整数映射至同一桶索引。 哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。 改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。 链式地址 在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。下图展示了一个链式地址哈希表的例子。 基于链式地址实现的哈希表的操作方法发生了以下变化。 查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key...

哈希表 哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1)O(1)O(1) 时间内获取对应的值 value 。 如下图所示，给定 nnn 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。 除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下表所示。 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 O(1)O(1)O(1) 时间。 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 O(n)O(n)O(n) 时间。 删除元素：需要先查询到元素，再从数组（链表）中删除，使用 O(n)O(n)O(n) 时间。 表   元素查询效率对比...