从二叉树到红黑树

二叉查找树

对于树中的每个节点 X X X

左子树所有关键字值小于 X X X 的关键字值右子树所有关键字值大于 X X X 的关键字值

#ifndef _Tree_H struct TreeNode; // 树节点类型 typedef int ElementType; // 值的类型 typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; // 树节点类型的指针 SearchTree MakeEmpty(SearchTree T); // 建立一颗空树 Position Find(ElementType X, SearchTree T); Position FindMin(SearchTree T); Position FindMax(SearchTree T); SearchTree Insert(ElementType X,SearchTree T); SearchTree Delete(ElementType X,SearchTree T); ElementType Retrieve(Position P); #endif /* _Tree_H */ #include "tree.h" #include <stdio.h> // 包含NULL的定义 #include <stdlib.h> // 包含free函数的定义 struct TreeNode{ ElementType Elemet; SearchTree Left; SearchTree Right; }; // 建立一棵空树 // 递归的清空整棵树的所有节点，释放他们占用的内存 SearchTree MakeEmpty(SearchTree T){ if (T != NULL){ MakeEmpty(T->Left); MakeEmpty(T->Right); free(T); } return NULL; } // 二叉查找树的Find操作 Position Find(ElementType X, SearchTree T){ if (T == NULL) return NULL; if (X < T->Elemet) return Find(X, T->Left); else if (X > T->Elemet) return Find(X, T->Right); else return T; } // 递归的实现 Position FindMin(SearchTree T){ if (T == NULL) return NULL; else if (T->Left == NULL) return T; else return FindMin(T->Left); } // 非递归实现 Position FindMax(SearchTree T){ if (T != NULL) while (T->Right != NULL) T = T->Right; return T; } // 插入元素到二叉查找树,返回插入X后的子树根 SearchTree Insert(ElementType X, SearchTree T){ if (T == NULL){ // 递归到不存在的子树就是要插入的位置 T = malloc(sizeof(struct TreeNode)); if (T == NULL) perror("Out of space!!!"); else{ T->Elemet = X; T->Left = T->Right = NULL; } } else if (X < T->Elemet){ T->Left = Insert(X, T->Left); } else if (X > T->Elemet){ T->Right = Insert(X, T->Right); } return T; } // 删除元素，用【右子树的最小数据】(或者左子树的最大数据)代替该节点，然后递归的删除【右子树的最小数据】节点 SearchTree Delete(ElementType X, SearchTree T){ Position TmpCell; if (T == NULL) perror("Element not found"); else if (X < T->Elemet){ T->Left = Delete(X, T->Left); } else if (X > T->Elemet){ T->Right = Delete(X, T->Right); } else if (T->Left && T->Right){ // Tow children TmpCell = FindMin(T->Left); T->Elemet = TmpCell->Elemet; // 代替 T->Left = Delete(TmpCell->Elemet, T->Left); // 递归删除 } else{ // One or zero children TmpCell = T; if (T->Left == NULL){ T = T->Right; }else if (T->Right == NULL){ T = T->Left; } } return T; } AVL树

AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树。一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度为 -1）。

让我们把必须重新平衡的节点叫做 α \alpha α。由于任意节点最多有两个儿子，因此高度不平衡时， α \alpha α 点的两棵子树的高度差2。容易看出，这种不平衡可能出现在下面四种情况中：

对 α 的左儿子的左子树进行一次插入。对α 的左儿子的右子树进行一次插入。对α 的右儿子的左子树进行一次插人。对 α 的右儿子的右子树进行一次插入。

情形1和4是关于α 点的镜像对称，而2和3是关于α 点的镜像对称。因此，理论上只有两种情况，当然从编程的角度来看还是四种情形。 第一种情况是插入发生在“外边”的情况（即左一左的情况或右一右的情况），该情况通过对树的一次单旋转（single rotation)而完成调整。 第二种情况是插入发生在“内部”的情形（即左-右的情况或右-左的情况），该情况通过稍微复杂些的双旋转（double rotation）来处理。我 们将会看到，这些都是对树的基本操作，它们多次用于平衡树的一些算法中。

单旋转

旋转时不改变元素横向顺序，即符合搜索树排序，在此基础上变换树

重的儿子 k 1 k_1 k1​ 上移成为新根老根 k 2 k_2 k2​ 成为新儿子重的儿子 k 1 k_1 k1​ 的轻子树 Y Y Y 跟随老根 k 2 k_2 k2​

