# 一、概念
### 1.動態順序統計
動態順序統計是指,在一個動態的無序的集合中,任意的順序統計量都可以在O(lgn)時間內確定。
### 2.基礎數組結構
紅黑樹,每個樹結點的域包括:key[x],color[x],left[x],right[x]
### 3.附加信息
size[x]:以結點x為根的子樹的內部結點(包括x)數,即子樹的大小。
如果定義哨兵nil,則size[nil[T]]為0
size[x] = size[left[x]] + size[right[x]] + 1
### 4.對信息的維護
(1)插入操作:
第一個階段,即從根開始,沿樹下降,將新結點插入為某個已有結點的孩子,這一階段的維護方法是對路徑上每個結點的size都+1,時間是O(lgn)
第二個階段,即沿樹上升,做一些顏色修改和旋轉以保持紅黑性質,例如LEFT-ROTATE(T, x),維護方法是size[y]<-size[x],size[x]<-size[left[x]] + size[right[x]] + 1,由于至多旋轉兩次,時間是O(1)
(2)刪除操作:
第一階段,即對查找樹進行操作,維護方法是對路徑上每個結點的size都-1,時間是O(lgn)
第二階段到多做三次旋轉,維護方式與上面相同,時間是O(1)
### 5.設計新的操作
OS-SELECT(x, i):找出順序統計樹T中的第i小關鍵字,時間為O(lgn)
OS-RANK(T, x):給定指向一順序統計樹T中結點x的指針,返回對T進行中序遍歷后得到 的線性序中x的位置,時間為O(lgn)
# 二、代碼
### 1.Os_Tree.h
~~~
#include <iostream>
using namespace std;
#define BLACK 0
#define RED 1
//順序統計量樹結點結構
struct node
{
/*紅黑樹的域*/
int key;
bool color;
node *p;
node *left;
node *right;
/*附加信息*/
int size;//以結點x為根的子樹的內部結點的個數,x->key=x->left->key+x->right->key+1
/*構造函數*/
node(node *init, int k):left(init),right(init),p(init),key(k),color(BLACK),size(1){}
};
//順序統計量樹結構
class Os_Tree
{
public:
node *root;
node *nil;//哨兵
/*構造函數*/
Os_Tree(){nil = new node(NULL, -1);root = nil;nil->size = 0;};
/*動態順序統計相關操作*/
node *Os_Select(node *x, int i);
int Os_Rank(node *x);
/*紅黑樹的相關操作*/
void Left_Rotate(node *x);//左旋
void Right_Rotate(node *x);//右旋
void Os_Insert_Fixup(node *z);//插入調整
void Os_Insert(node *z);//插入
void Os_Delete_Fixup(node *x);//刪除調整
node *Os_Delete(node *z);//刪除
void Print();//輸出
void Print(node *x);//輸出
node *Os_Search(node *x, int k);//在x的子樹中查找關鍵字為k的結點
node *Tree_Successor(node *x);//求后繼
node *Tree_Minimum(node *x);//求關鍵字最小的點
};
//左旋,令y = x->right, 左旋是以x和y之間的鏈為支軸進行旋轉
//涉及到的結點包括:x,y,y->left,令node={p,l,r},具體變化如下:
//x={x->p,x->left,y}變為{y,x->left,y->left}
//y={x,y->left,y->right}變為{x->p,x,y->right}
//y->left={y,y->left->left,y->left->right}變為{x,y->left->left,y->left->right}
void Os_Tree::Left_Rotate(node *x)
{
//令y = x->right
node *y = x->right;
//按照上面的方式修改三個結點的指針,注意修改指針的順序
x->right = y->left;
if(y->left != nil)
y->left->p = x;
y->p = x->p;
if(x->p == nil)//特殊情況:x是根結點
root = y;
else if(x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
//對附加信息的維護
y->size = x->size;
x->size = x->left->size + x->right->size + 1;
}
//右旋,令y = x->left, 左旋是以x和y之間的鏈為支軸進行旋轉
//旋轉過程與上文類似
void Os_Tree::Right_Rotate(node *x)
{
node *y = x->left;
x->left = y->right;
if(y->right != nil)
y->right->p = x;
y->p = x->p;
if(x->p == nil)
root = y;
else if(x == x->p->right)
x->p->right = y;
else
x->p->left = y;
y->right = x;
x->p = y;
//對附加信息的維護
y->size = x->size;
x->size = x->left->size + x->right->size + 1;
}
//紅黑樹調整
void Os_Tree::Os_Insert_Fixup(node *z)
{
node *y;
//唯一需要調整的情況,就是違反性質2的時候,如果不違反性質2,調整結束
while(z->p->color == RED)
{
//p[z]是左孩子時,有三種情況
if(z->p == z->p->p->left)
{
//令y是z的叔結點
y = z->p->p->right;
//第一種情況,z的叔叔y是紅色的
if(y->color == RED)
{
//將p[z]和y都著為黑色以解決z和p[z]都是紅色的問題
z->p->color = BLACK;
y->color = BLACK;
//將p[p[z]]著為紅色以保持性質5
z->p->p->color = RED;
//把p[p[z]]當作新增的結點z來重復while循環
z = z->p->p;
}
else
{
//第二種情況:z的叔叔是黑色的,且z是右孩子
if(z == z->p->right)
{
//對p[z]左旋,轉為第三種情況
z = z->p;
Left_Rotate(z);
}
//第三種情況:z的叔叔是黑色的,且z是左孩子
//交換p[z]和p[p[z]]的顏色,并右旋
z->p->color = BLACK;
z->p->p->color = RED;
Right_Rotate(z->p->p);
}
}
//p[z]是右孩子時,有三種情況,與上面類似
else if(z->p == z->p->p->right)
{
y = z->p->p->left;
if(y->color == RED)
{
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else
{
if(z == z->p->left)
{
z = z->p;
Right_Rotate(z);
}
z->p->color = BLACK;
z->p->p->color = RED;
Left_Rotate(z->p->p);
}
}
}
//根結點置為黑色
root->color = BLACK;
}
//插入一個結點
void Os_Tree::Os_Insert(node *z)
{
node *y = nil, *x = root;
//找到應該插入的位置,與二叉查找樹的插入相同
while(x != nil)
{
x->size++;
y = x;
if(z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if(y == nil)
root = z;
else if(z->key < y->key)
y->left = z;
else
y->right = z;
z->left = nil;
z->right = nil;
//將新插入的結點轉為紅色
z->color = RED;
//從新插入的結點開始,向上調整
Os_Insert_Fixup(z);
}
//對樹進行調整,x指向一個紅黑結點,調整的過程是將額外的黑色沿樹上移
void Os_Tree::Os_Delete_Fixup(node *x)
{
node *w;
//如果這個額外的黑色在一個根結點或一個紅結點上,結點會吸收額外的黑色,成為一個黑色的結點
while(x != root && x->color == BLACK)
{
//若x是其父的左結點(右結點的情況相對應)
if(x == x->p->left)
{
//令w為x的兄弟,根據w的不同,分為三種情況來處理
//執行刪除操作前x肯定是沒有兄弟的,執行刪除操作后x肯定是有兄弟的
w = x->p->right;
//第一種情況:w是紅色的
if(w->color == RED)
{
//改變w和p[x]的顏色
w->color = BLACK;
x->p->color = RED;
//對p[x]進行一次左旋
Left_Rotate(x->p);
//令w為x的新兄弟
w = x->p->right;
//轉為2.3.4三種情況之一
}
//第二情況:w為黑色,w的兩個孩子也都是黑色
if(w->left->color == BLACK && w->right->color == BLACK)
{
//去掉w和x的黑色
//w只有一層黑色,去掉變為紅色,x有多余的一層黑色,去掉后恢復原來顏色
w->color = RED;
//在p[x]上補一層黑色
x = x->p;
//現在新x上有個額外的黑色,轉入for循環繼續處理
}
//第三種情況,w是黑色的,w->left是紅色的,w->right是黑色的
else
{
if(w->right->color == BLACK)
{
//改變w和left[x]的顏色
w->left->color = BLACK;
w->color = RED;
//對w進行一次右旋
Right_Rotate(w);
//令w為x的新兄弟
w = x->p->right;
//此時轉變為第四種情況
}
//第四種情況:w是黑色的,w->left是黑色的,w->right是紅色的
//修改w和p[x]的顏色
w->color =x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
//對p[x]進行一次左旋
Left_Rotate(x->p);
//此時調整已經結束,將x置為根結點是為了結束循環
x = root;
}
}
//若x是其父的左結點(右結點的情況相對應)
else if(x == x->p->right)
{
//令w為x的兄弟,根據w的不同,分為三種情況來處理
//執行刪除操作前x肯定是沒有兄弟的,執行刪除操作后x肯定是有兄弟的
w = x->p->left;
//第一種情況:w是紅色的
if(w->color == RED)
{
//改變w和p[x]的顏色
w->color = BLACK;
x->p->color = RED;
//對p[x]進行一次左旋
Right_Rotate(x->p);
//令w為x的新兄弟
w = x->p->left;
//轉為2.3.4三種情況之一
}
//第二情況:w為黑色,w的兩個孩子也都是黑色
if(w->right->color == BLACK && w->left->color == BLACK)
{
//去掉w和x的黑色
//w只有一層黑色,去掉變為紅色,x有多余的一層黑色,去掉后恢復原來顏色
w->color = RED;
//在p[x]上補一層黑色
x = x->p;
//現在新x上有個額外的黑色,轉入for循環繼續處理
}
//第三種情況,w是黑色的,w->right是紅色的,w->left是黑色的
else
{
if(w->left->color == BLACK)
{
//改變w和right[x]的顏色
w->right->color = BLACK;
w->color = RED;
//對w進行一次右旋
Left_Rotate(w);
//令w為x的新兄弟
w = x->p->left;
//此時轉變為第四種情況
}
//第四種情況:w是黑色的,w->right是黑色的,w->left是紅色的
//修改w和p[x]的顏色
w->color =x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
//對p[x]進行一次左旋
Right_Rotate(x->p);
//此時調整已經結束,將x置為根結點是為了結束循環
x = root;
}
}
}
//吸收了額外的黑色
x->color = BLACK;
}
//找最小值
node *Os_Tree::Tree_Minimum(node *x)
{
//只要有比當前結點小的結點
while(x->left != nil)
x = x->left;
return x;
}
//查找中序遍歷下x結點的后繼,后繼是大于key[x]的最小的結點
node *Os_Tree::Tree_Successor(node *x)
{
//如果有右孩子
if(x->right != nil)
//右子樹中的最小值
return Tree_Minimum(x->right);
//如果x的右子樹為空且x有后繼y,那么y是x的最低祖先結點,且y的左兒子也是
node *y = x->p;
while(y != NULL && x == y->right)
{
x = y;
y = y->p;
}
return y;
}
//遞歸地查詢二叉查找樹
node *Os_Tree::Os_Search(node *x, int k)
{
//找到葉子結點了還沒找到,或當前結點是所查找的結點
if(x->key == -1 || k == x->key)
return x;
//所查找的結點位于當前結點的左子樹
if(k < x->key)
return Os_Search(x->left, k);
//所查找的結點位于當前結點的左子樹
else
return Os_Search(x->right, k);
}
//紅黑樹的刪除
node *Os_Tree::Os_Delete(node *z)
{
//找到結點的位置并刪除,這一部分與二叉查找樹的刪除相同
node *x, *y;
if(z->left == nil || z->right == nil)
y = z;
else y = Tree_Successor(z);
node *p = y->p;
while(p != nil)
{
p->size--;
p = p->p;
}
if(y->left != nil)
x = y->left;
else x = y->right;
x->p = y->p;
if(y->p == nil)
root = x;
else if(y == y->p->left)
y->p->left = x;
else
y->p->right = x;
if(y != z)
z->key = y->key;
//如果被刪除的結點是黑色的,則需要調整
if(y->color == BLACK)
Os_Delete_Fixup(x);
return y;
}
void Os_Tree::Print(node *x)
{
if(x->key == -1)
return;
Print(x->left);
cout<<x->key<<' '<<x->color<<endl;
Print(x->right);
}
void Os_Tree::Print()
{
Print(root);
cout<<endl;
}
//查找以x為根結點的樹中第i大的結點
node *Os_Tree::Os_Select(node *x, int i)
{
//令x左子樹中點的個數為r-1,
int r = x->left->size +1;
//那么x是x樹中第r大的結點
if(r == i)
return x;
//第i大的元素在x->left中
else if(i < r)
return Os_Select(x->left, i);
//第i大的元素在x->right中
else
return Os_Select(x->right, i - r);
}
//計算樹T中進行順序遍歷后得到的線性序中x的位置
int Os_Tree::Os_Rank(node *x)
{
//置r為以x為根的子樹中key[x]的秩
int r = x->left->size + 1;
node *y = x;
while(y != root)
{
//若y是p[y]的右孩子,p[y]和p[y]左子樹中所有結點前于x
if(y == y->p->right)
r = r + y->p->left->size + 1;
y = y->p;
}
return r;
}
~~~
### 2.main.cpp
~~~
#include <iostream>
#include "Os_Tree.h"
using namespace std;
int main()
{
char ch;
int x;
//生成一棵順序統計樹
Os_Tree *T = new Os_Tree;
while(1)
{
cin>>ch;
switch(ch)
{
//插入一個元素
case 'I':
{
cin>>x;
node *z = new node(T->nil, x);
T->Os_Insert(z);
break;
}
//刪除一個元素
case 'D':
{
cin>>x;
node *z = T->Os_Search(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
T->Os_Delete(z);
break;
}
//計算第x小關鍵字
case 'S':
{
cin>>x;
node *z = T->Os_Select(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
cout<<z->key<<endl;
break;
}
//計算x的位置
case 'R':
{
cin>>x;
node *z = T->Os_Search(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
cout<<T->Os_Rank(z)<<endl;
break;
}
case 'P':
T->Print();
break;
default:
break;
}
}
return 0;
}
~~~
# 三、練習
14.1-3
~~~
//14.1-3非遞歸地查找以x為根結點的樹中第i大的結點
node *Os_Tree::Os_Select_Iterative(node *x, int i)
{
//根結點開始找起
while(x != NULL)
{
int r = x->left->size + 1;
//如果找到了
if(r == i)
return x;
//如果位置更靠前
if(i < r)
x = x->left;
//如果位置更靠后
else
{
x = x->right;
i = i - r;
}
}
}
~~~
14.1-4
~~~
//14.1-4遞歸地計算樹T中進行順序遍歷后得到的線性序中x的位置
int Os_Tree::Os_Rank_Recursion(node *root, node *x)
{
if(x->key == root->key)
return root->left->size + 1;
if(x->key > root->key)
//左子樹的結點個數 + 根結點 + x在右結點中的秩
return root->left->size + 1 + Os_Rank_Recursion(root->right, x);
//在左子樹中的秩
return Os_Rank_Recursion(root->left, x);
}
~~~
14.1-5
~~~
//14.1-5確定x在該樹的線性序中第i個后繼
node *Os_Tree::Next(node *x, int i)
{
//就是當前結點
if(i == 0)
return x;
//在x的右子樹中
if(x->right != nil && x->right->size >= i)
return Os_Select(x->right, i);
//或在x某個祖先的右子樹中
else
{
//找到某個“有右子樹”且“x不在其右子樹上”的祖先
while(x->p != NULL && x == x->p->right)
x = x->p;
//找到了根結點,就停止查找
if(x->p == NULL)
{
cout<<"error:not exist"<<endl;
exit(0);
}
//對這個祖先進行遞歸的查找
Next(x, i-1);
}
}
~~~
15.1-6
~~~
附加信息rank[x]
插入時,若插入到x結點的左子樹中,則rank[x] = rank[x] + 1,否則不變
刪除時,若刪除的結點在x的左子樹中,則rank[x] = rank[x] - 1,否則不變
左旋時,若對x執行左旋,令y=x->right,則rank[x]不變,rank[y] = rank[y] + rank[x]
右旋時,若對x執行右旋,令y=x->left,則rank[y]不變,rank[x] = rank[x] + rank[y]
~~~
14.1-7
見[算法導論-14.1-7](http://blog.csdn.net/mishifangxiangdefeng/article/details/7730702)
[求逆序數](http://blog.csdn.net/mishifangxiangdefeng/article/details/7175642)中介紹了使用樹狀數組或歸并排序求逆序對,這里使用順序統計數。
數組中某個數字s[i]的逆序數是指出現在s[i]之前,但是比s[i]大的數字的個數。
根據順序統計量的Os_Rank(),每插入到一個元素x后,可以求得在已經出現的元素中,比x大的數字的個數
14.1-8【轉】
通過角度來判斷兩條弦是否相交,這樣可以在O(n*logn)內完成。
對于兩條弦P1P2和Q1Q2來說(順時針),圓心與端點形成的向量有一個角度A
如果A(P1)<A(Q1)<A(P2)<A(Q2)或者A(Q1)<A(P1)<A(Q2)<A(P2),這樣角度區間“交叉”就意味著兩條弦有交叉。
通過角度來統計交叉弦的對數,和“逆序對”的問題本質上是一樣的
這可以看做是“順序統計樹”的典型應用。
我們判斷兩條弦是否相交的依據還是上面提到的“角度”區間是否有“交叉”現象發生
(注意一個區間包含另一個區間的情況不能算作“交叉”)
首先n條弦共2n個端點,每個端點對于圓心來說,都對應一個[0,2*pi)內的角度。
我們按角度大小(實際上就是逆時針方向)對這2n個角度進行排序,這一步需要花費O(n*logn)
對于每條弦來說,它的兩個端點都可以看做是“事件點”:從0角度開始逆時針在圓上掃描,遇到弦的第一個點可以看成是弦的“起點”,遇到的第二個點看成是弦的“終點”。
然后,我們用一棵“順序統計樹”來輔助進行處理(初始化當然為空)。
~~~
按照角度小到大的順序遍歷這2n個端點:
如果該端點是某條弦X的“起點”
{
將弦X插入順序統計樹中(以X的“起點”角度作為key);
}
如果該端點是某條弦X的“終點”
{
統計出目前這棵樹中有多少條弦的“起點”角度比X的“起點”角度大,這就是與X相交的弦的數量;
//對于順序統計樹來說,上面這步只要O(logn)就能實現
將弦X從順序統計樹中刪除; //這一步同樣只需要O(logn)
}
~~~
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支