简单学习数据结构

2021-09-23

Java

0 0

数据结构简介

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。

常见的数据结构可分为[线性数据结构]和[非线性数据结构]，线性数据结构：[数组]、[链表]、[栈]、[队列]；非线性数据结构：[树]、[图]、[散列表]、[堆]。

数组

数组是将相同类型的元素存储与连续内存空间的数据结构，其长度不可变。

// 初始化一个长度为5的数组arr
int[] arr = new int[5];
// 元素赋值
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;

或者可以使用直接赋值的初始化方法

int[] arr = {1,2,3,4,5};

可变数组

[可变数组]是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。

// 初始化可变数组
List<Integer> arr = new ArrayList<>();
// 向尾部添加元素
arr.add(1);
arr.add(2);
arr.add(3);
arr.add(4);
arr.add(5);

链表

[链表]是以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：[值 val]、[后继节点引用 next]。

class ListNode {
    int val;		// 节点值
    ListNode next;	// 后继节点引用
    ListNode (int x) { val = x; }
}

建立链表需要实例化每个节点，并构建各节点的引用指向。

// 实例化节点
ListNode n1 = new ListNode(4); //节点head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);

//构建引用指向
n1.next = n2;
n2.next = n3;

栈

[栈]是一种具有[先入后出]特点的抽象数据结构，可使用数组或链表实现。

Stack<Integer> stack = new Stack<>();

通过常用操作 [入栈 push()] , [出栈 pop()] ，展示了栈的先入后出特性。

stack.push(1); // 元素 1 入栈
stack.push(2); // 元素 2 入栈
stack.pop();   // 出栈 -> 元素 2
stack.pop();   // 出栈 -> 元素 1

注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack，而一般将LinkedList作为栈来使用。

LinkedList<Integer> stack = new LinkedList<>();

stack.addLast(1);   // 元素 1 入栈
stack.addLast(2);   // 元素 2 入栈
stack.removeLast(); // 出栈 -> 元素 2
stack.removeLast(); // 出栈 -> 元素 1

队列

队列是一种具有 [先入先出] 特点的抽象数据结构，可使用链表实现。

Queue<Integer> queue = new LinkedList<>();

通过常用操作 [入队 push()] ，[出队 pop()] ，展示了队列的先入先出特性。

queue.offer(1); // 元素 1 入队
queue.offer(2); // 元素 2 入队
queue.poll();   // 出队 -> 元素 1
queue.poll();   // 出队 -> 元素 2

树

树是一种非线性数据结构，根据子节点数量可分为 [二叉树] 和 [多叉树] ，最顶层的节点称为 [根节点 root] 。以二叉树为例，每个节点包含三个成员变量：[值 val]、 [左子节点 left] 、[右子节点 right] 。

二叉树

二叉树的每个结点至多只有两颗子树（不存在大于2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2 ^i-1个结点。深度为K的二叉树至多有2 _k-1个结点；对任何一颗二叉树T，如果其终端结点树为n₀,度为2的的结点数为n ₂,则n ₀=n ₂+1。

示例：

满二叉树和完全二叉树

满二叉树：除最后一层无任何结点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点之外的所有节点均有两个子结点。结点数达到最大值，所有叶子结点必须在同一层上。

性质：

一棵树深度为h，最大层数为k，深度与最大层数相同，k=h；
叶子树为2^h;
第k层的结点数是：2^k-1;
总结点数是：2^k-1，且总结点数一定是奇数。

完全二叉树：若设二叉树的深度为h，除第h层外，其他各层（1～（h-1）层）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

注：完全二叉树是效率很高的数据结果，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

二叉树的性质

在非空二叉树中，第i层的结点总数不超过2^i-1，i>=1;
深度为n的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
对于任意一颗二叉树，如果其叶子结点数为N₀，而度数为2的结点总数为N₂，则N₀=N₂+1;
具有n个结点的完全二叉树的深度为log₂(n+1);
有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号
如果I>1，则其父结点的编号为1/2；
如果2I<=N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子；
如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N，则无右儿子。
给定N个结点，能构成h(N)中不同的二叉树，其中h(N)为卡特兰树的第N项，h(n)=C(2*n,n)/(n+1)。
设有i个结点，I为所有支点的道路长度总和，J为叶的道路长度总和J=I+2^{i^。}

二叉查找树

定义：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一颗空树，或者是具有下列性质的二叉树

若左子树不空，则左子树所有结点的值均小于它的根结点的值；
若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；
没有键值相等的结点。

