分析数据结构中的各种树

树

定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。具有以下特点：

• 每个结点有零个或多个子结点；
• 没有父结点的结点称为根结点；
• 每一个非根结点有且只有一个父结点；
• 除了根结点外，每个子结点可以分为多个不相交的子树；

空集合也是树，称为空树。空树中没有结点。

相关定义

• 根（Root）：树中最顶端的节点，根没有父节点。
• 叶结点或终端结点：度为0的结点称为叶结点；
• 非终端结点或分支结点：度不为0的结点；
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙；
• 兄弟结点：具有相同父结点的结点互称为兄弟结点；
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；
• 结点的度：一个结点含有的子树的个数称为该结点的度；
• 树的度：一棵树中，最大的结点的度称为树的度；
• 结点的层次/层级：根为 Level 0 层，根的子节点为 Level 1 层，以此类推。
• 树的高度或深度：树中层的数量。比如只有 Level 0,Level 1,Level 2 则高度为 3；
• 森林：由m（m>=0）棵互不相交的树的集合称为森林。

一个普通的树结构如下

二叉树

定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

特点

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

性质

• 在二叉树的第i层上最多有2i-1 个结点 。（i>=1）

• 二叉树中如果深度为k,那么最多有2k-1个结点。(k>=1）

• n0=n2+1，n0表示度数为0的结点数，n2表示度数为2的结点数。

• 在完全二叉树中，具有n个结点的完全二叉树的深度为[log₂n]+1，其中[log₂n]是向下取整。

• 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

  (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
  (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
  (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

存储

顺序存储

用一组连续的存储单元存放二叉树中的结点。按照二叉树结点从上至下、从左到右的顺序存储。

对于一般的二叉树，如果仍按从上至小、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系，只有添加一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后用一维数组顺序存储。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。

完全二叉树存储方式

非完全二叉树存储方式

灰色部分表示结点不存在，可以看出，连续存储方式出现了内存空白。

这种方式的存储对于右斜树而言，浪费的内存空间更大。

链式存储

用链式结构来表示一棵二叉树，即用链指针来指示其元素的逻辑关系。（二叉链表）

由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。

定义代码如下：

typedef struct BiTNode{
    TElemType data;//数据
    struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;

结构如图所示

遍历

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

二叉树的访问次序可以分为四种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前序遍历

从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

其访问顺序为：根结点->左子树->右子树

1. 从根结点出发，此为第一个到达的结点，输出；
2. 左子树遍历是否遍历完成，无则跳到3；右子树是否遍历完成，无则跳到4；叶子结点跳到5；
3. 输出左子树结点，此时，左子树可以理解为“根”，返回2；
4. 输出右子树结点，此时，右子树可以理解为“跟”，返回2；
5. 返回父结点，跳到2；
6. 全遍历完成，退出。

因此，前序遍历的输出为

A
A->B
A->B->D
A->B->D->E
A->B->D->E->G
A->B->D->E->G->C
A->B->D->E->G->C->F
A->B->D->E->G->C->F->H
A->B->D->E->G->C->F->H->I

实现代码如下

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
	      return;
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
    PreOrderTraverse(T->lchild);    /*再先序遍历左子树*/
    PreOrderTraverse(T->rchild);    /*最后先序遍历右子树*/
}

非递归版本

void PreOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreatStack(MAX_SIZE);    //创建并初始化堆栈S
    while(T || !IsEmpty(S))
    {
        while(T)        //一直向左并将沿途节点访问（打印）后压入堆栈 
        {
            printf("%d\n", T->Data);
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);    //节点弹出堆栈
            T = T->Right;  //转向右子树
        }
    }
}

中序遍历

对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的结点i，其必然为叶子，然后遍历i的父结点，再遍历i的兄弟结点。随着递归的逐渐出栈，最终完成遍历。

其访问顺序为：左子树->根结点->右子树

对于上图其输出顺序为

D
D->B
D->B->G
D->B->G->E
D->B->G->E->A
D->B->G->E->A->C
D->B->G->E->A->C->H
D->B->G->E->A->C->H->F
D->B->G->E->A->C->H->F->I

其实现代码如下

/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
		    return;
    InOrderTraverse(T->lchild); /*中序遍历左子树*/
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
    InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}

非递归版本

void InOrderTraversal(BinTree BT)
{ 
    BinTree T = BT;
    Stack S = CreatStack(MaxSize); //创建并初始化堆栈S
    while(T || !IsEmpty(S))
　　{
    　　while(T)    //一直向左并将沿途节点压入堆栈
    　　{ 
       　　 Push(S,T);
        　　T = T->Left;
    　　}
    　　if(!IsEmpty(S))
    　　{
       　　 T = Pop(S);                //节点弹出堆栈
       　　 printf("%d\n", T->Data);    //（访问） 打印结点
      　　  T = T->Right;              //转向右子树
    　　}
　　}
}

后序遍历

对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的结点i，其必然为叶子，然后遍历i的兄弟结点，再遍历i的父结点。随着递归的逐渐出栈，最终完成遍历。

其访问顺序为：左子树->右子树->根结点

对于上图其输出顺序为

D
D->G
D->G->E
D->G->E->B
D->G->E->B->H
D->G->E->B->H->I
D->G->E->B->H->I->F
D->G->E->B->H->I->F->C
D->G->E->B->H->I->F->C->A

其实现代码如下

/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
		    return;
    PostOrderTraverse(T->lchild);   /*先后序遍历左子树*/
    PostOrderTraverse(T->rchild);   /*再后续遍历右子树*/
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
}

