本篇博客参考了书本《王道数据结构》，和一些自己的见解，简单地总结了一下树相关内容。由于本人实力太菜，可能存在着一些欠缺。

目录

树的基本概念 

树的定义

树中结点数与度数的关系

二叉树

二叉树的定义

 几种特殊的二叉树

二叉树的性质

二叉树的存储结构

二叉树的遍历

由遍历序列构造二叉树 

线索二叉树

线索二叉树定义

通过中序遍历构建中序线索二叉树递归算法：

遍历中序线索二叉树：

森林

树、森林的相互转换

1.树转为二叉树:

2.森林转为二叉树 :

3.二叉树转为森林:

森林的遍历

树和森林与二叉树遍历方法的对应关系

哈夫曼树和哈夫曼编码

哈夫曼树定义

 哈夫曼树的构造

哈夫曼编码

并查集

并查集概念 

合并操作：

 并查集的应用

二叉搜索树（BST）

二叉搜索树定义

 二叉搜索树的查找

二叉搜索树的插入

二叉搜索树的删除

二叉搜索树的查找效率分析

平衡二叉树 

平衡二叉树的定义

​编辑 平衡二叉树的插入

平衡二叉树的删除

平衡二叉树的查找

红黑树

红黑树的定义

结论1：

结论2：

红黑树的插入

结论3：

红黑树的删除 

B树 

B树的定义

​编辑B树的查找

B树的高度

B树的插入 

B树的删除 

B+树 

B+树的基本概念

B树和B+树的差异

废话

---

 什么是树？

自然界中的树：

                                               

程序员的树：

      

开个玩笑，以下是数据结构中的树的基本概念：

树的基本概念 

树的定义

树是一种递归的数据结构，同时也是一种分层结构。树是n(n>=0)个结点的有限集。当n=0时，称为空树。

任一棵非空树应满足：

1）有且仅有一个特定的称为根的结点。

2）当n >1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，并且称为根的子树。像这样：

在我们讨论树时，会涉及到以下基本术语：

1. 节点(Node)：树中的基本单元,包含数据和指向其他节点的链接。 每个节点都有一个值(数据)和零个或多个子节点。

2. 根节点(Root Node)：树的起始节点,没有父节点。每棵树都有且只有一个根节点。

3. 子节点(Child Node)：一个节点直接链接到的下一级节点。一个节点可以有零个或多个子节点。

4. 父节点(Parent Node)：直接链接到某个节点的上一级节点。除根节点外,每个节点都有一个父节点。

5. 叶节点(Leaf Node)：没有子节点的节点,也称为终端节点。

6. 内部节点(Internal Node)：至少有一个子节点的节点,不包括根节点和叶节点。

7. 兄弟节点(Sibling Nodes)：拥有相同父节点的节点。

8. 树的高度(Height)：从根节点到最远叶节点的最长路径长度。空树的高度为0,单个节点的高度为1。

9. 树的深度(Depth)：某个节点到根节点的路径长度。根节点的深度为0。

10..子树(Subtree)：由某个节点及其所有后代节点组成的树。

11.节点的度（degree）:某个结点所包含的孩子数量

树中结点数与度数的关系

1）树的结点数n等于所有结点的度数之和加1。

因为有 n 个结点 一定 会有n - 1条边。

2）度为m的树中第 i 层上至多有 m^(i - 1)个结点（i>=1）。

3）高度为h的m叉树至多有（m^h - 1）/ （m - 1）个节点。

原理是等比数列求和。

谈到树，常用的树当然是二叉树啦。

二叉树

二叉树的定义

二叉树是一种特殊的树形结构，其特点是每个节点至多有两个子树。并且二叉树的子树有左右之分，其次序不能颠倒。

 二叉树5种形态：

 几种特殊的二叉树

1）满二叉树：

2）完全二叉树：

 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

所以完全二叉树若有度为1的结点，有且仅有一个左孩子。