性质：对二叉查找树进行中序遍历，即可得到有序的数列。

时间复杂度：它和二分查找一样，插入和查找的时间复杂度均为o(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候。树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

二叉查找树的高度决定了二叉查找树的查找效率。

插入过程：

若当前的二叉查找树为空，则插入的元素为根结点；
若插入的元素值小于根结点值，则将元素插入到左子树中；
若插入的元素值不小于根结点值，则将元素插入到右子树中。

三种删除的情况处理：

p为叶子结点，直接删除该结点，在修改其父结点的指针（注意分是根结点和不是根结点），如图a；
p为单支结点（即只有左子树或右子树）。让p的子树与p的父亲结点相连，删除p即可（注意分是根结点和不是根结点），如图b；
p的左子树和右子树均不空，找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲结点成为y的右子树的父亲结点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以直接删除x，并让x的父亲结点成为y的左子树的父亲结点，如果c。

二叉树实现相关源码

插入操作

struct node
{
    int val;
    pnode lchild;
    pnode rchild;
};

pnode BT = NULL;


//递归方法插入节点 
pnode insert(pnode root, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(root == NULL){
        root = p;  
    }  
    else if(x < root->val){
        root->lchild = insert(root->lchild, x);  
    }
    else{
        root->rchild = insert(root->rchild, x);  
    }
    return root;
}

//非递归方法插入节点 
void insert_BST(pnode q, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(q == NULL){
        BT = p;
        return ;  
    }  
    while(q->lchild != p && q->rchild != p){
        if(x < q->val){
            if(q->lchild){
                q = q->lchild;  
            }  
            else{
                q->lchild = p;
            }  
        }  
        else{
            if(q->rchild){
                q = q->rchild;  
            }  
            else{
                q->rchild = p;  
            }
        }
    }
    return;
}

删除操作

<P>
<PRE>bool delete_BST(pnode p, int x) //返回一个标志，表示是否找到被删元素 
{
    bool find = false;
    pnode q;
    p = BT;
    while(p && !find){  //寻找被删元素 
        if(x == p->val){  //找到被删元素 
            find = true;  
        }  
        else if(x < p->val){ //沿左子树找 
            q = p;
            p = p->lchild;  
        }
        else{   //沿右子树找 
            q = p;
            p = p->rchild;  
        }
    }
    if(p == NULL){   //没找到 
        cout << "没有找到" << x << endl;  
    }
  
    if(p->lchild == NULL && p->rchild == NULL){  //p为叶子节点 
        if(p == BT){  //p为根节点 
            BT = NULL;  
        }
        else if(q->lchild == p){   
            q->lchild = NULL;
        }  
        else{
            q->rchild = NULL;  
        }
        free(p);  //释放节点p 
    }
    else if(p->lchild == NULL || p->rchild == NULL){ //p为单支子树 
        if(p == BT){  //p为根节点 
            if(p->lchild == NULL){
                BT = p->rchild;  
            }  
            else{
                BT = p->lchild;  
            }
        }  
        else{
            if(q->lchild == p && p->lchild){ //p是q的左子树且p有左子树 
                q->lchild = p->lchild;    //将p的左子树链接到q的左指针上 
            }  
            else if(q->lchild == p && p->rchild){
                q->lchild = p->rchild;  
            }
            else if(q->rchild == p && p->lchild){
                q->rchild = p->lchild;  
            }
            else{
                q->rchild = p->rchild;
            }
        }
        free(p);
    }
    else{ //p的左右子树均不为空 
        pnode t = p;
        pnode s = p->lchild;  //从p的左子节点开始 
        while(s->rchild){  //找到p的前驱，即p左子树中值最大的节点 
            t = s;   
            s = s->rchild;  
        }
        p->val = s->val;   //把节点s的值赋给p 
        if(t == p){
            p->lchild = s->lchild;  
        }  
        else{
            t->rchild = s->lchild;  
        }
        free(s); 
    }
    return find;
}

查找操作

pnode search_BST(pnode p, int x)
{
    bool solve = false;
    while(p && !solve){
        if(x == p->val){
            solve = true;  
        }  
        else if(x < p->val){
            p = p->lchild;  
        }
        else{
            p = p->rchild;  
        }
    }
    if(p == NULL){
        cout << "没有找到" << x << endl;  
    } 
    return p;
}

平衡二叉树

对于一般的二叉搜索树（Binart Search Tree），其期望高度（即为一颗平衡树时）为log₂n,其各操作的时间复杂度O(log_{2n)同时也由此决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或队列，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除结点的后继代替它本身，这样就回造成总是右边的结点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性收到破坏，提高它的操作的时间复杂度。于是就有了平衡二叉树。}

定义：平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质，它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好的维持在O(log₂n)，大大降低了操作的时间复杂度。

最小二叉平衡树的结点公式：

F(n)=F(n-1)+F(n-2)+1

这个类似于一个递归的数列，可以参考Fibonacci数列，i时根结点，F(n-1)是左子树的结点数量，F(n-2)是右子树的结点数量。

平衡查找树之AVL树

定义：AVL树是最先发明的平衡二叉查找树，在AVL中任何结点的两个儿子子树的高度最大差别为1，所以它被成为高度平衡树，n个结点的AVL树最大深度约1.44log₂n。插入、查找和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题。把插入、查找和删除的时间复杂度最好情况和最坏情况都维持在了O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

AVL树的自平衡操作—旋转

ACL树最关键也是最难的一步操作就是旋转。旋转主要是为了实现AVL树在实施了插入和删除操作以后，树重新回到平衡的方法。下面我们重点研究一下AVL树的旋转。

对于一个平衡的结点，由于任意结点最多有两个儿子，因此高度不平衡时，此结点的两棵树的高度差2，容易看出，这种不平衡出现在下面四种情况。

6结点的左子树3结点高度比右子树7结点大2，左子树3结点的左子树1结点高度大于右子树4结点，这种情况成为左左。
6结点的左子树2结点高度比右子树7结点大2，左子树2结点的左子树1结点高度小于右子树4结点，这种情况成为左右。
2结点的左子树1结点高度比右子树5结点小2，右子树5结点的左子树3结点高度大于右子树6结点，这种情况成为右左。
2结点的左子树1结点高度比右子树4结点小2，右子树4结点的左子树3结点高度小于右子树6结点，这种情况成为右右。

从图2可以看出，1和4两种情况是对成的，这两种情况的旋转算法也是一致的，只需要经过一次旋转就可以到达目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两种算法，我们称之为双旋转。

单旋转

单旋转是针对于左左和右右这两种情况的解决方法，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，结点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

为使树恢复平衡，我们把k2变成这棵树的根结点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这种既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一颗AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这棵子树高度没有变化，所以通往根结点的路径就不需要在继续旋转了。

双旋转

对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，结点k3不满足平衡特性，因此它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

为使树恢复平衡，我们需要进行两部。第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步在进行一次左左旋转，最后得到了一颗以k2为根的平衡二叉树

AVL树实现源码

//AVL树节点信息
template<class T>
class TreeNode
{
    public:
        TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}
        T data;//值
        int hgt;//高度
        unsigned int freq;//频率
        TreeNode* lson;//指向左儿子的地址
        TreeNode* rson;//指向右儿子的地址
};
//AVL树类的属性和方法声明
template<class T>
class AVLTree
{
    private:
        TreeNode<T>* root;//根节点
        void insertpri(TreeNode<T>* &node,T x);//插入
        TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找
        void insubtree(TreeNode<T>* node);//中序遍历
        void Deletepri(TreeNode<T>* &node,T x);//删除
        int height(TreeNode<T>* node);//求树的高度
        void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转
        void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转
        void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转
        void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转
        int Max(int cmpa,int cmpb);//求最大值

