大顶堆/小顶堆
堆
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2025-07-12
平衡二叉树(AVL)
如果插入二叉搜索树的元素在插入之前就已经有序，那么插入后的二叉搜索树会退化为链表。在这种情况下，所有操作的时间复杂度将从 \(O(log_2n)\) 劣化为 \(O(n)\) 。因此产生了平衡二叉树，能够实现在插入、删除时保持树的平衡，避免树退化为链表。平衡二叉树全称为：平衡二叉搜索树(Balanced Binary Search Tree). 特点： 自平衡：在插入或删除节点时，AVL树会通过旋转操作（如左旋、右旋、左右旋、右左旋）来保持树的平衡。 如果一个树是AVL树，那么它的左右子树都是AVL树。 树中任意一个节点的平衡因子绝对值不超过1。 平衡因子：默认每个节点的平衡因子=左子树高度-右子树高度。（或者右子树高度-左子树高度） 实现 基本节点： 123456789101112typedef struct AVLNode { int data; int height{1}; // 节点高度：表示从当前节点到距离他最远的叶子节点的距离+1（叶子节点高度为1，空节点高度为0） AVLNode *left; AVLNode...
2025-07-10
二叉搜索树
特点 非空左子树的所有结点的值小于其根结点的值。 非空右子树的所有结点的值大于其根结点的值。 左、右子树都是二叉搜索树。 实现 主要操作 查询： 实现思路： 递归：调用递归方法，传入要查询的树的根节点和要查询的值，判断根节点值大小，然后递归查询。 非递归：通过while循环，判断当前指针指向的节点值是否满足条件或者当前指针是否为空。然后根据情况令指针指向当前节点的左子节点或者右子节点。如果当前节点变为空，说明没有找到目标值。 插入： 递归：调用递归方法，传入要插入的值和树的根节点。如果当前根节点值小于插入的值，递归调用插入方法，传入右子树的根节点。如果当前根节点值大于插入的值，递归调用插入方法，传入左子树的根节点。如果相等，报错（二叉搜索树不允许存在重复的值）。 非递归：通过while循环，通过判断插入值的大小，不断改变遍历的指针指向的节点，同时用另一个指针记录上一个遍历过的节点（方便查找到叶子节点时向前看一个节点，便于操作）。 删除： 首先找到要删除的节点，然后判断情况。主要分为三种情况： 左子树为空，只有右子树：直接将右子树向上提升一级（用右子树替换要删除的节点...
2025-07-08
二叉树
特性： 对于一个非空二叉树，其**\(叶子节点数=度为2的节点数+1\)**。 非空二叉树的第k层最多有\(2^k-1\)个节点。（根节点处于第1层） 高度为H的二叉树最多有\(2^H-1\)个节点。（高度=层数，根节点在第1层，叶子节点在第H层）（满二叉树） 对完全二叉树从上到下，从左到右依次编号\(1,2,3,...,n\)，则有以下关系： 最后一个分支节点的编号为：\(\left\lfloor n/2 \right\rfloor\)。如果\(i<\left\lfloor n/2\right\rfloor\)，则节点i为非叶子节点，否则为叶子节点。 叶子节点只能出现在最后两层。 若存在度为1的节点，则最多只可能有一个。且该节点只有左孩子，没有右孩子。 若总节点数n为奇数，则每个非叶子节点都有左右孩子。如果总节点数n为偶数，则编号最大的非叶子节点只有左孩子，没有右孩子。其余非叶子节点都有左右孩子。 当i>1时，节点i的双亲节点编号为：\(\left\lfloor i/2\right\rfloor\)。（如果i==0，那么节点i就是整个树的根节点。）
2025-07-09
完全二叉树
完全二叉树 基本概念 完全二叉树：基于二叉树，要求除了最下层外，其余各层都是满节点。并且，最后一层的节点必须尽可能向左放。 例：下面所有二叉树都不是完全二叉树： 特征 叶子节点之可能在最下面的两层出现 对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。 所有节点中，最多只有一个节点度为1（只有一个孩子）。 实现 方便起见，完全二叉树一般用数组实现而不用链表。 对于用数组存储的完全二叉树，有以下特点：（下标从0开始）（根节点层数为1） 如果一个节点在数组中下标为i，则它在树中的层数为 \(\left\lfloor log_2{(i+1)} \right\rfloor\) （向下取整），它的左子节点在数组中对应的下标为：\(2i+1\)（如果存在），右子节点在数组中对应的下标为\(2i+2\)（如果存在）。 如果完全二叉树总共有n (n>0)个节点，那么树高： \(h=\left \lfloor log_2{n} \right \rfloor+1\) （或者\(\left\lceil log_2{(n+1)} \rig...
2025-07-13
满二叉树
基本概念： 满二叉树：**层数(高度)**为H，总节点数为\(2^H-1\)的二叉树。（根节点在第1层，所有叶子节点都在第H层）。 此处认为满二叉树 == 完美二叉树。 有些地方存在另一种分类方法：完美(prefect)二叉树、完满(full)二叉树、完全(complete)二叉树。具体概念与上述满二叉树概念也有所区别，此处不做讨论。 本文所讨论的满二叉树对应上面的完美(prefect)二叉树，而不对应完满(full)二叉树。 而上述完满(full)二叉树实际对应王道考研书中的正则二叉树。 特点： 第i层一定有\(2^{i-1}\)个节点。（根节点在第1层） 前i层（1 ~ i层）节点数之和为\(2^i-1\)。 由前序遍历构建满二叉树 给定一个满二叉树的前序遍历数组，要求由该数组构建目标满二叉树，返回构建完成的满二叉树的根。然后输出该满二叉树的中序遍历。 C++实现： 一般来说，构造二叉树不能只用前序遍历，但这里给出了一个额外的条件，即该二叉树是满二叉树。我们可以利用这个额外的条件。 对满二叉树来说：前序遍历中根之后的元素数量（假设为n）应该是偶数（2 * 一个子树...
2025-07-14
红黑树
概念 一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 (“RED” or “BLACK”)，用于确保树在插入和删除时保持平衡。 红黑树是 4 阶 B 树（2-3-4 树）的变体。 特点 红黑树本身也是二叉搜索树，具有所有二叉搜索树的特点。 一棵合法的红黑树必须遵循以下性质： （节点颜色）所有节点为红色或黑色。 （根节点）根节点必须是黑色。 （叶子节点）NIL 节点（空叶子节点）都是黑色。 （红色节点）红色节点的左右子节点都为黑色（从每个NIL节点到根节点的路径上不能有连续的两个红色节点）。 （黑色节点）从任意节点到其所在子树的 NIL 节点的每条路径上的黑色节点数量相同（简称黑高）。 下图为一个合法的红黑树： 扩展特点 最长路径不超过最短路径的两倍。 由上一特点可得：任一节点的左右子树的高度差不会超过2倍。 对比平衡二叉树：平衡二叉树要求左右子树高度相差不超过1，而红黑树要求左右子树高度差不超过2倍。由此看来平衡二叉树对平衡的要求更严格，插入时进行的旋转操作更多。 实现 插入 插入的新节点默认是红色节点。因为如果对一个红黑树插入一个黑色节点，无...
