Ⅰ. 堆的概念与性质
0x00 堆的概念
📚 若有一个关键码的集合???， 堆分为大堆和小堆。将其所有元素按完全二叉树的顺序存储在一个数组中：
① 如满足??? 且??
? ?
?则称为小堆。
② 如满足??且?
? ?
? ，则称为大堆。
我们将根节点最大的堆称作最大堆（即大根堆），根节点最小的堆称作最小堆（即小根堆）。
🔺 综上所述：
① 大堆：树中任何一棵树及子树中，父亲的值都大于等于孩子 （??）
② 小堆：树中任何一颗树及子树中，父亲的值都小于等于孩子?（? ）
0x01 堆的性质
① 堆总是一棵完全二叉树。
② 堆中的某个节点的值总是不大于或不小于其父节点的值。
0x02 堆的作用
① 堆排序
② 解决??问题，在?
?个数中找出最大的前?
?个或找出最小的?
?个
……
Ⅱ. 堆的定义
所有的数组都可以表示成完全二叉树，但是它不一定是堆。大堆：树中所有父亲都大于等于孩子小堆：树中所有父亲都小于等于孩子。下面我们将要实现的是大堆。
0x00 数组堆
typedef int HPDataType;
typedef struct Heap {
HPDataType* array; //指向动态开辟的数组
int size; //有效数据的个数
int capacity; //容量空间的大小
} HP;0x01 接口函数
📚 这是需要实现几个接口函数：
/* 堆的初始化 */
void HeapInit(HP* php);
/* 堆的销毁 */
void HeapDestroy(HP* php);
/* 堆的打印 */
void HeapPrint(HP* php);
/* 判断堆是否为空 */
bool HeapIfEmpty(HP* hp);
/* 堆的插入 */
void HeapPush(HP* php, HPDataType x);
/* 检查容量 */
void HeapCheckCapacity(HP* php);
/* 交换函数 */
void Swap(HPDataType* px, HPDataType* py);
/* 大根堆上调 */
void BigAdjustUp(int* arr, int child);
/* 小根堆上调 */
void SmallAdjustUp(int* arr, int child);
/* 堆的删除 */
void HeapPop(HP* php);
/* 小根堆下调*/
void SmallAdjustDown(int* arr, int n, int parent);
/* 大根堆下调 */
void BigAdjustDown(int* arr, int n, int parent);
/* 返回堆顶数据*/
HPDataType HeapTop(HP* php);
/* 统计堆的个数 */
int HeapSize(HP* php);Ⅲ. 堆的实现
0x00 堆的初始化（HeapInit）
💬 Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* array; //指向动态开辟的数组
int size; //有效数据的个数
int capacity; //容量空间的大小
} HP;🔑 解读：堆的实际结构就是一个数组，我们用数组去实现，想要让它支持增删查改，我们就不能使用静态数组，要用动态数组。这样我们就可以扩容，有 size 和 capacity，这里和顺序表差不多，这是一个非常通用的结构。
💬 Heap.c
/* 堆初始化 */
void HeapInit(HP* php) {
assert(php);
php->array = NULL;
php->capacity = php->size = 0;
}0x01 堆的销毁（HeapDestroy）
💬 Heap.h
void HeapDestroy(HP* php);💬 Heap.c
/* 堆的销毁 */
void HeapDestroy(HP* php) {
assert(php);
free(php->array);
php->capacity = php->size = 0;
}0x02 堆的打印（HeapPrint）
💬 Heap.h
void HeapPrint(HP* php);💬 Heap.c
/* 堆的打印 */
void HeapPrint(HP* php) {
int i = 0;
for (i = 0; i < php->size; i++) {
printf("%d ", php->array[i]);
}
printf("\n");
}0x03?判断堆是否为空（HeapIsEmpty）
💬 Heap.h
/* 判断堆是否为空 */
bool HeapIsEmpty(HP* hp);💬 Heap.c
/* 判断堆是否为空 */
bool HeapIsEmpty(HP* php) {
assert(php);
return php->size == 0; // 如果为size为0则表示堆为空
}🔑 解读：这里巧妙利用布尔特性，直接 return 数组大小即可。?size?== 0 则为真，反之返回假。
0x04?大堆的插入（HeapPush）
?📌 插入的核心思路：?
① 先将元素插入到堆的末尾，即最后一个孩子之后。
② 插入之后如果堆的性质遭到破坏，就将新插入的节点顺着其的父亲往上调整到合适位置。直到调到符合堆的性质为止。
我们先来解决这个插入功能，先实现下增容部分的代码，方便我们下面能更专心地研究堆的插入问题。这个我们在顺序表里也详细讲过，这里我们再复习一下：
检查是否需要增容（HeapCheckCapacity）
void HeapCheckCapacity(HP* php) {
if(php->size == php->capacity) {
int newCapacity = php->capacity == 0 ? 4 : (php->capacity * 2); //第一次给4，其他情况扩2倍
HPDataType* tmpArray = (HPDataType*)realloc(php->array, sizeof(HPDataType) * newCapacity); // 数组扩容
if(tmpArray == NULL) { //检查realloc
printf("realloc failed!\n");
exit(-1);
}
//更新他们的大小
php->array = tmpArray;
php->capacity = newCapacity;
}
}🔑 解读：参考顺序表章节的讲解，这里不再赘述。
根据堆的性质，如果不满足大堆和小堆，出现子大于父或父大于子的情况，为了保证插入之后堆还是堆，我们就需要进行自下往上的调整。堆插入数据对其他节点没有影响，只是可能会影响从它到根节点路径上节点的关系。
💭 举例：
① 比如下面的情况：新插入的为 60，子大于父（60 > 56 ），这时就需要交换。
② 还有更特殊的情况：比如新插入的为 100，100 和 56 交换完之后还要和 70 交换。
先把父亲赋值给孩子，再把孩子赋值给父亲，再让父亲往上走，判断是否比父亲大，如果大就再进行交换。?为了搞定这些情况，我们就需要写一个 "向上调整" 的算法（最坏调到根停止）：
向上调整（AdjustUp）
void AdjustUp(int* arr, int child) {
assert(arr);
// 首先根据公式计算算出父亲的下标
int parent = (child - 1) / 2;
// 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0）
while(child > 0) {
if(arr[child] > arr[parent]) { // 如果孩子大于父亲（不符合堆的性质）
// 交换他们的值
HPDataType tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
// 往上走
child = parent;
parent = (child - 1) / 2;
} else { // 如果孩子小于父亲（符合堆的性质）
// 跳出循环
break;
}
}
}🔑 解读：
① 设计 AdjustUp 接口时需要先想好要接收什么值，因为我们想要对数组内容进行调整，所以我们需要传入数组，并用 int* 接收。另外用 child 接收我们刚插入的值的下标，作为调整位置的起始位置。
②?首先要防止传入的数组为空。
③ 我们首先要确定孩子和父亲的下标，已知孩子求父亲：
? （该公式在上一章已经学过了）
孩子下标我们已经有了，因为我们把调整位置的起始位置，也就是刚插入的数据传到了该函数中并以 child 接收了。这时我们定义 parent 变量，根据公式就可以推导出父亲的下标了。
④ 我们已经得到了孩子和父亲的下标，我们就可以开始进行操作了。首先分析一下最坏的情况，最坏的情况就是调到根位置，child = parent，因为根节点永远是 0，child 为 0 时那么 parent 就该小于 0 了，所以当 child 作为根节点时就说明已经调完了，这里我们 while 的判断条件为 child > 0，至于为什么这里要这么别扭地以 child > 0 作为条件而不是 parent >= 0，我们下面会细说。
⑤ 进入循环后先 if 判断，如果数组中 child 的值大于 parent 的值，说明孩子大于父亲，这意味着不符合大堆的性质。我们就要进行置换的操作。这里我们创建一个 HPDataType 类型的 tmp 临时变量进行交换即可。
⑥ 交换完毕后，他们的值已经互相交换好了，这时我们要改变 parent 和 child 的指向，让它们继续往上走，以便于继续进行判断。child = parent，parent 再次根据公式算出新的 parent 即可。
⑦?设计下 if 的 else 部分，如果数组的 child 的值大于 parent 的值，说明符合大堆的性质了，?break 跳出循环即可。
? 写循环条件时为什么要写成：while(child?>?0)??我们要看是否调到根了，按照正常思路，不应该是看 parent 是否小于0吗？?while(parent?>=?0)
💡 这么写是不行的！这么写实际上是存在问题的我们带入一个值看看就知道了：
while(child?>?0)? ?
while(parent?>=?0) ?
我们来分析一下过程，拿个值带入测试一下：假设插入75
【开始】
70
50 30 (p)
25 15 10 75* (c)
parent最后等于2
【第一次】
70 (p)
50 75* (c)
25 15 10 30
parent最后等于0
【最后一次】
(p)
75* (c)
50 70
25 15 10 30
parent最后还是等于0（我们希望它的结果是小于0的）
为什么呢？最后一次往上走时，
child = parent; 此时child=0
parent = (child - 1) / 2;
(0 - 1) / 2 = 0 这么一来parent仍然会是0
导致parent根本就不会小于0！int main(void) {
int parent = (0 - 1) / 2;
printf("%d", parent);
return 0;
}🚩 运行结果： 0
🔺 所以我们要使用?while(child?>?0) ，既不会带来问题效果也和 parent>=0 一样。因为当 child =?0 时就说明已经触及到根了。
? 这里我们用到了交换，因为后面写删除接口也是需要用到交换的，我们不妨把它封装成一个接口，方便我们后续可以多次调用：
交换（Swap）
void Swap(HPDataType* px, HPDataType* py) {
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}void AdjustUp(int* arr, int child) {
assert(arr);
// 首先根据公式计算算出父亲的下标
int parent = (child - 1) / 2;
// 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0）
while(child > 0) {
if(arr[child] > arr[parent]) { // 如果孩子大于父亲（不符合堆的性质）
// 交换他们的值
Swap(&arr[child],&arr[parent]); // 传地址
// 往上走
child = parent;
parent = (child - 1) / 2;
} else { // 如果孩子小于父亲（符合堆的性质）
// 跳出循环
break;
}
}
}检查是否扩容和向上调整的接口都已经写好了，我们现在可以实现堆的插入了：
💬 Heap.h
void HeapPush(HP* php, HPDataType x);💬 Heap.c
void HeapPush(HP* php, HPDataType x) {
assert(php);
// 检查是否需要扩容
HeapCheckCapacity(php);
// 插入数据
php->array[php->size] = x;
php->size++;
// 向上调整 [目标数组，刚插入的数据]
AdjustUp(php->array, php->size - 1);
}🔑 解读：
① 首先检查 php 是否为空。
② 检查是否需要扩容调用我们刚才实现好的 HeapCheckCapacity 接口即可。
③ 随后插入数据即可，这里和顺序表的尾插的一样。
④ 最后调用 AdjustUp 接口，传入目标数组，和插入的数据（即?size - 1）。
0x05 堆的删除（HeapPop）
堆的删除，因为在讲堆的插入时我们用大堆演示的，我们这里先用小堆来演示。
📌 删除的核心思路：删除堆，删除的是堆顶的数据。就是删除这个树的根。
📚 将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
① 将堆顶元素与堆中最后一个元素进行交换。
② 删除堆中的最后一个元素。
③ 将堆顶元素向下调整到满足堆特性为止。
向下调整，把它调整成堆，跟左右孩子中小的那个交换。
结束条件（有一个成立即可）：
① 父
?小的孩子，则停止。
② 调整到叶子（因为叶子特征为没有孩子，左孩子下标超出数组范围，就不存在了）。
小堆向下调整（SmallAdjustDown）
void SmallAjustDown(int* arr, int n, int parent) {
int child = parent * 2 + 1; // 默认为左孩子
while(child < n) { // 叶子内
// 选出左右孩子中小的那一个
if(child + 1 < n && arr[child + 1] < arr[child]) {
child = child + 1;
}
// 如果孩子小于父亲（不符合小堆的性质）
if(arr[child] < arr[parent]) {
// 交换它们的值
Swap(&arr[child], &arr[parent]);
// 往下走
parent = child;
child = parent * 2 + 1;
} else { // 如果孩子大于父亲（符合小堆的性质）
// 跳出循环
break;
}
}
}
🔑 解读：
① 因为要考虑左孩子还是右孩子，我们可以定义两个变量，分别记录左孩子和有孩子。但是我们这里可以用更好的方法，只需要定义一个孩子即可。具体实现方法如下：首先创建 child，我们先默认它是左孩子，利用传进来的 parent 根据公式计算出 child 的大小：
因为我们暂且默认为左孩子，我们随后进入循环后要进行检查，看看是左孩子大还是右孩子大，这里我们只需要根据数组的性质，将 child + 1 即可得到右孩子的下标，从而方便我们进行比较。比较完毕后将 child 重新赋值，拿个孩子小就将 child 给谁。
② 一共有两个结束条件（出口），第一个结束条件是父亲小于孩子就停止，第二个结束条件是chi调整到叶子。所以，循环体判断部分根据我们分析的结束条件，如果调整到叶子就结束，我们接受了 n，也就是数组的大小，只要 child 超过数组的大小（child > n） 就结束，这是第一个出口。
③ 进入循环后，对比左孩子和右孩子哪一个更小，child 就交付给谁。这里还要注意的是，要防止孩子不存在的情况，如果 child + 1 比 n 大，就说明孩子不存在。所以我们再写 if 判断条件的时候就要注意了，我们加一个 child + 1 < n 的条件限制一下：
if(child + 1 < n && arr[child + 1] < arr[child]) {...}④ 确认好较小的孩子后，我们就可以开始比较孩子和父亲的大小了。如果孩子小于父亲，就不符合小堆的性质，我们就要交换它们的值。这里我们直接调用我们刚才写的 Swap 接口即可，这就是为什么在写向上调整的时候要我们单独把交换部分的代码写成函数的原因。
⑤ 交换完毕后，他们的值已经互相交换好了，这时我们要改变 parent 和 child 的指向，让它们往下走，parent = child ，child?再次根据公式算出新的?child 即可。
⑥ 设计下 if 的 else 部分，如果数组的 child 的值大于 parent 的值，说明符合小堆的性质了，?break 跳出循环即可，这是第二个出口。
下上调整的接口写好了，我们现在可以实现堆的删除了：
💬 Heap.h
void HeapPop(HP* php);💬 Heap.c
void HeapPop(HP* php) {
assert(php);
assert(!HeapIsEmpty(php));
// 删除数据
Swap(&php->array[0], &php->array[php->size - 1]);
php->size--;
// 向下调整 [目标数组，数组的大小，调整位置的起始位置]
SmalljustDown(php->array, php->size, 0);
}🔑 解读：
① 首先检查 php 是否为空。
② 因为删除必须得有东西可删，这里肯定是要检查是否为空的，调用 HeapIsEmpty?，逻辑反操作一下，断言数组不为空。
③ 因为删除堆，删除的是堆顶的数据，所以这里我们要在删除前让，删除数据根据我们的经验，直接 size - - 即可。
④ 最后调用 AdjustDown?接口，传入目标数组，数组的大小，和起始位置（即 0）。
? 如果我们想改成大堆呢？
💡 只需要改变一下判断条件即可：
① 选出左右孩子大的那一个。
② 小堆是所有父亲都小于孩子，大堆则是所有父亲都要大于孩子，我们来改一下：
大根堆向下调整（BigAdjustDown）
void BigAdjustDown(int* arr, int n, int parent) {
int child = parent * 2 + 1; // 默认为左孩子
while (child < n) { // 叶子内
// 选出左右孩子中大的那一个
if (child + 1 < n && arr[child + 1] > arr[child]) {
child++;
}
if (arr[child] > arr[parent]) { // 如果孩子大于父亲（不符合大堆的性质）
// 交换它们的值
Swap(&arr[child], &arr[parent]);
// 往下走
parent = child;
child = parent * 2 + 1;
}
else { // 如果孩子小于父亲（符合大堆的性质）
// 跳出循环
break;
}
}
}🔑 解读：很简单，只需要改一下判断的条件即可。
💬 Test.c
我们来测试一下刚才写的部分代码。
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapTest1() {
// 大根堆
int a[] = { 70, 56, 30, 25,15,10,75 };
HP hp;
HeapInit(&hp);
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
HeapPush(&hp, a[i]);
}
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
}
int main()
{
HeapTest1();
return 0;
}🚩 运行结果：
0x06 返回堆顶数据（HeapTop）
💬 Heap.h
HPDataType HeapTop(HP* php);💬 Heap.c
/* 返回堆顶数据 */
HPDataType HeapTop(HP* php) {
assert(php);
assert(!HeapIsEmpty(php));
return php->array[0];
}🔑 解读：
① 首先检查传入的?php 是否为空，还要防止堆内没有数据。
② 返回堆顶，堆顶就是根，根的下标为 0，返回根即可。
0x07?统计堆的个数（HeapSize）
💬 Heap.h
HPDataType HeapTop(HP* php);💬 Heap.c
/* 统计堆的个数 */
int HeapSize(HP* php) {
assert(php);
return php->size;
}🔑 解读：
① 首先检查传入的?php 是否为空。
② 与其说统计堆的个数，不如说是返回堆的个数，因为根本就不需要统计，直接返回 size 就完事了。
Ⅳ. 【霍洛维兹数据结构笔记】The Heap Abstract Data Type
0x00 大根堆定义
A max tree is a tree in which the key value in each node is no smaller than the key values in its children (if any). A max heap is a complete binary tree that is also a max tree.
大根树中每个结点的关键字都不小于孩子结点（如果有的话）的关键字。大根堆即是完全二叉树又是大根树。
A min tree is a tree in which the key value in each node is no larger than the key values in its children (if any). A min heap is a complete binary tree that is also a min tree.
小根数中每个结点的关键字都不大于孩子节点（如果有的话）的关键字。大根堆即是完全二叉树又是小根树。
值得注意的是，我们将堆表示为一个数组，尽管我们没有使用位置0。
从堆的定义可以看出：
? ? ? ? ① 最小树的根包含树中最小的键。
? ? ? ? ② 最大树的根包含树中的最大键。
对最大堆的基本操作：(1) 创建一个空堆? (2) 向堆中插入一个新元素? (3) 从堆中删除最大元素。
0x02?Priority Queues
堆，常用来实现优先级队列。优先级队列的删除操作以队列元素的优先级高低为准。
譬如总是删除优先级最高的元素，或总是删除优先级最低的元素。
优先级队列的插入操作不限制元素的优先级，任何时刻任何优先级的元素都可以入列。
实现优先级队列：堆被用来作为优先级队列的有效实现。
0x03 大根堆插入操作?-?Insertion Into A Max Heap
#define MAX_ELEMENTS 200 /*maximum heap size+1 */
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
typedef struct {
int key;
/* other fields */
} element;
element heap[MAX_ELEMENTS];
int n = 0;
我们可以通过以下步骤在一个有 ?个元素的堆中插入一个新元素。
① 将元素放在新的节点（即第 ?个位置）
② 沿新节点到根的路径移动，如果当前节点的元素比其父节点的元素大，则将它们互换并重复。
[Program 5.13] Insertion into a max heap （大根堆插入操作）
void insert_max_heap(element item, int* n)
{
/* insert item into a max heap of current size *n */
int i;
if (HEAP_FULL(*n)) {
fprintf(stderr, "The heap is full. \n");
exit(1);
}
i = ++(*n);
while ((i != 1) && (item.key > heap[i / 2].key)) {
heap[i] = heap[i / 2];
i /= 2;
}
heap[i] = item;
}
对于?insert_max_heap 的分析：
该函数首先检查是否有一个完整的堆。 如果没有，则将 ?设置为新堆的大小（
）。
然后通过使用while循环确定项目在堆中的正确位置。
这个 while 循环被迭代了 ?次，因此时间复杂度为?
?。
0x04 大根堆删除操作 - Delete From A Max Heap
当我们从一个最大堆中删除一个元素时，我们总是从堆的根部取走它。
如果堆有 ?个元素，在删除根部的元素后，堆必须成为一个完整的二叉树，少一个节点，即（
）个元素。。
我们把元素放在根节点的位置 ?，为了建立堆，我们向下移动堆，比较父节点和它的子节点，交换失序的元素，直到重新建立堆为止。
[Program 5.14] : Deletion from a max_heap - 大根堆删除操作
element delete_max_heap(int* n)
{
/* delete element with the highest key from the heap */
int parent, child;
element item, temp;
if (HEAP_EMPTY(*n)) {
fprintf(stderr, "The heap is empty");
exit(1);
}
/* save value of the element with the largest key */
item = heap[1];
/* use last element in heap to adjust heap */
temp = heap[(*n)--];
parent = 1; child = 2;
while (child <= *n) {
/* find the larger child of the current parent */
if ((child < *n) && (heap[child].key < heap[child + 1].key))
child++;
if (temp.key >= heap[child].key) break;
/* move to the next lower level */
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}对于 delete_max_heap 的分析：
函数 delete_max_heap 的操作是向下移动堆，比较和交换父节点和子节点，直到重新建立堆的定义。由于一个有 ?个元素的堆的高度为?
，while 循环了??次。因此时间复杂度为?
.
Ⅴ. 二叉搜索树 -?BINARY SEARCH TREES
?0x00 介绍
虽然堆很适合于需要优先级队列的应用，但它并不适合于我们删除和搜索任意元素的应用。 二叉搜索树在操作、插入、删除和搜索任意元素方面的性能都很不错。
0x01 定义
二叉搜索树是一棵二叉树。它可能是空的。 如果它不是空的，它满足以下属性：
① 每个元素都有一个键，没有两个元素有相同的键，也就是说，键是唯一的。
② 非空的左子树中的键必须比根中的键小。
③ 非空的右子树中的键必须比根中的键大。
④ 左和右子树也是二叉搜索树
思考：如果我们按顺序遍历二叉搜索树，并按访问的顺序打印节点的数据，
那么打印的数据顺序是什么？
0x02 搜索一颗二叉搜索树
[Program 5.15] : Recursive search for a binary search tree
tree_pointer search(tree_pointer root, int key)
{
/* return a pointer to the node that contains key.
If there is no such node, return NULL. */
if (!root) return NULL;
if (key == root->data) return root;
if (key < root->data)
return search(root->left_child, key);
return search(root->right_child, key);
}[Program 5.16] Iterative search for a binary search tree
tree_pointer search2(tree_pointer tree, int key)
{
/* return a pointer to the node that contains key.
If there is no such node, return NULL. */
while (tree) {
if (key == tree->data) return tree;
if (key < tree->data)
tree = tree->left_child;
else
tree = tree->right_child;
}
return NULL;
}分析：设??是二叉搜索树的高度，那么 search 和 search2 的时间复杂性都是
?。 然而，搜索有一个额外的堆栈空间要求，是
?。
0x03 二叉搜索树的插入
要插入一个新的元素，键 。
首先，我们通过搜索树来验证该键是否与现有元素不同。
如果搜索不成功，我们就在搜索终止的地方插入该元素。
?[Program 5.17] : Inserting an element into a binary search tree
void insert_node(tree_pointer* node, int num)
{
/* If num is in the tree pointed at by node do nothing;
otherwise add a new node with data = num */
tree_pointer ptr, temp = modified_search(*node, num);
if (temp || !(*node)) {
/* num is not in the tree */
ptr = (tree_pointer)malloc(sizeof(node));
if (IS_FULL(ptr)) {
fprintf(stderr, "The memory is full");
exit(1);
}
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
if (*node) /* insert as child of temp */
if (num < temp->data)
temp->left_child = ptr;
else temp->right_child = ptr;
else *node = ptr;
}
}modified_search 在二叉搜索树 *node 中搜索键 num。 如果树是空的，或者num被提出，它返回NULL。 否则，它返回一个指向搜索过程中遇到的树的最后一个节点的指针。
分析 insert_node：
设 ?为二叉搜索树的高度。 由于搜索需要
?时间，算法的其余部分需要 Θ(1) 时间。 所以insert_node需要的总体时间是?
.
0x04 二叉搜索树的删除
删除一个叶子节点。
将其父级的相应子字段设置为NULL并释放该节点。
删除有单个子节点的非叶节点：erase 该节点，然后将单个子节点放在被 erase 节点的位置上。
删除有两个子节点的非叶节点：用其左子树中最大的元素或其右子树中最小的元素替换该节点。 然后从子树中删除这个被替换的元素。
注意，子树中最大和最小的元素总是在零度或一度的节点中。
不难看出，删除可以在 ?时间内进行，其中
?是二叉搜索树的高度。
0x05 二叉搜索树的高度
然而，当随机插入和删除时，二叉搜索树的高度平均为 ?。
最坏情况下高度为 ?的搜索树被称为平衡搜索树。
Ⅵ. 不相交集合的表示?-?SET REPRESENTATION
0x00 引子
我们研究树在集合表示中的使用。 为了简单起见，我们假设集合的元素是数字 ?。 我们同时还假设被表示的集合是成对且不相交的。
下图展示的是一个可能的表示方法：
请注意，对于每一个集合来说，节点都是从子集到父集的链接。
对这些集合进行的操作如下：
① 不相交集合的合并。如果我们希望得到两个不相交的集合 ?和
的合并，用
?代替
?和
。 ② Find(i). 找到包含元素
?的集合
0x01 合并与查找操作 - Union and Find Operations
假设我们希望得到 ?和
的合并。 我们只需让其中一棵树成为另一棵树的子树。
?可以用下图中的任何一种表现形式：
为了实现集合的合并操作，我们只需将其中一个根的父域设置为另一个根。
下图展示了命名这些集合的方式：
为了简化对 union 和 find 算法的讨论，我们将忽略集合的名称，而用代表它们的树的根来识别集合。 由于树中的节点被编号为 0 到 n-1 ，我们可以用节点的编号作为一个索引。
注意，根节点的父节点为 -1
我们可以实现find(i)，方法是从 ?开始跟踪指数，直到父的指数为负数为止。
[Program 5.18] : Initial attempt at union-find functions.
int find(int i)
{
for (; parent[i] >= 0; i = parent[i])
;
return i;
}
void union1(int i, int j)
{
parent[i] = j;
}分析 union1 和 find1：
让我们处理以下的 union-find 操作序列：
这个序列产生了下图的蜕化树：
由于? 的时间是恒定的，所有的
?个联合可以在时间
?内处理完毕。
对于每个发现，如果该元素处于第i层，那么找到其根部所需的时间是 ?。
因此，处理 ?个发现所需的总时间为：
通过避免退化树的创建，我们可以获得更有效的 union 和 find 的操作实现。
0x02?定义
?的加权规则。如果树
?中的节点数少于树j中的节点数，则使
?成为
?的父节点；否则使??
?成为
?的父节点。
为了实现加权规则，我们需要知道每棵树上有多少个节点。 也就是说，我们需要在每棵树的根部维护一个计数字段。 我们可以将根部的父字段中的计数保持为一个负数。
[Program 5.19] : Union operation incorporating the weighting rule.
void union2(int i, int j)
{
/* parent[i] = -count[i] and parent[j] = -count[j] */
int temp = parent[i] + parent[j];
if (parent[i] > parent[j]) {
parent[i] = j; /* make j the new root */
parent[j] = temp;
}
else {
parent[j] = i; /* make i the new root */
parent[i] = temp;
}
}引理：令 ?是一棵有
?个节点的树，作为
?的结果而创建，那么?
?的深度为：
参考资料
Fundamentals of Data Structures in C