3）二叉搜索树（BST）：左节点val < 根val < 右节点val

4）平衡二叉树（AVL）：左右子树高度差不超过1。

5）红黑树（Bleak Red Tree）：自平衡的二叉搜索树。

6）正则二叉树：树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。

二叉树的性质

1）非空二叉树中N0 = N2 + 1。

2）非空二叉树的第k层最多有2^(k - 1)个结点。

3）高度为h的二叉树至多有2^h - 1个结点。

4）具有n个结点的完全二叉树的高度为⌊log2n⌋ +1。

二叉树的存储结构

1)顺序存储结构

将编号与数组下标一一对应顺序存储在一维数组中。适合满二叉树和完全二叉树，其余的二叉树会造成大量空间的浪费。

2)链式存储结构

二叉链表: 利用指针存储结点的左右孩子，避免了空间的浪费。

struct TreeNode {
    ElemType val;
    TreeNode *lchild;
    TreeNode *rchild;
    TreeNode() : val(0), lchild(nullptr), rchild(nullptr) {}
 };

三叉链表:在二叉链表的基础上增加指向父结点的指针域。

struct TreeNode {
    ElemType val;
    TreeNode *lchild;
    TreeNode *rchild;
    TreeNode *parent;
    TreeNode() : val(0), lchild(nullptr), rchild(nullptr),parent(nullptr) {}
};

静态二叉链表：使用数组记录左右孩子的数组下标。

struct BiTNode { // 结点结构
    ElemType val;
    int  lchild, rchild ;
}
struct BiTree {  // 树结构
    BNode nodes[ MAX_TREE_SIZE ];
    int  num_node;   // 结点数目
    int  root;       // 根结点的位置
}

二叉树的遍历

1.先序遍历：

1）访问根结点；

2）遍历访问左子树；

3）遍历访问右子树。

递归算法：

void perorder(TreeNode* root){
    if(!root) return ;
    visit(root);
    perorder(root->left);
    perorder(root->right);
}

 迭代算法：

