splaytree.cpp (4) topdown

Bài toàn

Thực hiện thao tác chèn trên splay tree kiểu top-down indexable.

Độ phức tạp

Lên đến O(logn) cho các thao tác.

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <iostream>

#include <algorithm>

using namespace std;

struct node {

   int Value, Size;

   node *ll, *rr;

   node(int V, node* Nil){ Value=V; ll=rr=Nil; Size=1; }

   void update(){ Size=ll->Size+rr->Size+1; }

} *Nil, *Root;

node* first(node* a){ while (a->ll!=Nil) a=a->ll; return a; }

node* last(node* a){ while (a->rr!=Nil) a=a->rr; return a; }

node* link(node* L, node* X, node* R){ X->ll=L, X->rr=R, X->update(); return X; }

node* llzig(node* X, node* Y){ return link(Y->ll, Y, link(Y->rr, X, X->rr)); }

node* rrzig(node* X, node* Y){ return link(link(X->ll, X, Y->ll), Y, Y->rr); }

ostream& operator << (ostream& cout, node* a){

   if (a==Nil) return cout;

   return cout << "(" << a->ll << " " << a->Value << " " << a->rr << ")";

}

node* splay(node* X, int Index){

   node Header(0, Nil), *Left=&Header, *Right=&Header;

     while (X->ll->Size != Index){

      if (Index < X->ll->ll->Size)

         X=llzig(X, X->ll);

      else if (Index > X->ll->Size + 1 + X->rr->ll->Size) 

         X=rrzig(X, X->rr);

      if (X->ll->Size==Index) break;

      if (Index < X->ll->Size) { 

         node *Y=X->ll; X->ll=Nil, X->update();

         Right->ll=X, Right->update(); X=Y; Right=first(Right); 

      } else {

         Index -= X->ll->Size + 1;

         node *Y=X->rr; X->rr=Nil, X->update(); 

         Left->rr=X, Left->update(); X=Y; Left=last(Left);

      }

   }

   Left->rr=X->ll, Left->update();

   Right->ll=X->rr, Right->update();

   X->ll=Header.rr, X->rr=Header.ll, X->update();

   return X;

}

node* split(node* &X, int Index){

   if (X==Nil) return Nil;

   X=splay(X, Index);

   node* Y=X; X=Y->ll; Y->ll=Nil, Y->update();

   return Y;

}

node* join(node* X, node* Y){

   if (Y==Nil) return X;

   Y=splay(Y, 0);

   Y->ll=X, Y->update();

   return Y;

}

main(){

   Nil = new node(0, NULL); Nil->ll=Nil->rr=Nil; Nil->Size=0;

   Root=Nil;

   int x, y;

   while (cin >> x >> y){

      node* Foo = split(Root, x);

      Root=join(join(Root, new node(y, Nil)), Foo);

      cout << Root << endl;

   }

}

Nhận xét

Tạm thời thì mình thấy splay tree kiểu top-down có các đặc điểm: không cần lưu nút cha, không đệ quy.

Code có vẻ ngắn, đoạn code trên là 72 dòng, về sau code nhiều hơn thì độ dài sẽ còn giảm.