@fuheimao
2015-08-11T20:04:03.000000Z
字数 2135
阅读 604
数据结构
腹黑猫
#include "iostream"
#include "ctime"
#include "cstdlib"
using namespace std;
struct Node{
Node* Child[2];
int Key;
int Priority;
int Size;
void Maintain(){
Size = 1;
if (Child[0] != NULL) Size += Child[0] -> Size;
if (Child[1] != NULL) Size += Child[1] -> Size;
}
};
void Rotate(Node* &Top, bool Flick){
Node* K = Top -> Child[Flick ^ 1];
Top -> Child[Flick ^ 1] = K -> Child[Flick];
K -> Child[Flick] = Top;
Top -> Maintain();
K -> Maintain();
Top = K;
}
int Find(Node* Top, int Key){
while (Top != NULL){
if (Top -> Key == Key) return true;
int LOR = Key > Top -> Key;
Top = Top -> Child[LOR];
}
return false;
}
void Insert(Node* &Top, int Key){
//if (Find(Top, Key)) return; 若有重复元素注释掉……
if (Top == NULL){
Top = new Node();
Top -> Child[0] = Top -> Child[1] = NULL;
Top -> Key = Key;
Top -> Priority = rand();
}else{
int LOR = Key > Top -> Key;
Insert(Top -> Child[LOR], Key);
if (Top -> Child[LOR] -> Priority > Top -> Priority){
Rotate(Top, LOR ^ 1);
}
}
Top -> Maintain();
}
void Remove(Node* &Top, int Key){
int LOR = Key > Top -> Key;
if (Key == Top -> Key){
if (Top -> Child[0] == NULL){
Top = Top -> Child[1];
}else if (Top -> Child[1] == NULL){
Top = Top -> Child[0];
}else{
LOR = Top -> Child[0] -> Priority > Top -> Child[1] -> Priority;
Rotate(Top, LOR);
Remove(Top -> Child[LOR], Key);
}
}else{
Remove(Top -> Child[LOR], Key);
}
if (Top != NULL) Top -> Maintain();
}
int FindKth(Node* Top, int K){
if (Top == NULL || K <= 0 || K > Top -> Size) return 0;
int Size = (Top -> Child[1] == NULL ? 0 : Top -> Child[1] -> Size);
if (K == Size + 1){
return Top -> Key;
}else if (K <= Size){
return FindKth(Top -> Child[1], K);
}else{
return FindKth(Top -> Child[0], K - Size - 1);
}
}
int Rank(Node* Top, int Key){
if (!Find(Top, Key)) return 0;
int _Rank = (Top -> Child[0] == NULL ? 0 : Top -> Child[0] -> Size);
if (Top -> Key == Key){
return _Rank + 1;
}else if (Top -> Key > Key){
return Rank(Top -> Child[0], Key);
}else{
return Rank(Top -> Child[1], Key) + _Rank + 1;
}
}
Node* Predecessor(Node* Top, Node* Best, int Key){
if (Top == NULL) return Best;
if (Key < Top -> Key){
return Predecessor(Top -> Child[0], Best, Key);
}
return Predecessor(Top -> Child[1], Top, Key);
}
Node* Successor(Node* Top, Node* Best, int Key){
if (Top == NULL) return Best;
if (Key <= Top -> Key){
return Successor(Top -> Child[0], Top, Key);
}
return Successor(Top -> Child[1], Best, Key);
}
int main(int argc, char const *argv[]){
Node* Root = NULL;
Insert(Root, 10);
Insert(Root, 50);
Remove(Root, 10);
Insert(Root, 400);
Insert(Root, 20);
cout << endl << FindKth(Root, 2);
cout << endl << Rank(Root, 400);
return 0;
}