<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 一、概念 ### 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) } ~~~
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看