非递归版本

void PostOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S1 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S1
    Stack S2 = CreatStack(MAX_SIZE);    //创建并初始化堆栈S2   
    while(T || !IsEmpty(S1))
    {
        while(T)        //一直向右并将沿途节点访问（压入S2）后压入堆栈S1 
        {
            Push(S2, T);
            Push(S1, T);
            T = T->Right;
        }
        if (!IsEmpty(S1))
        {
            T = Pop(S1);    //节点弹出堆栈
            T = T->Left;  //转向左子树
        }
    }
    while(!IsEmpty(S2))    //访问（打印）S2中元素
    {
        T = Pop(S2);
        printf("%d\n", T->Data);
    }          
}

层序遍历

层次遍历就是按照树的层次自上而下、自左而右的遍历二叉树。

实现代码如下

#include <deque>
using namespace std;

template<typename T, typename VST >
void levelIterationTraverse(BiNodePos(T) x, VST& visit)
{
    deque<BiNodePos(T)> q;
    q.push_back(x);
    while (!q.empty())
    {
        x = q.front(); q.pop_front();
        visit(x.data);
        if (x->lChild) q.push_back(x->lChild);
        if (x->rChild) q.push_back(x->rChild);
    }
}//O(n)

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

完美二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为完美二叉树，也叫做满二叉树。

其特点如下：

1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2. 非叶子结点的度一定是2。
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

特点：

1. 叶子结点只能出现在最下层和次下层。
2. 最下层的叶子结点集中在树的左部。
3. 倒数第二层若存在叶子结点，一定在右部连续位置。
4. 如果结点度为1，则该结点只有左孩子，即没有右子树。
5. 同样结点数目的二叉树，完全二叉树深度最小。

满二叉树一定是完全二叉树，但反过来不一定成立。

完满二叉树

所有非叶子结点的度都是2的树叫做完满二叉树。（只要你有孩子，你就必然是有两个孩子。）

三者总结

完美二叉树	Perfect Binary Tree	Every node except the leaf nodes have two children and every level (last level too) is completely filled. 除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
完全二叉树	Complete Binary Tree	Every level except the last level is completely filled and all the nodes are left justified. 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
完满二叉树	Full/Strictly Binary Tree	Every node except the leaf nodes have two children. 除了叶子结点之外的每一个结点都有两个孩子结点。

• 完美(Perfect)二叉树一定是完全(Complete)二叉树，但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
• 完美(Perfect)二叉树一定是完满(Full)二叉树，但完满(Full)二叉树不一定是完美(Perfect)二叉树。
• 完全(Complete)二叉树可能是完满(Full)二叉树，完满(Full)二叉树也可能是完全(Complete)二叉树。
• 既是完全(Complete)二叉树又是完满(Full)二叉树也不一定就是完美(Perfect)二叉树。