对称情形

双旋转

失衡情形

向 Y Y Y 插入一项，这个事实保证它是非空的。 因此，我们可以假设 Y Y Y 它有一个根和两棵子树。恰好好树 B B B 或树 C C C 中有一颗比 D D D 深两层（除非它们都是空的），但是我们不能肯定是哪一棵，我们可以假设都比 D D D 深，做通用调整

k 2 k_2 k2​ 作新根， k 1 k_1 k1​、 k 2 k_2 k2​ 作新儿子 B B B 成 k 1 k_1 k1​ 右子树 C成 k 3 k_3 k3​ 左子树

叫做双旋转是因为进行两次类似单旋转的操作 一次围绕k1 k2左旋，之后再右旋

对称情形

AVL树的最坏情况

在最坏的情况下，AVL树（即自平衡二叉搜索树）的深度与其节点数 n n n 是对数关系。AVL树通过旋转操作来确保任何节点的两个子树的高度差（平衡因子）不超过1，从而保持树的高度尽可能低。

对于包含 n n n 个节点的AVL树，其高度 h h h 满足以下关系： h = O ( log ⁡ n ) h = O(\log n) h=O(logn)

具体来说，AVL树的高度不会超过 1.44 log ⁡ 2 ( n + 1.5 ) − 0.325 1.44 \log_2(n + 1.5) - 0.325 1.44log2​(n+1.5)−0.325（这个界是由一些研究者得出的，虽然不是最紧的，但提供了一个很好的上界）。然而，在实际应用中，我们通常简化地说AVL树的高度是 O ( log ⁡ n ) O(\log n) O(logn)。

这意味着，在最坏的情况下，AVL树中的查找、插入和删除操作的时间复杂度都是 O ( log ⁡ n ) O(\log n) O(logn)，因为所有这些操作都需要遍历从根到某个叶子节点的一条路径，而这条路径的长度（即树的高度）是 O ( log ⁡ n ) O(\log n) O(logn)。

总结一下，最坏情况的AVL树深度（即高度）是对数级别的，与节点数 n n n 成对数关系。

例程

前置定义

前置定义

struct AvlNode{ ElementType Element; AvlTree Left; AvlTree Right; int Height; }; int Max(int a, int b){ return a > b ? a : b; } // 计算AVL节点高度的函数 static int Height(Position P){ if (P == NULL) return -1; else return P->Height; } 单旋转 - LL左外插入失衡

// 单旋转 LL失衡 static Position SingleRotateWithLeft(Position K2){ Position K1; K2->Left = K2->Right; K1->Right = K2; K2->Height = Max(Height(K2->Left),Height(K2->Right))+1; K1->Height = Max(Height(K1->Left),K2->Height) +1; return K1; } 单旋转 - RR失衡 // 单旋转 RR失衡 static Position SingleRotateWithRight(Position K2){ Position K1; K1 = K2->Right; // K1是K2的右孩子 K2->Right = K1->Left; // K2的右孩子变为K1的左孩子 K1->Left = K2; // K1的左孩子变为K2 // 更新高度 K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1; K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1; return K1; // 返回新的根节点K1 } 双旋转 - LR左儿子的右子树插入失衡

// 双旋转 LR失衡 static Position DoubleRotateWithLeft(Position K3){ // K1 与 K2 左旋平衡 K3->Left = SingleRotateWithLeft(K3->Left); // K3 与 K2 右旋平衡 return SingleRotateWithLeft(K3); } 双旋转 - RL右儿子的左子树插入失衡 // 双旋转 RL失衡 static Position DoubleRotateWithRight(Position K3){ // K1 与 K2 右旋平衡右子树 K3->Right = SingleRotateWithRight(K3->Right); // K3 与 K2 左旋平衡整个树 return SingleRotateWithRight(K3); } B-tree

随着数据的插入，树的深度会变深，IO次数更多，影响读取效率。 如果数据比较发生在集中的数据区，有利于内存的局部集中读入提高性能 B树就是一个有序的多路查询树

阶为M的B-树是一颗具有下列结构特性的树：

树的根或者是一篇树叶，或者其儿子数在2和M之间。除根外，所有非树叶节点的儿子数在[M/2]和M之间所有树叶都在相同的深度上

所有数据都存储在树叶上。

从b树到红黑树可以直接看 b站的讲解 .bilibili /video/BV1Q24y1y7pP

红黑树是b树的一种特例的变体