    public:
        AVLTree():root(NULL){}
        void insert(T x);//插入接口
        TreeNode<T>* find(T x);//查找接口
        void Delete(T x);//删除接口
        void traversal();//遍历接口

};
//计算节点的高度
template<class T>
int AVLTree<T>::height(TreeNode<T>* node)
{
    if(node!=NULL)
        return node->hgt;
    return -1;
}
//求最大值
template<class T>
int AVLTree<T>::Max(int cmpa,int cmpb)
{
    return cmpa>cmpb?cmpa:cmpb;
}
//左左情况下的旋转
template<class T>
void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2)
{
    TreeNode<T>* k1;
    k1=k2->lson;
    k2->lson=k1->rson;
    k1->rson=k2;

    k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
    k1->hgt=Max(height(k1->lson),k2->hgt)+1;
}
//右右情况下的旋转
template<class T>
void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2)
{
    TreeNode<T>* k1;
    k1=k2->rson;
    k2->rson=k1->lson;
    k1->lson=k2;

    k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
    k1->hgt=Max(height(k1->rson),k2->hgt)+1;
}
//左右情况的旋转
template<class T>
void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3)
{
    SingRotateRight(k3->lson);
    SingRotateLeft(k3);
}
//右左情况的旋转
template<class T>
void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3)
{
    SingRotateLeft(k3->rson);
    SingRotateRight(k3);
}
//插入
template<class T>
void AVLTree<T>::insertpri(TreeNode<T>* &node,T x)
{
    if(node==NULL)//如果节点为空,就在此节点处加入x信息
    {
        node=new TreeNode<T>();
        node->data=x;
        return;
    }
    if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x
    {
        insertpri(node->lson,x);
        if(2==height(node->lson)-height(node->rson))
            if(x<node->lson->data)
                SingRotateLeft(node);
            else
                DoubleRotateLR(node);
    }
    else if(node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x
    {
        insertpri(node->rson,x);
        if(2==height(node->rson)-height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转
            if(x>node->rson->data)
                SingRotateRight(node);
            else
                DoubleRotateRL(node);
    }
    else ++(node->freq);//如果相等,就把频率加1
    node->hgt=Max(height(node->lson),height(node->rson));
}
//插入接口
template<class T>
void AVLTree<T>::insert(T x)
{
    insertpri(root,x);
}
//查找
template<class T>
TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x)
{
    if(node==NULL)//如果节点为空说明没找到,返回NULL
    {
        return NULL;
    }
    if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中查找x
    {
        return findpri(node->lson,x);
    }
    else if(node->data<x)//如果x大于节点的值,就继续在节点的左子树中查找x
    {
        return findpri(node->rson,x);
    }
    else return node;//如果相等,就找到了此节点
}
//查找接口
template<class T>
TreeNode<T>* AVLTree<T>::find(T x)
{
    return findpri(root,x);
}
//删除
template<class T>
void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x)
{
    if(node==NULL) return ;//没有找到值是x的节点
    if(x < node->data)
    {
         Deletepri(node->lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x
         if(2==height(node->rson)-height(node->lson))
            if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )
                DoubleRotateRL(node);
            else
                SingRotateRight(node);
    }

    else if(x > node->data)
    {
         Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x
         if(2==height(node->lson)-height(node->rson))
            if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
                DoubleRotateLR(node);
            else
                SingRotateLeft(node);
    }

    else//如果相等,此节点就是要删除的节点
    {
        if(node->lson&&node->rson)//此节点有两个儿子
        {
            TreeNode<T>* temp=node->rson;//temp指向节点的右儿子
            while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点
            //把右子树中最小节点的值赋值给本节点
            node->data=temp->data;
            node->freq=temp->freq;
            Deletepri(node->rson,temp->data);//删除右子树中最小值的节点
            if(2==height(node->lson)-height(node->rson))
            {
                if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
                    DoubleRotateLR(node);
                else
                    SingRotateLeft(node);
            }
        }
        else//此节点有1个或0个儿子
        {
            TreeNode<T>* temp=node;
            if(node->lson==NULL)//有右儿子或者没有儿子
            node=node->rson;
            else if(node->rson==NULL)//有左儿子
            node=node->lson;
            delete(temp);
            temp=NULL;
        }
    }
    if(node==NULL) return;
    node->hgt=Max(height(node->lson),height(node->rson))+1;
    return;
}
//删除接口
template<class T>
void AVLTree<T>::Delete(T x)
{
    Deletepri(root,x);
}
//中序遍历函数
template<class T>
void AVLTree<T>::insubtree(TreeNode<T>* node)
{
    if(node==NULL) return;
    insubtree(node->lson);//先遍历左子树
    cout<<node->data<<" ";//输出根节点
    insubtree(node->rson);//再遍历右子树
}
//中序遍历接口
template<class T>
void AVLTree<T>::traversal()
{
    insubtree(root);
}