二叉查找树

二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(logn)。

中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望O(log n)，最坏O(n)（数列有序，树退化成线性表）。

查找算法

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
    // 在根指针T所指二元查找树中递归地查找其关键字等于key的数据元素，若查找成功，
    // 则指针p指向该数据元素节点，并返回TRUE，否则指针指向查找路径上访问的最后
    // 一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
    if (!T) { // 查找不成功
        p = f;
        return false;
    } else if (key == T->data.key) { // 查找成功
        p = T;
        return true;
    } else if (key < T->data.key) // 在左子树中继续查找
        return SearchBST(T->lchild, key, T, p);
    else // 在右子树中继续查找
        return SearchBST(T->rchild, key, T, p);
}

插入节点

1. 若b是空树，则将s所指节点作为根节点插入，否则：
2. 若s->data等于b的根节点的数据域之值，则返回，否则：
3. 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
4. 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

插入之后，以任一根节点为中心，左边所有值都小于根，右边所有值都大于根。

/* 当二元搜寻树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回 FALSE */
Status InsertBST(BiTree *T, ElemType e) {
    if (!T) {
        s = new BiTNode;
        s->data = e;
        s->lchild = s->rchild = NULL;
        T = s; // 被插节点*s为新的根结点
    } else if (e.key == T->data.key)
        return false;// 关键字等于e.key的数据元素，返回错误
    if (e.key < T->data.key)
        InsertBST(T->lchild, e);  // 将 e 插入左子树
    else
        InsertBST(T->rchild, e);  // 将 e 插入右子树
    return true;
}

删除节点

在二叉查找树删去一个结点，分三种情况讨论：

1. 若*p结点为叶子结点，即PL（左子树）和PR（右子树）均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

2. 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉查找树的特性。

   

3. 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：

   1. 令*p的左子树为*f的左/右（依*p是*f的左子树还是右子树而定）子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；
   2. 令*p的直接前驱（in-order predecessor）或直接后继（in-order successor）替代*p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。

   

   中心思想：以删除的节点为中心，找到左树中最大的（最右节点）进行替代；或者右树中最小的（最左节点）替代。

   Status DeleteBST(BiTree *T, KeyType key) {
       // 若二叉查找树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回
       // TRUE；否则返回FALSE
       if (!T)
           return false; //不存在关键字等于key的数据元素
       else {
           if (key == T->data.key)   //   找到关键字等于key的数据元素
               return Delete(T);
           else if (key < T->data.key)
               return DeleteBST(T->lchild, key);
           else
               return DeleteBST(T->rchild, key);
       }
   }
   
   Status Delete(BiTree *&p) {
       // 该节点为叶子节点，直接删除
       BiTree *q, *s;
       if (!p->rchild && !p->lchild) {
           delete p;
           p = NULL;  // Status Delete(BiTree *&p) 要加&才能使P指向NULL
       } else if (!p->rchild) { // 右子树空则只需重接它的左子树
           q = p->lchild;
           /*
           p->data = p->lchild->data;
           p->lchild=p->lchild->lchild;
           p->rchild=p->lchild->rchild;
           */
           p->data = q->data;
           p->lchild = q->lchild;
           p->rchild = q->rchild;
           delete q;
       } else if (!p->lchild) { // 左子树空只需重接它的右子树
           q = p->rchild;
           /*
           p->data = p->rchild->data;
           p->lchild=p->rchild->lchild;
           p->rchild=p->rchild->rchild;
           */
           p->data = q->data;
           p->lchild = q->lchild;
           p->rchild = q->rchild;
           delete q;
       } else { // 左右子树均不空
           q = p;
           s = p->lchild;
           while (s->rchild) {
               q = s;
               s = s->rchild;
           } // 转左，然后向右到尽头
           p->data = s->data;  // s指向被删结点的“前驱”
           if (q != p)
               q->rchild = s->lchild;  // 重接*q的右子树
           else
               q->lchild = s->lchild;  // 重接*q的左子树
           delete s;
       }
       return true;
   }