vector preorder(TreeNode* root) {
    vector ans;
    stack stk;
    while( root != nullptr || !stk.empty()){
        while(root){
            ans.push_back(root->val);
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        root = root->right;
    }
    return ans;
}

2.中序遍历：

1）遍历访问左子树；

2）访问根结点；

3）遍历访问右子树。

递归算法：

void inorder(TreeNode* root){
    if(!root) return ;
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

迭代算法：

vector inorder(TreeNode* root) {
    vector ans;
    stack stk;
    while(root != nullptr || !stk.empty()){
        while(root){
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        ans.push_back(root->val);
        root = root->right;
    }
    return ans;
}

3.后序遍历：

1）遍历访问左子树；

2）遍历访问右子树；

3）访问根结点。

递归算法：

void postorder(TreeNode* root){
    if(!root) return ;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

迭代算法：

vector postorder(TreeNode* root) {
    vector ans;
    stack stk;
    while( root != nullptr || !stk.empty()){
        while(root){
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        ans.push_back(root->val);
        root = root->right;            
    }
    return ans;
}

4.层次遍历

利用队列：

vector> levelOrder(TreeNode* root) {
    vector> res;
    if(!root) return res;
    queue qu;
    qu.push(root);
    while( !qu.empty() ){
        int cursize = qu.size();
        res.push_back(vector());
        for(int i = 1; i <= cursize; ++i){
            auto node = qu.front();qu.pop();
            res.back().push_back(node->val);
            if(node->left) qu.push(node->left);
            if(node->right) qu.push(node->right);
        }             
    }
    return res;
 }

由遍历序列构造二叉树 

已知中序序列，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。

例如：先序遍历加中序遍历

 

后序加中序：从右至左看后序，在中序中找相对位置，方法同上。

层次加中序：从左至右看层次，在中序中找相对位置，层次定根，中序定位。

线索二叉树

线索二叉树定义

线索二叉树(Threaded Binary Tree)是在普通二叉树的基础上进行扩展的一种二叉树结构。

1. 每个节点除了有左右孩子指针外,还有一个线索指针。
2. 如果某个节点没有左子树,则左孩子指针指向该节点的前驱节点(中序遍历序列中的前一个节点)。
3. 如果某个节点没有右子树,则右孩子指针指向该节点的后继节点(中序遍历序列中的下一个节点)。
4. 根节点的左孩子指针指向中序遍历的第一个节点,根节点的右孩子指针指向中序遍历的最后一个节点。

这种结构的特点是:

1. 利用原本无用的空指针域存储前驱和后继节点的信息,从而实现了中序遍历的快速访问。
2. 可以不需要使用递归就可以实现中序遍历,遍历效率更高。
3. 可以方便地找到某个节点的前驱和后继节点。

先序线索和后序线索类似。 

 线索二叉树结点代码：

struct TreedNode{
    int val;
    TreeNode *lchild;
    TreeNode *rchild;   
    int ltag,rtag;    //左右线索标志
    TreeNode(int x) : val(x), lchild(nullptr), rchild(nullptr), ltag(0), rtag(0) {}
}

标志域含义：

ltag = 0 ：lchild指向左孩子    ltag = 1：lchild指向结点前驱

rtag = 0 ：rchild指向右孩子   rtag = 1：rchild指向结点后继

通过中序遍历构建中序线索二叉树递归算法：

// 结节点定义
struct TreeNode {
    int val;
    TreeNode *left, *right;
    bool leftThread, rightThread; // 标记是否有前驱或后继线索
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), leftThread(false), rightThread(false) {}
};
// 全局变量,记录上一个访问的节点
TreeNode *pre = nullptr;
// 中序遍历建立线索二叉树
void inThreading(TreeNode *root) {
    if (root == nullptr) return;   
    // 递归左子树
    inThreading(root->left);    
    // 处理当前节点
    if (root->left == nullptr) {
        root->left = pre;
        root->leftThread = true;
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = root;
        pre->rightThread = true;
    }
    pre = root;    
    // 递归右子树
    inThreading(root->right);
}
// 中序遍历构造线索二叉树
void CreateInThread(TreeNode *root) {
    if(root != nullptr){
        inThreading(root);
        pre-right = nullptr;
        pre->rightThread = true;
    }
}

遍历中序线索二叉树：

void inOrder(TreeNode *root) {
    TreeNode *p = root;
    while (p != nullptr) {
        // 一直向左走,直到遇到leftThread为false的节点
        while (!p->leftThread)
            p = p->left;
        
        cout << p->val << " ";
        
        // 沿着右线索访问后继节点
        while (p->rightThread && p->right != nullptr) {
            p = p->right;
            cout << p->val << " ";
        }
        
        // 转向右子树
        p = p->right;
    }
}

先序线索二叉树和后序线索二叉树类似，只需变动线索化构造的代码与调用线索化左右子树递归函数的位置。

森林

森林是m(m>=0)棵互不相交的树的集合。（就是一堆树。）

树、森林的相互转换

1.树转为二叉树:

2.森林转为二叉树 :

将每棵树的根结点连成一串。

3.二叉树转为森林:

森林的遍历

对每棵独立树进行依次遍历。

树和森林与二叉树遍历方法的对应关系

哈夫曼树和哈夫曼编码

哈夫曼树定义

含有n个带权叶结点的二叉树中，带权路径长度（WPL）最小的二叉树称为哈夫曼树。

 哈夫曼树的构造

从集合中选两个权值最小的结点构成一个新结点，组成一棵树放入集合中，依次类推，直至集合中剩一棵树为止。

所以构建过程中会生成n - 1个结点，哈夫曼树结点总数为2n - 1。 权值越小的结点到根结点的路径越长。哈夫曼树中不存在度为1的结点。

哈夫曼编码

前缀编码：没有一个编码是另一个编码的前缀。

哈夫曼编码：一种无损数据压缩算法,它基于哈夫曼树来为每个字符分配一个唯一的二进制编码。

利用二叉树设计二进制前缀编码 

约定左分支表示0，右分支表示1，从根结点的路径上用分支标记组成的序列作为该叶结点字符的编码。将每个字符当作独立的结点，其权值为它出现的频率（或次数）

 这棵哈夫曼树的WPL = 1 * 45 + 3 * （13 + 12 + 16）+ 4 * （5 + 9）= 224

若采用3位固定长度编码，则得到的二进制编码长度为300位。因此哈夫曼编码共压缩了25%的数据，利用哈夫曼树可以设计最短的二进制前缀编码。

并查集

并查集概念 

是一种简单的集合，查询两个东西是不是属于一个集合中。

并查集两个功能：查询、合并

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

初始化并查集：

#include 
using namespace std;
const int N = 1e5+5;
int pre[N]; //结点的父结点
int rnk[N],sz[N];  //用于按秩合并和启发式合并
int m,n;
int main(){
    cin >> n;
    for(int i = 1;i <= n; ++i) pre[i] = i,sz[i] = 1;  //初始化并查集，并将sz数组大小设为1
    return 0;
}

查根：

int root(int x){
    return pre[x] == x ? x : root(pre[x]);
}
//路径压缩  只需要将结点都插到父节点即可
int root(int x){
    return pre[x] = pre[x] == x ? x : root(pre[x]);
}
//循环写法
int root(int x){
	while(pre[x] != x) x = pre[x];
	return x;
}

路径压缩，按秩合并，启发式合并。只能三选一。 

因为路径压缩破坏了树的结构，而按秩合并和启发式合并将树变得更胖了。

合并操作：

void merge(int x,int y){
	x = root(x),y = root(y);  //先找根结点
    if(x == y) return ;
    pre[x] = y;
}
//按秩合并
void merge(int x,int y){
	x = root(x),y = root(y);
	if(x == y) return ;
    if(rnk[x] > rnk[y]) swap(x,y);  //若树x的高度>y的高度，交换
    pre[x] = y;
    if(rnk[x] == rnk[y]) rnk[y]++;  
}
//启发式合并，其实就是按大小合并，小的合到大的上
void merge(int x,int y){
	x = root(x),y = root(y);
	if(x == y) return ;
    if(sz[x] > sz[y]) swap(x,y);  //若树x的高度>y的高度，交换
    pre[x] = y;
    sz[x] += sz[y];  //最后数量累加
}

 并查集的应用

1. 连通性问题：判断图中两个节点是否连通。
2. 图的聚类：将图中连通的节点归类为一个集合。
3. 图的最小生成树：Kruskal 算法使用并查集来维护连通性。
4. 社交网络中的好友关系：判断两个人是否在同一社交圈。

聊到这，对树已经有些了解了，接下来登场的是骨灰级数据结构

 

二叉搜索树（BST）

二叉搜索树定义

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树数据结构,它具有以下性质:

1. 左子树上所有节点的值均小于根节点的值。
2. 右子树上所有节点的值均大于根节点的值。
3. 左、右子树也分别满足二叉搜索树的性质。

 二叉搜索树的查找

二叉搜索树的递归算法：

// 二叉搜索树的节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉搜索树的查找操作
TreeNode* searchBST(TreeNode* root, int val) {
    // 如果根节点为空或者找到目标值,则返回当前节点
    if (root == nullptr || root->val == val) {
        return root;
    }
    // 如果目标值小于当前节点的值,则在左子树中继续查找
    if (val < root->val) {
        return searchBST(root->left, val);
    }
    // 否则,在右子树中继续查找
    return searchBST(root->right, val);
}

二叉搜索树的非递归算法：

// 二叉搜索树的非递归查找操作
TreeNode* searchBSTIterative(TreeNode* root, int val) {
    // 从根节点开始查找
    TreeNode* curr = root; 
    // 循环查找,直到找到目标值或者到达叶子节点
    while (curr != nullptr) {
        // 如果找到目标值,返回当前节点
        if (curr->val == val) {
            return curr;
        }
        // 如果目标值小于当前节点的值,则继续在左子树中查找
        else if (val < curr->val) {
            curr = curr->left;
        }
        // 否则,继续在右子树中查找
        else {
            curr = curr->right;
        }
    }
    // 如果没有找到目标值,返回 nullptr
    return nullptr;
}

二叉搜索树的插入

插入顺序不同生成的二叉搜索树也不同。

// 二叉搜索树的节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉搜索树的插入操作
TreeNode* insertBST(TreeNode* root, int val) {
    // 如果根节点为空,创建一个新的节点并返回
    if (root == nullptr) {
        return new TreeNode(val);
    }
    // 如果目标值小于当前节点的值,则递归地插入到左子树
    if (val < root->val) {
        root->left = insertBST(root->left, val);
    }
    // 如果目标值大于等于当前节点的值,则递归地插入到右子树
    else {
        root->right = insertBST(root->right, val);
    }
    
    // 返回根节点
    return root;
}

二叉搜索树的删除

1）若被删结点是叶结点，则直接删除。

2）若被删结点z只有一棵左子树或右子树，则让z的子树称为z父节点的子树。

3）若被删结点z有左右子树，则令z的直接后继或直接前驱替代z。

 以下是C++代码实现删除操作

// 二叉搜索树的删除操作
TreeNode* deleteNode(TreeNode* root, int key) {
    // 如果根节点为空,直接返回
    if (root == nullptr) {
        return nullptr;
    }
    
    // 如果要删除的值小于当前节点的值,则递归地在左子树中删除
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    // 如果要删除的值大于当前节点的值,则递归地在右子树中删除
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    // 找到要删除的节点
    else {
        // 如果要删除的节点没有左子树
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // 如果要删除的节点没有右子树
        else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // 如果要删除的节点有左右子树
        else {
            // 找到右子树中的最小节点,用它来替换当前节点
            root->val = minValue(root->right);
            // 在右子树中删除最小节点
            root->right = deleteNode(root->right, root->val);
        }
    }
    
    return root;
}
// 找到右子树中的最小节点
int minValue(TreeNode* root) {
    int minv = root->val;
    while (root->left != nullptr) {
        minv = root->left->val;
        root = root->left;
    }
    return minv;
}

二叉搜索树的查找效率分析

为了提高查询效率，防止出现右图的情况，于是引入了基于BST的数据结构。

平衡二叉树 

平衡二叉树的定义

平衡二叉树也称AVL树，是一种特殊的二叉搜索树,它满足以下性质:

1. 对于树中的任意节点,其左子树和右子树的高度差的绝对值不超过 1。
2. 树中所有子树也都是平衡二叉树。

这种平衡性质确保了二叉搜索树的查找、插入和删除操作的时间复杂度都为 O(log n),而不会退化成 O(n)。

 平衡二叉树的插入

  二叉搜索树保证平衡的基本思想如下:每当在二叉搜索树中插入(或删除)一个结点时，首

先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉搜索特性的前提下，调整各结点的位置关系，使之重新达到平衡。

  平衡二叉树的插入过程前半部分于二叉搜索树相同，但在新节点插入时，需进行判断，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整分为以4种情况：

 1）LL平衡旋转（右单旋）。由于不平衡结点的左孩子（L）的左子树（L）插入新节点导致的，则需要一次右旋。将D向右上旋转代替B，将B向右下旋转成为D的右孩子，而D的原右子树成为B的左子树（这里为空）。

  2）RR平衡旋转（左单旋）。由于不平衡结点的右孩子（R）的右子树（R）插入新节点导致的，则需要一次左旋。将C向左上旋转代替A，将A向左下旋转成为C的左孩子，而C的原左子树成为A的右子树。

3）LR平衡旋转（先左旋再右旋） 。由于不平衡结点的左孩子（L）的右子树（R）插入新节点导致的，则需要进行两次旋转。先左旋，E上升到D的位置，再右旋B上升到A的位置。

 4）RL平衡旋转（先右旋再左旋） 。由于不平衡结点的右孩子（R）的左子树（L）插入新节点导致的，则需要进行两次旋转。先右旋，G上升到F的位置，再左旋E上升到C的位置。

 

c++代码实现插入操作

struct TreeNode {
	int val;
	int height;
	TreeNode* lchild;
	TreeNode* rchild;
	TreeNode(int x) :val(x), lchild(nullptr), rchild(nullptr) {};
};
int getHeight(TreeNode* node) {
	return node ? node->height : 0;
}
void llRotation(TreeNode* node, TreeNode*& root) {
	TreeNode* tmp = node->lchild;
	node->lchild = tmp->rchild;
	tmp->rchild = node;
	node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	tmp->height = max(getHeight(tmp->lchild), getHeight(tmp->rchild)) + 1;
	root = tmp;
}
void rrRotation(TreeNode* node, TreeNode*& root) {
	TreeNode* tmp = node->rchild;
	node->rchild = tmp->lchild;
	tmp->lchild = node;
	node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	tmp->height = max(getHeight(tmp->lchild), getHeight(tmp->rchild)) + 1;
	root = tmp;
}
void avlInsert(TreeNode*& T, int val) {
	if (T == nullptr) {
		T = new TreeNode(val);
		T->height = 0;
	}
	else if (val < T->val) {
		avlInsert(T->lchild, val);
		int Lheight = getHeight(T->lchild);
		int Rheight = getHeight(T->rchild);
		if (Lheight - Rheight == 2) {
			if (val < T->lchild->val) {
				//LL调整
				llRotation(T, T);
			}
			else {
				//LR调整
				rrRotation(T->lchild, T->lchild); //左孩子进行左旋
				llRotation(T, T);  //再让根进行右旋
			}
		}
	}
	else if (val > T->val) {
		avlInsert(T->rchild, val);
		int Lheight = getHeight(T->lchild);
		int Rheight = getHeight(T->rchild);
		if (Rheight - Lheight == 2) {
			if (val > T->rchild->val) {
				//RR调整
				rrRotation(T, T);
			}
			else {
				//RL调整
				llRotation(T->rchild, T->rchild);  //右孩子进行右旋
				rrRotation(T, T);  //再让根进行左旋
			}
		}
	}
	T->height = max(getHeight(T->lchild), getHeight(T->rchild)) + 1;
}

平衡二叉树的删除

与平衡二叉树的插入的操作类似，以删除结点w为例来说明平衡二叉树删除操作步骤：

1）用二叉搜索树的方法对结点w执行删除操作。

2）若为叶结点，直接删除。若导致不平衡，则从结点w开始向上回溯，找到第一个不平衡的结点z（即最小不平衡子树）;y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。

3）然后对z为根的子树进行平衡调整（LL、RR、LR、RL）。

// 删除节点
TreeNode* avlDelete(TreeNode* root, int key) {
    if (!root) return nullptr; // 空树直接返回
    // 1. 找到要删除的节点
    if (key < root->val) {
        root->left = avlDelete(root->left, key);
    } else if (key > root->val) {
        root->right = avlDelete(root->right, key);
    } else { // 找到要删除的节点
        // 2. 如果是叶子节点,直接删除
        if (!root->left && !root->right) {
            delete root;
            return nullptr;
        }
        // 3. 如果只有一个子节点,用子节点替换
        else if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // 4. 如果有两个子节点,用中序后继节点替换
        else {
            TreeNode* successor = findMin(root->right);
            root->data = successor->val;
            root->right = avlDelete(root->right, successor->val);
        }
    }
    // 更新高度并旋转以保持平衡
    root->height = 1 + max(height(root->left), height(root->right));
    int balance = getBalance(root);
    if (balance > 1 && getBalance(root->left) >= 0) // LL 旋转
        return llRotate(root);
    if (balance > 1 && getBalance(root->left) < 0) // LR 旋转
        return lrRotate(root);
    if (balance < -1 && getBalance(root->right) <= 0) // RR 旋转
        return rrRotate(root);
    if (balance < -1 && getBalance(root->right) > 0) // RL 旋转
        return rlRotate(root);
    return root;
}

平衡二叉树的查找

在平衡二叉树上进行关键字比较次数不超过树的深度。因此查找效率为O(log n)；

 

红黑树

为了保持AVL树的平衡性，在插入和删除操作后，会非常频繁地调整全树整体拓扑结构，代价较大。为此在AVL树的平衡标准上进一放宽条件，引入了红黑树。c++STL库中的map底层就是用红黑树实现的。

红黑树的定义

一棵红黑树就是满足红黑性质的二叉搜索树：

①每个结点或是红色，或是黑色

②根结点是黑色

③叶结点（虚拟外部结点）都是黑色

④不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）

⑤对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量都是相同的

口诀：左根右，根叶黑，不红红，黑路同

 

结论1：

从根到叶结点的最长路径不大于最短路径的2倍。

结论2：

有n个内部结点的红黑树高度h <= 2log(n + 1)。

 

以下是红黑树结点定义c++代码： 

#include 
enum class Color { RED, BLACK };
template 
struct RBTreeNode {
    T data;
    RBTreeNode* left;
    RBTreeNode* right;
    RBTreeNode* parent;
    Color color;
    RBTreeNode(const T& val, Color c = Color::RED, RBTreeNode* l = nullptr, RBTreeNode* r = nullptr, RBTreeNode* p = nullptr)
        : data(val), color(c), left(l), right(r), parent(p) {}
};

红黑树的插入

红黑树的插入过程和二叉搜索树的插入过程基本类似，不同之处在于，在红黑树中插入新结点后需要进行调整（着色与旋转），以满足红黑树的性质。

结论3：

新插入红黑树中的结点初始着为红色。

红黑树的插入流程如下：

1）若插入结点为根结点，则染黑，结束。

2）采用二叉搜索树插入法插入，若父节点是黑色，什么都不做，此时就是一棵标准的红黑树。

 

3）若插入结点的父结点为红，则违反性质 ④（违反不红红就看叔）。分为以下情况：

情况1：如果叔（父结点为兄弟）为黑色，则进行LL、RR、LR、RL调整，然后谁换谁染色（儿换爷，儿爷染色；父换爷，父爷染色。LR、RL调整时第二步旋转后染色）。

情况2：如果叔为红色，父叔爷染色，爷变新节点（若为根节点则染为黑色），若爷与他的父皆为红，则再分情况而论。

 

代码：

没有代码，因为我不会。

 

红黑树的删除 

红黑树的删除过程:

1. 首先找到要删除的结点。如果该结点有两个子节点,则用中序遍历的前驱或后继结点替换该节点。

2. 如果被删除的结点只有一个子结点,则直接用该结点替换被删除的结点。

3. 如果被删除的结点没有子结点,则直接删除该结点。

4. 删除结点后,可能会破坏红黑树的性质,需要进行调整。主要有以下几种情况:

   • 如果被删除的节点是红色的,直接删除即可,不需要调整。
   • 如果被删除的节点是黑色的,且它的子节点是红色的,将子节点变黑即可。
   • 如果被删除的节点是黑色的,且它的子节点也是黑色的,则需要进行调整操作,包括旋转和重新着色。直到满足红黑树的性质。

B树 

B树的定义

B树是一种平衡多路查找树,它是一种用于实现索引的数据结构。所谓m阶B树是所有结点的平衡因子等于0 的m路平衡查找树。

一棵m阶B树或空树，满足以下特性：

1）树中每个结点至多有m棵子树，至多有m - 1个关键字

2）若根结点不是叶结点，至少有2棵子树，即至少1个关键字

3）除根结点外所有的非叶结点至少有⌈m/2⌉棵子树，至少⌈m/2⌉ - 1个关键字

4）⌈m/2⌉ - 1 <= n <= m - 1（n为结点中的关键字的个数）

5）所有的叶结点都在同一层，且不带任何信息。

B树的查找

  在B树上进行查找与二叉排序树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。 

  B树的查找包含两个基本操作:1）在B树中找结点；2）在结点内找关键字。由于B树常存储在磁盘上，则前一查找操作是在磁盘上进行的，而后一查找操作是在内存中进行的，即在磁盘上找到目标结点后，先将结点信息读入内存，然后再采用顺序查找法或折半查找法。因此，在磁盘上进行查找的次数即目标结点在B树上的层次数，决定了B树的查找效率。 

B树的高度

B树的大部分操作所需的磁盘存取次数与B树的高度成正比

一棵包含n（n >= 1）个关键字、高度为h、阶数为m的B树：

1）若让每个结点的关键字个数达到最多，则容纳同样多关键字的B树高度达到最小。有                h >= logm(n + 1)

2） 若让每天结点的关键字个数达到最少，则容纳同样多关键字的B树高度达到最大。有                  h <= log⌈m/2⌉( (n + 1) / 2) + 1

B树的插入 

插入结点始终为终端结点，若满（结点内达到了m - 1个关键字）则⌈m/2⌉位置为父结点，左右分块。若父结点也满了，则开创一个父结点，再分......

 

 

B树的删除 

删除操作与插入操作类似，但涉及了“合并”问题。

具体操作流程如下，只讨论被删关键字在终端结点的情形，有三种情况：

1）直接删。若被删关键字所在节点删除前的关键字的个数>=⌈m/2⌉，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

2）兄弟够借。若被删关键字所在节点删除前关键字个数 =  ⌈m/2⌉ - 1，且与该结点相邻的右（或左）兄弟结点的关键字个数 >= ⌈m/2⌉,则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。

 3）兄弟不够借。若被删关键字所在节点删除前关键字个数 =  ⌈m/2⌉ - 1，且与该结点相邻的左、右兄弟结点的关键字个数都 = ⌈m/2⌉ - 1,则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。

 

  在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0(根结点关键字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根； 若双亲结点不是根结点，且关键字个数减少到⌈m/2⌉ - 2,则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。  

B+树 

B+树的基本概念

B+树是数据库所需而出现的一种B树的变形树。

一棵m阶B+树满足以下条件：

1)每个分支结点最多有m棵子树(孩子结点)。 

2)非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。

3)结点的子树个数与关键字个数相等。 

4)所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列

并且相邻叶结点按大小顺序相互链接起来(支持顺序查找)。 

5)所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块) 中关键字的最大值及指向其子结点的指针。 

B树和B+树的差异

1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n + 1棵子树。

2）在B+树中，每个非根结点的关键字个数n的范围是⌈m/2⌉ <= n <= m(非叶根结点：2 <= n <= m)；而在B树中，每个非根结点关键字个数n的范围是⌈m/2⌉ - 1 <= n <= m - 1(根节点 ：1 <= n <= m - 1)。

3)在B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中:而

在B树中，最外层的终端结点包含的关键字和其他结点包含的关键子是不重复的。

 4)在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点的每个索引项只含

有对应子树的最大关键字和指向该子树的指针，不含有对应记录的存储地址，这样能使

一个磁盘块存储更多的关键字，使得磁盘读/写次数更少，查找速度更快。 

5)在B+树中，用一个指针指向关键字最小的叶结点，将所有叶结点串成一个线性链表。

 

  B+树的查找、插入和删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在B+ 树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。  

废话

历时十几个小时，终于整理了完了。还有什么图论中的最小生成树，选择排序的败者树就不是本章的内容了。