平衡二叉树之红黑树

定义：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，称之为“对称二叉B树”。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(logn)的时间内做查找，插入和删除，这里的n是树中元素的数目。

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值。

性质：红黑树是每个结点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的恶额外要求

结点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL结点）。
每个红色结点必须有两个黑色的子结点。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的，因为操作比如插入、删除和查找某个值的最快情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。，

红黑树的自平衡操作

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量（O(logn)）的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持O(logn)次。

我们首先以二叉查找树的方法增加结点并标记它为红色。如果设置为黑色，就会导致根到叶子的路径上有一条路上多一个格外的黑结点，这个是很难调整的（违背性质5）。但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近结点的颜色。同人类的家族树中一样，我们将使用术语叔父结点来指一个结点的父结点的兄弟结点，注意：

性质1和性质3总是保持着
性质4只在增加红色结点、重绘黑色结点为红色，或做旋转时受到威胁。
性质5只在增加黑色结点、重绘红色结点为黑色，或做旋转时受到威胁。

插入操作：

假设，将要插入的结点标为N，N的父结点标为P，N的祖父结点标为G，N的叔父结点标为U，在途中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含的。

情形1：该树为空树，直接插入根结点的位置，违反性质1，把结点颜色由红改为黑即可。
情形2：插入结点N的父结点P为黑色，不违反任何性质，无需做任何修改。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新结点N有两个黑色叶子子结点；但由于新结点N是红色，通过它的每个字结点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色结点，所以依然满足这个性质。
注：情形1很简单，情形2中P为黑色，一切安然无事，但P为红就不一样了，下边是P为红的各种情况，也是真正难懂的地方。
情形3：如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行上述情形的整个过程（把G当成是新加入的节点进行各种情形的检查）。比如，G为根节点，那我们就直接将G变为黑色（情形1）；如果G不是根节点，而它的父节点为黑色，那符合所有的性质，直接插入即可（情形2）；如果G不是根节点，而它的父节点为红色，则递归上述过程（情形3）。
情形4：父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色(如果P和G都是红色就违反了性质4，所以G必须是黑色)。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。
情形5：父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形4 处理以前的父节点P以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5仍有效。