遍历

可参考本章“二叉树”一节的四种遍历。

构造一棵二叉查找树

用一组数值建造一棵二叉查找树的同时，也把这组数值进行了排序。其最差时间复杂度为O(n²)。

例如，若该组数值已经是有序的（从小到大），则建造出来的二叉查找树的所有节点，都没有左子树。自平衡二叉查找树可以克服上述缺点，其时间复杂度为O(nlog n)。一方面，树排序的问题使得CPU Cache性能较差，特别是当节点是动态内存分配时。而堆排序的CPU Cache性能较好。另一方面，树排序是最优的增量排序（incremental sorting）算法，保持一个数值序列的有序性。

树的构造其核心为对值的插入，“插入节点”一节已实现。

二叉查找树的性能

每个结点的C_i为该结点的层次数。最坏情看看看况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度为n，其平均查找长度为$$\frac{n+1}{2}$$（和顺序查找相同），最好的情况是二叉查找树的形态和折半查找的判定树相同，其平均查找长度和log₂n 成正比 O(log₂n)。

二叉查找树的优化

一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

笛卡尔树

笛卡尔树

笛卡尔树

笛卡尔树学习笔记

堆、二叉堆、堆排序

算法入门：堆排序

MVP树

todo

Top tree

T树

自平衡二叉查找树

自平衡二叉查找树（Self-Balancing Binary Search Tree）的运行时间与树的高度（Height）有关系。一棵树的高度指的是从树的根开始所能到达的最长的路径长度。树的高度可被递归性地定义为：

• 如果节点没有子节点，则高度为 0；
• 如果节点只有一个子节点，则高度为该子节点的高度加 1；
• 如果节点有两个子节点，则高度为两个子节点中高度较高的加 1；

计算树的高度要从叶子节点开始，首先将叶子节点的高度置为 0，然后根据上面的规则向上计算父节点的高度。以此类推直到树中所有的节点高度都被标注后，则根节点的高度就是树的高度。

下图显示了几棵已经计算好高度的BST树

如果树中节点的数量为 n，则一棵满足O(log₂n) 渐进运行时间的 BST 树的高度应接近于比 log₂n 小的最大整数。

树-a的节点数量为10，而高度为4，log₂10 = 3.3219，比 3.3219 小的最大整数是 3，所以树-a最理想的高度应该是3。（情况最好）

树-b的节点数量为8，而高度为3，所以log₂8 = 3，结果正好与树的高度相等。

树-c的节点数量是 5，所以log₂5 = 2.3219，则理想高度为 2，但实际上是 4。（情况最差）

我们可以通过移动距离最远的节点到中间的某个非叶子节点，以减少数的高度，以使该树的高度与节点数量的比例达到最优。

实际上我们真正面对的问题是如何保证 BST 的拓扑结构始终保持树高度与节点数量的最佳比例。在不试图让数据源决定数据顺序的情况下，新的节点插入后仍然可以保持 BST 树的平衡（balanced）。这种能够始终维持树平衡状态的数据结构称为自平衡二叉查找树（self-balancing binary search tree）。

一棵平衡树指的是树能够保持其高度与广度能够保持预先定义的比例。不同的数据结构可以定义不同的比例以保持平衡，但所有的比例都趋向于log₂n。那么，一颗自平衡的 BST 也同样呈现出 O(log₂n) 的渐进运行时间。

AVL树

AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n) 。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

// 计算平衡因子
int treeGetBalanceFactor(nodeptr_t root) {
    if(root == NULL)
        return 0;
    else
        return x->left->height - x->right->height;
}

旋转

在每一次插入数值之后，树的平衡性都可能被破坏，这时可以通过一个简单的操作来矫正平衡–旋转。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

• 左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
• 如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。
• 如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。

插入节点时分四种情况，四种情况对应的旋转方法是不同的：

对于被破坏平衡的节点 a 来说：

