树与堆

binary tree

从物理结构来看，树是一种基于链表的数据结构。当然也可以用数组表示，将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

class TreeNode:
    """二叉树节点类"""
    def __init__(self, val: int):
        self.val: int = val                # 节点值
        self.left: TreeNode | None = None  # 左子节点引用
        self.right: TreeNode | None = None # 右子节点引用

# 初始化二叉树
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)

# 构建节点之间的引用（指针）
n1.left = n2
n1.right = n3

n2.left = n4
n2.right = n5

通常将高度和深度定义为经过的边的数量，但有些题目或教材可能会将其定义为经过的节点的数量。在这种情况下，高度和深度都需要加 1。

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。

二叉树分类

• 完美二叉树：所有层的节点都被完全填满，也称作满二叉树，除叶节点外其余节点的度都是2，节点总数为 \(2^{h+1} - 1\)
• 完全二叉树：除最底层外，其它层节点都被填满，且最底层节点尽量靠左填充
• 完满二叉树：除了叶节点外，其余节点都有两个子节点
• 平衡二叉树：任意节点左右子树的高度之差不超过 1

二叉树的最佳结构是完美二叉树，最差结构则是所有节点都偏向一侧，即退化为了链表

二叉树遍历

遍历方式是通过指针逐个访问节点，但由于非线性，遍历树要更复杂，需要借助搜索算法。

• 广度优先遍历：层序遍历

• 深度优先遍历：前序、中序、后序遍历

binary search tree

二叉搜索树（BST）任意节点 左子树各节点的值 < 节点值 < 右子树各节点的值，通常用作系统中的多级索引

自平衡，意味着树会通过算法（旋转、分裂、合并）在每次插入或删除节点之后自动调整，以保持树的平衡，从而确保树的高度保持在平衡因子（-1、0、1）范围内。

• AVL树，自平衡二叉搜索树，任何节点的两个子树的高度差最多为1
• 红黑树，自平衡二叉搜索树，从根到叶子的最长路径不会超过最短路径的两倍
• B树，自平衡多路搜索树，所有的叶子节点都在同一层

heap

堆，是一种满足特定条件的完全二叉树，根节点称为堆顶，将底层最靠右的节点称为堆底

完全二叉树非常适合用数组来表示，所以通常采用数组来存储堆。