七.动态顺序统计树
? ? ? ? 借助红黑树数据结构的扩张，每个节点都存储自己含有的字节点的个数，即size，nil节点的size为0。
? ? ? ? 其中size = left.size + right.size +1，利用节点的该信息，可以完成和前面三、四中递归查找的工作，一个元素在以该元素为根的子树中的Rank就是left.size + 1。这是本算法的关键所在。
? ? ? ? 如果查询第K个元素，则和root比较，计算root的Rank，如果K<Rank，说明在该树的左子树中存在第K个元素；如果K>Rank,则在右子树中查找第K-Rank个元素；如果相等则返回即可。这和前面利用快速排序主元划分思想的求解过程是十分类似的，只是该算法无需查找主元，只需要动态维护一棵扩张了的红黑树，维护该树的代价，和在该树中进行的操作（Insert、Delete、Find）等操作都和高度直接相关，即上述所有操作的时间复杂度均为O(lgn)，是不是快到超乎你的想象呢？
? ? ? ? 不过红黑树性质虽好，但难在维护，在插入和删除过程中都需要动态维护该棵红黑树，红黑树的插入和删除过程都存在一个操作节点和着色两部分，第一部分沿着路径增加或减少节点的size，第二部分操作则涉及到旋转，在旋转中可以使用线性时间则可以维护该size。
1.Insert过程中的维护
第一阶段： 插入的节点从root向下寻找空的合适的位置，经过该路径的节点的size均+1；
第二阶段：插入的节点在着色的时候涉及到左旋右旋，如果右旋，则直接x = y.size;(旋转前）? ? ? ????????????????y.size = y.left + y.right + 1;( 旋转后）
比较简单吧！只涉及到两个过程。删除就要复杂一点了。
?2.?Delete过程中的维护
第一阶段：
????????从根到删除的节点，沿着该路径上的节点size均-1，同时，如果拼接的节点不是删除节点的直接后继，则要从拼接的节点到x路径上size-1，因为从x前方抽走了y，沿着该抽走路径的节点size-1，然后将y拼接上原来要删除node的位置，将其size置为node->size-1，完成维护工作。
????????是不是比较复杂？
第二阶段：
????????插入的节点在着色的时候涉及到左旋右旋，如果右旋，则直接?x = y.size;(旋转前）? ? ?
????????y.size = y.left + y.right + 1;( 旋转后）
? ? ? ? 聪明的你，一定发现了插入和删除的第二阶段的相似性。算法的复杂点在于删除操作对节点路径的影响不止一条，涉及到元素跨路径的拼接。
? ? ? ? 原文中的部分内容如下：?
? ? ? ? 代码如下：分为头文件Order_Statistic_Tree.h 和源文件Order_Statistic_Tree.c 以及main.c函数用于测试和演示。
? ? ? ? 1.Order_Statistic_Tree.h
//
// Created by long on 2021/11/22.
//
#ifndef ORDER_STATISTIC_TREE_H
#define ORDER_STATISTIC_TREE_H
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/*
* 基于红黑树的扩张
* 对每个节点添加size作为维护内容
* 通过size可以很方便求出RANK
* 在其上进行按顺序查找、求出给定元素的RANK、求给定节点的RANK等
* 在红黑树的插入删除的两个阶段维护各个节点size的大小
* 借助红黑树的优质特性可以使上述操作在Log(n)的时间复杂度下完成
* 相较于线性的查找便捷许多
*/
typedef _Bool bool;
typedef int Item;
//定义枚举常量表示红黑
enum Color{
Red,Black
};
typedef struct RBTree{
int size;//节点所含的节点数 size.left+size.right+1
Item data;
enum Color color;//表示红黑的颜色标记
struct RBTree*P,*Lchild,*Rchild;
}RBTree,*RBTreePointer;
//Search the node of item
RBTreePointer Search(RBTreePointer Tree, Item data);
//Insert the node into the binary tree
RBTreePointer Insert(RBTreePointer Tree, Item data);
RBTreePointer Delete(RBTreePointer Tree,Item data);//删除节点
//Fixup the color of the node which insert
RBTreePointer RB_Insert_Fixup(RBTreePointer Tree,RBTreePointer Node);
RBTreePointer RB_Delete_Fixup(RBTreePointer Tree,RBTreePointer Node);
//如果不使用带返回值的函数 对root的操作是很复杂的
//左旋
RBTreePointer LeftRotate(RBTreePointer Tree,RBTreePointer Node);
//右旋
RBTreePointer RightRotate(RBTreePointer Tree,RBTreePointer Node);
//The help function of delete
void TransPlant(RBTreePointer *Tree, RBTreePointer u, RBTreePointer v);
//Delete the Item from RBTree
bool RBDelete(RBTreePointer *Tree,Item data);
//The help function
RBTreePointer Minimize(RBTreePointer Tree,RBTreePointer node);
//查找第i大的元素
RBTreePointer OS_SELECT(RBTreePointer Tree,int i);
//辅助函数（核心函数
RBTreePointer OS_SELECT_Help(RBTreePointer Tree,int i);
//查找Node在Tree中的位置
int OS_RANK(RBTreePointer Tree,RBTreePointer Node);
int OS_RANK_ELEMENT(RBTreePointer Tree,int data);
RBTreePointer Successor(RBTreePointer Tree, Item data);
//Traverse the binary search tree
void InorderTraverse(RBTreePointer Tree,RBTreePointer nil);
#endif //ORDER_STATISTIC_TREE_H
????????2.Order_Statistic_Tree.c
//
// Created by 周龙 on 2021/11/22.
//
#include "Order_Statistic_Tree.h"
RBTreePointer Insert(RBTreePointer Tree, Item data) {
//节点不存在
if (!Tree) {
Tree = (RBTreePointer) malloc(sizeof(RBTree));//Allocate the memory
Tree->P = Tree->Lchild = Tree->Rchild = (RBTreePointer) malloc(sizeof(RBTree));//The parent of root is null
Tree->data = data;
Tree->size=1;
Tree->color=Black;
Tree->P->color=Black;//Set the color of nil black
Tree->P->size=0;//nil不计节点数
return Tree;
}
//在查找插入位置的时候沿着该路径使size++
else {
RBTreePointer Reserve = Tree;//Reserve the node of the tree
//Find the site to insert
RBTreePointer nil=Reserve->P;//The node of nil
RBTreePointer Pre = Tree;//To record the predecessor of node
while (Tree!=nil) {
Pre = Tree;//记录前驱 用于更新
Tree->size++;
if (data == Tree->data) {
//存在相同的内容无需插入 这个判断对size来说有点bug 不支持重复元素
return Reserve;
}
if (data > Tree->data) {
//大于则在右边
Tree = Tree->Rchild;
} else {
//小于则在左边
Tree = Tree->Lchild;
}
}
//找到待插入的空节点 Pre不可能不存在
RBTreePointer New_node = (RBTreePointer) malloc(sizeof(RBTree));
New_node->data = data;
New_node->Rchild = New_node->Lchild = nil;
New_node->color=Red;//The new insert node must be red
New_node->P = Pre;
New_node->size=1;
//在右侧插入
if (data > Pre->data)
Pre->Rchild = New_node;
//在左侧插入
else
Pre->Lchild = New_node;
Tree= RB_Insert_Fixup(Reserve,New_node);//在着色时调整fixup对size的操作
return Tree;//Fixup the color of red black tree
}
}
//6种情况 3种对称
RBTreePointer RB_Insert_Fixup(RBTreePointer Tree,RBTreePointer Node){
RBTreePointer Reserve=Tree;
RBTreePointer Nil=Tree->P;
//The conflict of node
while(Node->P->color==Red){
//左侧
if(Node->P==Node->P->P->Lchild){
RBTreePointer Temp=Node->P->P->Rchild;
//The uncle of the node is red
if(Temp->color==Red){
Node->P->color=Black;
Temp->color=Black;
Node=Node->P->P;
}
else{
//判断是否需要左旋
if(Node==Node->P->Rchild){
Node=Node->P;
//此处的根节点不会发生旋转
LeftRotate(Tree,Node);//Node left rotate
}
//处理右旋 判断根节点是否需要参加右旋
//Node 为red 令node->p 为 black 保证不冲突 而后旋转 使节点node->p->p为中间节点
Node->P->color=Black;
Node->P->P->color=Red;
//为根节点
if(Node->P->P==Tree){
//修改根节点
RBTreePointer temp = RightRotate(Tree,Node->P->P);
Reserve=temp;
}
else{
RightRotate(Tree,Node->P->P);//Just right rotate
}
}
}
else{
RBTreePointer Temp=Node->P->P->Lchild;
//The uncle of the node is red
if(Temp->color==Red){
Node->P->color=Black;
Temp->color=Black;
Node=Node->P->P;
}
//右侧
else{
//判断是否需要右旋
if(Node==Node->P->Lchild){
Node=Node->P;
//此处的根节点不会发生旋转
RightRotate(Tree,Node);//Node left rotate
}
//处理左旋 判断根节点是否需要参加左旋
//Node 为red 令node->p 为 black 保证不冲突 而后旋转 使节点node->p->p为中间节点
Node->P->color=Black;
Node->P->P->color=Red;
RBTreePointer temp=(RBTreePointer)malloc(sizeof(RBTree));
//为根节点
if(Node->P->P==Tree){
//修改根节点
temp = LeftRotate(Tree,Node->P->P);
Reserve=temp;
}
else{
LeftRotate(Tree,Node->P->P);//Just left rotate
}
}
}
//Fix the color of root
Reserve->color=Black;
Reserve->P=Nil;
Reserve->P->color=Black;
}
return Reserve;
}
//左旋
RBTreePointer LeftRotate(RBTreePointer Tree,RBTreePointer Node){
RBTreePointer nil = Tree->P;
RBTreePointer temp=Node->Rchild;
Node->Rchild=temp->Lchild;//连上child
if(temp->Lchild!=nil){
temp->Lchild->P=Node;//修改parent指针
}
//修改Node的亲节点
temp->P=Node->P;
//为ROOT
if(Node->P!=nil){
//左侧
if(Node->P->Lchild==Node){
Node->P->Lchild=temp;
}
//右侧
else{
Node->P->Rchild=temp;
}
}
//链接node和temp
temp->Lchild=Node;
Node->P=temp;
//同样的更新方式 维护size
temp->size=Node->size;
Node->size=Node->Rchild->size+1+Node->Lchild->size;
return temp;//返回旋转后的节点
}
//右旋
RBTreePointer RightRotate(RBTreePointer Tree,RBTreePointer Node){
RBTreePointer nil = Tree->P;
RBTreePointer temp=Node->Lchild;//新的root node被旋转至right
Node->Lchild=temp->Rchild;//连上child
//是否是nil节点
if(temp->Rchild!=nil){
temp->Rchild->P=Node;//修改parent指针
}
//修改Node的亲节点
//为ROOT
temp->P=Node->P;
if(Node->P!=nil){
//左侧
if(Node->P->Lchild==Node){
Node->P->Lchild=temp;
}
//右侧
else{
Node->P->Rchild=temp;
}
}
//链接node和temp
temp->Rchild=Node;
Node->P=temp;
//更新size
temp->size=Node->size;
Node->size=Node->Rchild->size+1+Node->Lchild->size;
return temp;//返回旋转后的节点
}
//Traverse the binary search tree
void InorderTraverse(RBTreePointer Tree,RBTreePointer nil) {
//Traverse the data of tree
if (Tree == nil ) {
return;
} else {
//The Inorder Traverse
InorderTraverse(Tree->Lchild,nil);
printf("Data=%d Color=%d Size=%d\n", Tree->data,Tree->color,Tree->size);
InorderTraverse(Tree->Rchild,nil);
}
}
//修改删除的方式
bool RBDelete(RBTreePointer *Tree,Item data){
/*
* 沿用z的删除方式 使用y作为带插入的节点 而使用x作为新拼接上的节点
* y插入z并不会导致节点内容的丢失 节点内容的丢失在x点处
* 因而需要记录y源的颜色 如果为黑
* 则表明在x进行替代的过程中使黑色节点的个数减少了
*/
//使用指针传入的方式以便能修改指针
RBTreePointer *Restore=Tree;//直接保存二级指针的值
int flag;
RBTreePointer Temp=*Tree;
RBTreePointer nil=Temp->P;
//Find the node which data equal to data
while (Temp != nil) {
//沿着路径减少size的值
if (data == Temp->data) {
break;
}
Temp->size--;
if (Temp->data < data) {
Temp = Temp->Rchild;
} else {
Temp = Temp->Lchild;
}
}
if(Temp==nil){
printf("The node is not exists\n");
return 0;//The node is not exists
}
RBTreePointer z=Temp;
RBTreePointer y=z;
RBTreePointer x;
int y_original_color=y->color;//记录y的原始颜色
//开始delete
if (z->Lchild ==(*Tree)->P ) {
//connect the Rchild
x=z->Rchild;//记录拼接的位置
TransPlant(Restore, z, z->Rchild);
}
else if (z->Rchild == (*Tree)->P) {
//connect the Lchild
x=z->Lchild;//同上
TransPlant(Restore,x, x->Lchild);
}
else{
RBTreePointer pre = (*Tree)->P;
RBTreePointer node=z->Rchild;
while (node != (*Tree)->P) {
node->size--;
pre = node;
node = node->Lchild;//Minimize data is always in the left
}
y= pre;
y_original_color=y->color;//找到y的位置 即后继节点
x=y->Rchild;//即将拼接的节点
/*
* 这一部分是十分关键的！！！！！！
* 并不是多余的操作
* 本身x如果为nil那么p是随意指向的
* 那么如果在后面进行调整的时候是无法完成的
* 因而需要修改x的p的指向 令p就是指向的删除的节点
*/
x->P=y;
if (y!= z->Rchild) {
x->P=y;//??
TransPlant(Tree,y,x);//concat the node
y->Rchild = z->Rchild;
y->Rchild->P = y;
}
//The successor must in the right of the node
TransPlant(Restore,z,y);//拼接y到z的位置
y->color=z->color;//修改y的颜色
y->size=z->size-1;//修改z的节点大小
//处理z的左节点
y->Lchild=z->Lchild;
y->Lchild->P = y;
}
if(y_original_color==Black){
*Tree= RB_Delete_Fixup(*Tree,x);
}
return 1;
}
RBTreePointer RB_Delete_Fixup(RBTreePointer Tree,RBTreePointer x){
RBTreePointer Restore = Tree;
RBTreePointer w;
//为了分担这个黑色的节点
while(x!=Tree && x->color==Black){
//在左侧
if(x==x->P->Lchild){
w=x->P->Rchild;//sibling node
//为红则以w节点作为黑节点的消解节点
if(w->color==Red){
//旋转时一定要随时注意根节点的位置
w->color=Black;//消解黑色节点
x->P->color=Red;
//若为根节点
if(x==Tree)
//修改Tree的值然后用于返回
Tree= LeftRotate(Restore,x->P);
else
LeftRotate(Restore,x->P);
}
//节点颜色为黑色
else{
//两个都是黑色
if(w->Lchild->color==Black&&w->Rchild->color==Black){
w->color=Red;
x=x->P;//把Black向上推 直接结束循环 在循环体结束后为x的颜色赋值为Black
//不管剩下的红节点了吗
}
//右侧为Black
else {
//右侧
if (w->Rchild->color == Black) {
w->Lchild->color = Red;
w->color = Red;
//右旋w不会是根节点 则直接旋转就行
RightRotate(Restore, w);
w = x->P->Rchild;//重回原位置
}
//左侧
w->color=x->P->color;
x->P->color=Black;//旋转后不破坏prenode
w->Rchild->color=Black;//借助w的Rchild消解掉多余的黑色节点
//观察是否处理到了root
if(x->P==Tree){
Tree= LeftRotate(Restore,x->P);
}
else{
LeftRotate(Restore,x->P);
}
x=Tree;//x为根节点
}
}
}
//X在右侧
else{
// return Tree;
//在右侧
if(x==x->P->Rchild){
w=x->P->Lchild;//sibling node
//为红则以w节点作为黑节点的消解节点
if(w->color==Red){
//旋转时一定要随时注意根节点的位置
w->color=Black;//消解黑色节点
x->P->color=Red;
//若为根节点
if(x==Tree)
//修改Tree的值然后用于返回
Tree= RightRotate(Restore,x->P);
else
RightRotate(Restore,x->P);
}
//节点颜色为黑色
else{
//两个都是黑色
if(w->Lchild->color==Black&&w->Rchild->color==Black){
w->color=Red;
x=x->P;//把Black向上推 直接结束循环 在循环体结束后为x的颜色赋值为Black
//不管剩下的红节点了吗 在节点结束后抹去颜色
}
//右侧为Black
else {
//左侧
if (w->Lchild->color == Black) {
w->Rchild->color = Red;
w->color = Red;
//左旋w不会是根节点 则直接旋转就行
LeftRotate(Restore, w);
w = x->P->Lchild;//重回原位置
}
//左侧
w->color=x->P->color;
x->P->color=Black;//旋转后不破坏prenode
w->Lchild->color=Black;//借助w的Lchild消解掉多余的黑色节点
//观察是否处理到了root
if(x->P==Tree){
Tree= RightRotate(Restore,x->P);
}
else{
RightRotate(Restore,x->P);
}
x=Tree;//x为根节点
}
}
}
}
}
x->color=Black;
return Tree;
}
//Let v be u->parent->child
void TransPlant(RBTreePointer *Tree, RBTreePointer u, RBTreePointer v) {
//Reverse the root
if (u->P ==(*Tree)->P) {
*Tree = v;//The v is the root of BST
}
//The left child
else if (u == u->P->Lchild) {
u->P->Lchild = v;
} else {
u->P->Rchild = v;
}
//由于NULL代表一个nil节点 则无需判断 直接全指 为空也指
v->P = u->P;//尽管是nil 它的parent已然需要往前指 改动节点为v
}
RBTreePointer Minimize(RBTreePointer Tree,RBTreePointer node) {
RBTreePointer pre = Tree->P;
while (node != Tree->P) {
pre = node;
node = node->Lchild;//Minimize data is always in the left
}
return pre;
}
RBTreePointer Maximum(RBTreePointer Tree,RBTreePointer node) {
RBTreePointer pre = Tree->P;
while (node != Tree->P) {
pre = node;
node = node->Rchild;//Minimize data is always in the left
}
return pre;
}
//Visit the successor of the assign node from binary search tree
RBTreePointer Successor(RBTreePointer Tree, Item data) {
RBTreePointer Temp=Tree;
RBTreePointer KeyNode = Search(Temp, data);//Find the node which will delete
if (KeyNode == Temp->P) {
return Temp->P;
}
if (KeyNode->Rchild) {
return Minimize(Tree,KeyNode->Rchild);
} else {
//Find the pre data
RBTreePointer pre = KeyNode->P;
while (pre && pre->Rchild == KeyNode) {
KeyNode = KeyNode->P;
pre = KeyNode->P;
}
return pre;
//直到找到root或者node 如果是root表明没有节点为前驱 返回NULL
}
}
//Search the item from binary search tree
RBTreePointer Search(RBTreePointer Tree, Item data) {
RBTreePointer Temp=Tree;
//Find the node which data equal to data
while (Temp != Tree->P) {
if (data == Temp->data) {
return Temp;
} else if (Temp->data < data) {
Temp = Temp->Rchild;
} else {
Temp = Temp->Lchild;
}
}
return Tree->P;//If the search is fail
}
RBTreePointer OS_SELECT(RBTreePointer Tree,int i){
if(i>Tree->size){
printf("The rank is more than size of array\n");
return NULL;
}
else{
return OS_SELECT_Help(Tree,i);
}
}
RBTreePointer OS_SELECT_Help(RBTreePointer Tree,int i){
int r=Tree->Lchild->size+1;//Rank Of Root
if(r==i){
return Tree;
}
else if(r>i){
return OS_SELECT(Tree->Lchild,i);//Tree的Rank过大 则向左
}
else{
return OS_SELECT(Tree->Rchild,i-r);
}
}
//查找Node在Tree中的位置
int OS_RANK(RBTreePointer Tree,RBTreePointer Node){
if(Node==NULL){
return 0;
}
int r=Node->Lchild->size+1;
while(Node!=Tree){
//如果是Rchild 则表明P的Lchild以及P都是Node的前驱
if(Node->P->Rchild==Node){
r+=Node->P->Lchild->size+1;
}
Node=Node->P;
}
return r;
}
int OS_RANK_ELEMENT(RBTreePointer Tree,int data){
//向左加则向右减
int r=Tree->Lchild->size+1;
RBTreePointer Temp=Tree;
while(Temp!=Tree->P&&Temp->data!=data){
//如果大则向右
if(data>Temp->data){
Temp=Temp->Rchild;
r+=Temp->Lchild->size+1;
}
//向左
else{
Temp=Temp->Lchild;
r-=Temp->Rchild->size+1;
}
}
if(Temp==Tree->P){
return -1;//表示未查找到
}
return r;
}
????????3.main.c
#include "Order_Statistic_Tree.h"
int main(void) {
RBTreePointer Tree=NULL;
for(int i=0;i<10;i++){
Tree= Insert(Tree,i);
}
InorderTraverse(Tree,Tree->P);
printf("The rank i:\n");
RBTreePointer Res=OS_SELECT(Tree,9);
printf("按元素9的rank查找到元素：%d\n", OS_RANK(Tree,Res));
int res= OS_RANK_ELEMENT(Tree,1);
printf("元素1的位置为%d\n",res);
res= OS_RANK_ELEMENT(Tree,5);
printf("元素5的位置为%d\n",res);
return 0;
}
? ? ? ? ?运行main.c就可以了，输出内容是我自己的测试内容，大家可以随意更改，只是这红黑树确实过于庞大，但一旦写出来，效果非常好。
? ? ? ? 算法运行结果：
? ? ? ?恳请大家指正！?
????????