插入方式	描述	旋转方式
LL	在a的左子树根节点的左子树上插入节点而破坏平衡	右旋
RR	在a的右子树根节点的右子树上插入节点而破坏平衡	左旋
LR	在a的左子树根节点的右子树上插入节点而破坏平衡	先左旋后右旋
RL	在a的右子树根节点的左子树上插入节点而破坏平衡	先右旋后左旋

LL 右旋

新插入节点 3 破坏了树的平衡性，因此不平衡的树一定位于 3 所在子树上。找离新插入的节点最近的不平衡的树进行调整，上图中就是 6（左子树高度为2，右子树高度为0，差2）。

子树 6->4->3 为不平衡树，需要对其进行调整，对 4 进行右旋，使高度差减1，从而达到平衡状态。

右旋操作，就是把上图中的 6 节点和 4 节点进行“父子交换”。在仅有这三个节点时候，是十分简单的。但是当 4 节点处存在右孩子时，事情就变得有点复杂了。我们通常的操作是：抛弃右孩子，将之和旋转后的节点 6 相连，成为节点 6 的左孩子。

nodeptr_t treeRotateRight(nodeptr_t root) {
    nodeptr_t left = root->left;
    
    root->left = left->right; // 将将要被抛弃的节点连接为旋转后的 root 的左孩子
    left->right = root; // 调换父子关系

    left->height = max(treeHeight(left->left), treeHeight(left->right))+1;
    right->height = max(treeHeight(right->left), treeHeight(right->right))+1;
    
    return left;
}

RR 左旋

左旋和右旋类似，都是单旋。

nodeptr_t treeRotateLeft(nodeptr_t root) {
    nodeptr_t right = root->right;

    root->right = right->left;
    right->left = root;

    left->height = max(treeHeight(left->left), treeHeight(left->right))+1;
    right->height = max(treeHeight(right->left), treeHeight(right->right))+1;

    return right;
}

LR 先左旋后右旋

左旋一次后，不平衡状况依然存在，还需要再次进行旋转。

RL 先右旋后左旋

类似 LR 情况。

LR 和 RL 实现代码如下：