注：插入实际上是原地算法，因为上述所有调用都是用了尾部递归。

删除操作：

**如果需要删除的结点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的结点的问题。**对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

我们只需要讨论删除只有一个儿子的节点 (如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候 ，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N (在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为S 。在下面的示意图中，我们还是使用P 称呼N的父亲，S~L~ 称呼S的左儿子，S~R~ 称呼S的右儿子。

红黑树实现源码

<PRE>#define BLACK 1
#define RED 0

using namespace std;

class bst {
private:

    struct Node {
        int value;
        bool color;
        Node *leftTree, *rightTree, *parent;

        Node() {
            color = RED;
            leftTree = NULL;
            rightTree = NULL;
            parent = NULL;
            value = 0;
        }

        Node* grandparent() {
            if (parent == NULL) {
                return NULL;
            }
            return parent->parent;
        }

        Node* uncle() {
            if (grandparent() == NULL) {
                return NULL;
            }
            if (parent == grandparent()->rightTree)
                return grandparent()->leftTree;
            else
                return grandparent()->rightTree;
        }

        Node* sibling() {
            if (parent->leftTree == this)
                return parent->rightTree;
            else
                return parent->leftTree;
        }
    };

    void rotate_right(Node *p) {
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->rightTree;

        fa->leftTree = y;

        if (y != NIL)
            y->parent = fa;
        p->rightTree = fa;
        fa->parent = p;

        if (root == fa)
            root = p;
        p->parent = gp;

        if (gp != NULL) {
            if (gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }

    }

    void rotate_left(Node *p) {
        if (p->parent == NULL) {
            root = p;
            return;
        }
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->leftTree;

        fa->rightTree = y;

        if (y != NIL)
            y->parent = fa;
        p->leftTree = fa;
        fa->parent = p;

        if (root == fa)
            root = p;
        p->parent = gp;

        if (gp != NULL) {
            if (gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }
    }

    void inorder(Node *p) {
        if (p == NIL)
            return;

        if (p->leftTree)
            inorder(p->leftTree);

        cout << p->value << " ";
      
        if (p->rightTree)
            inorder(p->rightTree);
    }

    string outputColor(bool color) {
        return color ? "BLACK" : "RED";
    }

    Node* getSmallestChild(Node *p) {
        if (p->leftTree == NIL)
            return p;
        return getSmallestChild(p->leftTree);
    }

    bool delete_child(Node *p, int data) {
        if (p->value > data) {
            if (p->leftTree == NIL) {
                return false;
            }
            return delete_child(p->leftTree, data);
        } else if (p->value < data) {
            if (p->rightTree == NIL) {
                return false;
            }
            return delete_child(p->rightTree, data);
        } else if (p->value == data) {
            if (p->rightTree == NIL) {
                delete_one_child(p);
                return true;
            }
            Node *smallest = getSmallestChild(p->rightTree);
            swap(p->value, smallest->value);
            delete_one_child(smallest);

            return true;
        }
    }

    void delete_one_child(Node *p) {
        Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
        if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {
            p = NULL;
            root = p;
            return;
        }
  
        if (p->parent == NULL) {
            delete  p;
            child->parent = NULL;
            root = child;
            root->color = BLACK;
            return;
        }
  
        if (p->parent->leftTree == p) {
            p->parent->leftTree = child;
        } else {
            p->parent->rightTree = child;
        }
        child->parent = p->parent;

        if (p->color == BLACK) {
            if (child->color == RED) {
                child->color = BLACK;
            } else
                delete_case(child);
        }

        delete p;
    }

    void delete_case(Node *p) {
        if (p->parent == NULL) {
            p->color = BLACK;
            return;
        }
        if (p->sibling()->color == RED) {
            p->parent->color = RED;
            p->sibling()->color = BLACK;
            if (p == p->parent->leftTree)
                rotate_left(p->sibling());
            else
                rotate_right(p->sibling());
        }
        if (p->parent->color == BLACK && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            delete_case(p->parent);
        } else if (p->parent->color == RED && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            p->parent->color = BLACK;
        } else {
            if (p->sibling()->color == BLACK) {
                if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
                        && p->sibling()->rightTree->color == BLACK) {
                    p->sibling()->color = RED;
                    p->sibling()->leftTree->color = BLACK;
                    rotate_right(p->sibling()->leftTree);
                } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
                        && p->sibling()->rightTree->color == RED) {
                    p->sibling()->color = RED;
                    p->sibling()->rightTree->color = BLACK;
                    rotate_left(p->sibling()->rightTree);
                }
            }
            p->sibling()->color = p->parent->color;
            p->parent->color = BLACK;
            if (p == p->parent->leftTree) {
                p->sibling()->rightTree->color = BLACK;
                rotate_left(p->sibling());
            } else {
                p->sibling()->leftTree->color = BLACK;
                rotate_right(p->sibling());
            }
        }
    }

    void insert(Node *p, int data) {
        if (p->value >= data) {
            if (p->leftTree != NIL)
                insert(p->leftTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->leftTree = tmp;
                insert_case(tmp);
            }
        } else {
            if (p->rightTree != NIL)
                insert(p->rightTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->rightTree = tmp;
                insert_case(tmp);
            }
        }
    }

    void insert_case(Node *p) {
        if (p->parent == NULL) {
            root = p;
            p->color = BLACK;
            return;
        }
        if (p->parent->color == RED) {
            if (p->uncle()->color == RED) {
                p->parent->color = p->uncle()->color = BLACK;
                p->grandparent()->color = RED;
                insert_case(p->grandparent());
            } else {
                if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
                    rotate_left(p);
                    rotate_right(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
                    rotate_right(p);
                    rotate_left(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_right(p->parent);
                } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_left(p->parent);
                }
            }
        }
    }

    void DeleteTree(Node *p) {
        if (!p || p == NIL) {
            return;
        }
        DeleteTree(p->leftTree);
        DeleteTree(p->rightTree);
        delete p;
    }
public:

    bst() {
        NIL = new Node();
        NIL->color = BLACK;
        root = NULL;
    }

    ~bst() {
        if (root)
            DeleteTree(root);
        delete NIL;
    }

    void inorder() {
        if (root == NULL)
            return;
        inorder(root);
        cout << endl;
    }

    void insert(int x) {
        if (root == NULL) {
            root = new Node();
            root->color = BLACK;
            root->leftTree = root->rightTree = NIL;
            root->value = x;
        } else {
            insert(root, x);
        }
    }

    bool delete_value(int data) {
        return delete_child(root, data);
    }
private:
    Node *root, *NIL;
};

B树

B树也是一种用于查找的平衡树，但是它又不是二叉树。

B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循环存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个字结点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1-Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根结点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

B树作为一种多路搜索树（并不是二叉的）：

定义任意非叶子结点最多只有M个儿子；且M>2；
根结点的儿子树为[2,M]；
除根结点以外的非叶子结点的儿子树为[M/2,M]；
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少两个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：k[1],k[2],...,k[M-1];且k[i]<k[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；

B+树

B+树是B树的变体，也是一种多路搜索树

其定义基本与B-树相同，除了：
非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；

B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+树的性质

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中；
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
更适合文件索引系统。

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

标题：简单学习数据结构
作者：zzzzchen
地址：https://www.dczzs.com/articles/2021/09/06/1630908314829.html