nodeptr_t treeRebalance(nodeptr_t root) {
    int factor = treeGetBalanceFactor(root);
    if(factor > 1 && treeGetBalanceFactor(root->left) > 0) // LL
        return treeRotateRight(root);
    else if(factor > 1 && treeGetBalanceFactor(root->left) <= 0) { //LR
        root->left = treeRotateLeft(root->left);
        return treeRotateRight(temp);
    } else if(factor < -1 && treeGetBalanceFactor(root->right) <= 0) // RR
        return treeRotateLeft(root);
    else if((factor < -1 && treeGetBalanceFactor(root->right) > 0) { // RL
        root->right = treeRotateRight(root->right);
        return treeRotateLeft(root);
    } else { // Nothing happened.
        return root;
    }
}

AVL树的旋转图解和简单实现

详解 AVL 树（基础篇）

插入和删除操作

利用递归来实现AVL树的插入操作

void treeInsert(nodeptr_t *rootptr, int value)
{
    nodeptr_t newNode;
    nodeptr_t root = *rootptr;

    if(root == NULL) {
        newNode = malloc(sizeof(node_t));
        assert(newNode);

        newNode->data = value;
        newNode->left = newNode->right = NULL;

        *rootptr = newNode;
    } else if(root->data == value) {
        return;
    } else {
        if(root->data < value)
            treeInsert(&root->right,value);
        else
            treeInsert(&root->left,value)
    }

    treeRebalance(root);
}

删除也同样使用递归

void treeDelete(nodeptr_t *rootptr, int data)
{
    nodeptr_t *toFree;
    nodeptr_t root = *rootptr;

    if(root) {
        if(root->data == value) {
            if(root->right) {
                root->data = treeDeleteMin(&(root->right));
            } else {
                toFree = root;
                *rootptr = toFree->left;
                free(toFree);
            }
        } else {
        if(root->data < value)
            treeDelete(&root->right,value);
        else
            treeDelete(&root->left,value)
        }

        treeRebalance(root);
    }
}

在线演示

此网站可以看到 AVL 树的可视化，墙裂推荐。

红黑树

红黑树是在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

黑色高度： 从根节点到叶节点的路径上黑色节点的个数。

特性

1. 每个节点要么是红色，要么是黑色；
2. 根节点永远是黑色的；
3. 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
4. 每个红色节点的两个子节点一定都是黑色；
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

注意：
性质 3 ：红黑树的每个叶子节点都是空节点，并且叶子节点都是黑色。

性质 4 ：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。

因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N - 1;最长路径的情况为节点红黑

相间，树的高度为 2(N - 1) 。

性质 5 ：红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。

红黑树的左旋右旋

红黑树左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。

漫画：什么是红黑树？

面试旧敌之红黑树

30张图带你彻底理解红黑树

AA树

AA树—简单的红黑树

左倾红黑树

替罪羊树

伸展树

树堆

加权平衡树

B树

B树也称B-树,它是一颗多路平衡查找树。描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。

B树、B-树

m阶B树定义：

1. 每个结点关键字个数n取值范围为 Math.ceil(m/2)-1 <= n <= m-1；
2. 根结点最少可以只有1个关键字；
3. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它；
4. 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，

B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。

我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key

就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

B树的插入操作

插入操作是指插入一条记录，即（key, value）的键值对。

如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key，则一定是在叶子结点中进行插入操作。

1. 根据要插入的key的值，找到叶子结点并插入。
2. 判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
3. 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

以5阶B树为例，在5阶B树中，结点最多有4个key,最少有2个key。

1. 在空树中插入39，此时根结点就一个key，此时根结点也是叶子结点

   

2. 继续插入22，97和41，根结点此时有4个key

   

3. 继续插入53，

   

   插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

   

4. 依次插入13，21，40，同样会造成分裂，结果如下图所示。

   

5. 依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。

   

6. 插入key值为26的记录，插入后的结果如下图所示。

   

   当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。

   

   进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

   

7. 最后再依次插入key为17,28,29,31,32的记录，结果如下图所示。

   

在实现B树的代码中，为了使代码编写更加容易，可以将结点中存储记录的数组长度定义为m而非m-1，这样方便底层的结点由于分裂向上层插入一个记录时，上层有多余的位置存储这个记录。同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

一般来说，对于确定的m和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。

B树的删除操作

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1. 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
2. 该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
3. 如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key

1. 原始状态

   

2. 在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

   

3. 在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

   

   删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

   

4. 在上述情况下接着32，结果如下图。

   

   当删除后，当前结点中只key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

   

   当前结点key的个数满足条件，故删除结束。

5. 上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

   

   同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

   

   同理，对于当前结点而言只能继续合并了，最后结果如下所示。

   

   合并后结点当前结点满足条件，删除结束。

B树和B+树的插入、删除图文详解

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

B+树

B+树

漫画算法：什么是 B+ 树？

重温数据结构：理解 B 树、B+ 树特点及使用场景

B+树及插入和删除操作详解 —— 深度好文、强烈推荐

特征

m阶B+树

1. 每个结点关键字个数n取值范围为 Math.ceil(m/2)-1 <= n <= m；
2. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素）；
3. 每个元素不保存数据，只用来索引，所有数据都保存在叶子节点；
4. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
5. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

如图所示，B+树中含有两个头指针，一个指向整棵树的根结点，另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序链接，所有的叶子结点构成了一个 sqt 指针为头指针的链表。

所以，B+树可以进行两种查找运算：

• 利用 sqt 链表做顺序查找
• 从树的根结点开始，进行类似于二分查找的查找方式。

在 B+树中，所有非终端结点都相当于是终端结点的索引，而所有的数据都存放在终端结点中，所以在从根结点出发做查找操作时，如果非终端结点上的关键字恰好等于给定值，此时并不算查找完成，而是要继续向下直到叶子结点。

B+树的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。
卫星数据：索引元素所指向的数据记录。B-树中每个节点都包含卫星数据，而B+树中，只有叶子节点包含。

B+树的插入操作

在B+树中插入关键字时，需要注意以下几点：

• 插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
• 由于 B+树中各结点中存储的关键字的个数有明确的范围，做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行“分裂”；

B+树中做插入关键字的操作，有以下 3 种情况：

1. 若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入结束；

   在图1中插入关键字13，其结果如下图2所示

   

2. 若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，一个结点包含⌊M/2⌋，另一个结点包含⌈M/2⌉。同时，将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M，则插入操作完成。

   在图1中插入关键字95，其结果如下图3所示

   

3. 在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。

   在图1中插入关键字40，其结果如下图所示

   

如果插入的关键字比当前结点中的最大值还大，破坏了B+树中从根结点到当前结点的所有索引值，此时需要及时修正后，再做其他操作。
例如，在图 1 的 B+树种插入关键字 100，由于其值比 97 还大，插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。

B+树的删除操作

在 B+树中删除关键字时，有以下几种情况：

1. 找到存储有该关键字所在的结点时，由于该结点中关键字个数大于⌈M/2⌉，做删除操作不会破坏 B+树，则可以直接删除。

   在图 1 所示的 B+树中删除关键字 91，其结果如下图5所示

   

2. 当删除某结点中最大或者最小的关键字，就会涉及到更改其双亲结点一直到根结点中所有索引值的更改。

   在图 1 所示的 B+树中删除关键字 91，其结果如下图所示

   

3. 当删除该关键字，导致当前结点中关键字个数小于⌈M/2⌉，若其兄弟结点中含有多余的关键字，可以从兄弟结点中借关键字完成删除操作。

   在图 1 的 B+树中删除关键字 51，由于其兄弟结点中含有 3 个关键字，所以可以选择借一个关键字，同时修改双亲结点中的索引值，删除之后的 B+树如图7所示

   

4. 第 3 种情况中，如果其兄弟结点没有多余的关键字，则需要同其兄弟结点进行合并。

   在图 7 的 B+树种删除关键字 59，删除之后的 B+树如图8所示

   

5. 当进行合并时，可能会产生因合并使其双亲结点破坏 B+树的结构，需要依照以上规律处理其双亲结点。

   在图 6 的 B+树中删除关键字 63，当删除后该结点中只剩关键字 72，且其兄弟结点中只有 2 个关键字，无法实现借的操作，只能进行合并。但是合并后，合并后的效果图如图 9 所示

   

如图 9 所示，其双亲结点中只有一个关键字，而其兄弟结点中有 3 个关键字，所以可以通过借的操作，来满足 B+树的性质，最终的 B+树如图 10 所示：

总之，在 B+树中做删除关键字的操作，采取如下的步骤：

1. 删除该关键字，如果不破坏 B+树本身的性质，直接完成操作；
2. 如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；
3. 在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并。（注意这两种方式有时需要更改其父结点中的索引值。）

B+树相对于B-树的特点

• B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
• B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
• B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
• B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B*树

B^x树

UB树

2-3树

2-3-4树

(a.b)-树

Dancing tree

H树

堆

二叉堆

二项堆

斐波那契堆

左偏树

配对堆

斜堆

Van Emde Boas tree

字典树(TRIE)

后缀树

广义后缀树

基数树

三叉查找树

X-快速前缀树

Y-快速前缀树

AC自动机

二叉空间分割（BSP）树

四叉树

八叉树

k-d树

隐式k-d树

VP树

非二叉树

指数树

融合树

区间树

PQ树

Range tree

SPQR树

空间数据分割树

R树

R*树

R+树

X树

M树

线段树

可持久化线段树

希尔伯特树

优先R树

其他树

散列日历

散列树

Finger tree

顺序统计树

Metic tee

Cover tree

BK树

Doubly chained tee

iDistance

Link-cut tree

Log-structured merge-tree

树状数组

哈希树(Merkle tree)

哈夫曼树

https://blog.csdn.net/csdn_aiyang/article/details/84977814#%E7%AC%AC%E5%9B%9B%E8%8A%82%EF%BC%9A%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%A0%91%E2%80%94%E2%80%94%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91

树与森林

优秀资料

深入学习二叉树(一) 二叉树基础

常用数据结构——树

完美二叉树, 完全二叉树和完满二叉树

二叉树的遍历

二叉搜索树

自平衡二叉查找树

详解 AVL 树（基础篇）

AVL树的旋转图解和简单实现