데이터 구조 복습 차 검색 트 리 구축

검색 효율 이 가장 높 은 것 은 평균 검색 길이 가 가장 작은 것 이다. 앞에서 배 운 지식 에 따라 우 리 는 질서 표 가 비 등 확률 상황 에서 지 켜 야 할 두 가지 원칙 을 제시 할 수 있다.   
1. 가장 먼저 방문 하 는 결점 은 방문 확률 이 가장 큰 결점 이 어야 한다. 
2. 매번 방문 할 때마다 결점 양쪽 에 아직 방문 하지 않 은 결점 의 방문 확률 과 가능 한 한 같 아야 한다.
이 두 가지 원칙 은 한 마디 로 나 무 를 띠 권 내 경로 의 길이 와 가장 작은 이 진 트 리 로 판정 하 는 것 이다. 즉, PH = ＞ wihi 이다.  최소, 그 중 n 은 질서 표 길이, hi i 번 째 결점 판정 트 리 의 층 횟수, wi = cpi, c 는 상수, pi 제 i 의 결점 을 찾 을 확률 입 니 다.
        이러한 나 무 는 정적 최 적 검색 트 리 (static optimal search tree) 라 고 부 릅 니 다. 이런 나 무 를 구성 하 는 시간 대가 가 너무 크 고 시간 복잡 도가 매우 크기 때문에 우 리 는 보통 구조 차 우수 검색 트 리 (nearly optimal search tree) 입 니 다. 구조 시간 대 가 는 구조 최 적 검색 트 리 보다 훨씬 낮 지만 검색 성능 은 최 적 검색 트 리 보다 1% ~ 2% 차이 가 납 니 다.3% 이상 차이 가 거의 없다.
차 우 찾기 트 리 의 구조:           순서 표 가 있 는 모든 기록 의 가중치 는 wl, wl + 1, wh 이 고 첫 번 째 방문 해 야 할 노드 번 호 는 i 이 며 다음 과 같다. Δpi =   ∑wj - ∑wj   최소Δpi = Min {Δpj } {rl, rl + 1,..., ri - 1} 과 {ri + 1, ri + 2,..., rh} 에 대해 각각 차 검색 트 리 를 구성 합 니 다.   계산 하기 편리 하도록 누적 가중치 swi = ＞ wj 를 도입 하고 wl - 1 = swl - 1 = 0 을 설정 하면:
            구조 차 우 에서 나 무 를 찾 을 때 앞에서 말 한 원칙 1 을 고려 하지 않 았 기 때문에 뿌리 로 선 정 된 노드 의 가중치 가 인근 노드 의 가중치 보다 작 을 수 있 습 니 다. 이때 나 무 를 찾 아 적당 한 조정 을 하고 인접 가중치 가 큰 결점 을 뿌리 결점 으로 해 야 합 니 다.
          차 우 검색 트 리 의 검색 방법 은 절반 으로 나 누 어 찾 는 것 과 유사 하 며, 평균 검색 길 이 는 log n 과 정비례 한다.
주의: 상기 알고리즘 을 이용 하여 차 우 이 진 트 리 를 구성 한 후에 가장 좋 은 것 이 아 닐 수 있 습 니 다. 구조 과정 에서 하나의 키워드 의 해당 가중치 를 고려 하지 않 으 면 뿌리 로 선 택 된 키워드 의 가중치 비례 가 나타 날 수 있 습 니 다.
인접 한 키워드 의 가중치 가 작 습 니 다. 이 때 는 적당 한 조정 을 해 야 합 니 다. 인접 한 가중치 가 큰 키 워드 를 선택 하여 차 우 검색 트 리 의 뿌리 노드 (즉, 왼쪽 회전 과 오른쪽 회전 트 리 \ # include < iostream > 입 니 다.

#include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<cmath>

#define N 100

#define MAXN 0x3f3f3f3f

using namespace std; template<typename T>

class TreeNode{ public: TreeNode* child[2]; T val; int w; TreeNode(){ child[0] = child[1] = NULL; } }; template<typename T>

class NearlyOptimalSearchTree{//      

    public: int n; T val[N]; int w[N]; int sw[N]; TreeNode<T> *t; void input(); void init(); void outT(TreeNode<T>* t); private: void buildT(int ld, int rd, TreeNode<T>* &t);//        

        void adjustment(TreeNode<T>* &t);//        

        void rotateT(TreeNode<T>* &t, int x); }; template<typename T>

void NearlyOptimalSearchTree<T>::input(){ cin>>n; for(int i=1; i<=n; ++i) cin>>val[i]>>w[i]; } template<typename T>

void NearlyOptimalSearchTree<T>::init(){ sw[0] = 0; for(int i=1; i<=n; ++i) sw[i] = sw[i-1]+w[i]; buildT(1, n, t); cout<<"          :"<<endl; outT(t); adjustment(t); cout<<endl<<"        :"<<endl; outT(t); cout<<endl; } template<typename T>

void NearlyOptimalSearchTree<T>::buildT(int ld, int rd, TreeNode<T>* &t){ if(ld > rd) return; int minN = MAXN; int i; for(int j=ld; j<=rd; ++j){ int ans = sw[rd] - sw[j-1] - sw[j]; ans = abs(ans); if(minN > ans){ minN = ans; i = j; } } t = new TreeNode<T>; t->val = val[i]; t->w = w[i]; if(ld==rd) return; buildT(ld, i-1, t->child[0]); buildT(i+1, rd, t->child[1]); } template<typename T>

void NearlyOptimalSearchTree<T>::adjustment(TreeNode<T>* &t){ if(!t) return; int lmax = 0, rmax = 0; if(t->child[0]) lmax = t->child[0]->w; if(t->child[1]) rmax = t->child[1]->w; int maxVal = max(lmax, rmax); if(t->w < maxVal){ if(maxVal == lmax){ rotateT(t, 1);//     

        } else { rotateT(t, 0);//     

 } } adjustment(t->child[0]); adjustment(t->child[1]); } template<typename T>

void NearlyOptimalSearchTree<T>::rotateT(TreeNode<T>* &o, int x){ TreeNode<T>* k = o->child[x^1]; o->child[x^1] = k->child[x]; k->child[x] = o; o = k; } template<typename T>

void NearlyOptimalSearchTree<T>::outT(TreeNode<T>* t){ if(!t) return; cout<<t->val<<" "; outT(t->child[0]); outT(t->child[1]); } int main(){ NearlyOptimalSearchTree<string> nost; nost.input(); nost.init(); return 0; }

/*
　　      :

9A 1B 1C 2D 5E 3F 4G 4H 3I 5 조정 전의 순서 없 음: F D B A C E G H I 조정 후의 순서 없 음: D C B A F E G I H

 
   
5
A 1
B 30
C 2
D 29
E 2
没有调整前的先序遍历:
C B A D E
调整后的先序遍历:
B A D C E
 
   

*/
  
  
#include<iostream> 

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<string> 

#include<iomanip>

#include<cmath>

#include<queue>

#define N 100

#define MAXN 0x3f3f3f3f

using namespace std;



template<typename T>

class TreeNode{

    public:

        TreeNode* child[2];

        T val;

        int w; 

        int d;//          

        TreeNode(){

            child[0] = child[1] = NULL;

        }

};



template<typename T>

class NearlyOptimalSearchTree{//      

    public:

        int n;

        T val[N];

        int w[N];

        int sw[N];

        TreeNode<T> *t;

        void input();

        void init();

        void outT(TreeNode<T>* t);

    private:

        int width;

        int step;

        void buildT(int ld, int rd, TreeNode<T>* &t);//        

        void adjustment(TreeNode<T>* &t);//        

        void rotateT(TreeNode<T>* &t, int x);

        void widthT(TreeNode<T>* t);//               

};



template<typename T>

void NearlyOptimalSearchTree<T>::input(){

    cin>>n;

    for(int i=1; i<=n; ++i)

        cin>>val[i]>>w[i];

}



template<typename T>

void NearlyOptimalSearchTree<T>::init(){

    sw[0] = 0;

    width = 0;

    step = 2;

    for(int i=1; i<=n; ++i)    

        sw[i] = sw[i-1]+w[i];

    buildT(1, n, t);

    cout<<"          :"<<endl;

    outT(t);

    adjustment(t);

    cout<<endl<<"        :"<<endl;

    outT(t);

    cout<<endl;

}



template<typename T>

void NearlyOptimalSearchTree<T>::buildT(int ld, int rd, TreeNode<T>* &t){

    if(ld > rd) return;

    int minN = MAXN;

    int i;

    for(int j=ld; j<=rd; ++j){

        int ans = sw[rd] - sw[j-1] - sw[j];    

        ans = abs(ans);

        if(minN > ans){

            minN = ans;

            i = j;

        }

    }

    t = new TreeNode<T>;

    t->val = val[i];

    t->w = w[i];

    if(ld==rd) return;

    buildT(ld, i-1, t->child[0]);

    buildT(i+1, rd, t->child[1]);

}



template<typename T>

void NearlyOptimalSearchTree<T>::adjustment(TreeNode<T>* &t){

    if(!t) return;

    int lmax = 0, rmax = 0;

    if(t->child[0]) lmax = t->child[0]->w;

    if(t->child[1]) rmax = t->child[1]->w;

    int maxVal = max(lmax, rmax);

    if(t->w < maxVal){

        if(maxVal == lmax){

            rotateT(t, 1);//     

        } else {

            rotateT(t, 0);//     

        } 

    }

    adjustment(t->child[0]);

    adjustment(t->child[1]);

}



template<typename T>

void NearlyOptimalSearchTree<T>::rotateT(TreeNode<T>* &o, int x){

    TreeNode<T>* k = o->child[x^1];

    o->child[x^1] = k->child[x];

    k->child[x] = o;

    o = k; 

}



template<typename T>

void NearlyOptimalSearchTree<T>::widthT(TreeNode<T>* t){

    if(!t) return;

    widthT(t->child[0]);

    t->d = width;

    width+=step; 

    widthT(t->child[1]);

}



template<typename T>

void NearlyOptimalSearchTree<T>::outT(TreeNode<T>* t){

    width=0;

     widthT(t);

     queue<TreeNode<T>*> q, qq;

     q.push(t);

     int n=1;//         

     int i=1;//         

     int nn=0;//           

     int pred;//              

     while(!q.empty()){

         TreeNode<T>* tt = q.front();

         q.pop();

         qq.push(tt);

        if(tt != t){//     ,        

             if(i==1){

                 printf("%*s", tt->d, "|");

                 pred = tt->d;

             } else {

                 printf("%*s", tt->d-pred, "|");

                 pred = tt->d;

             }

        }

         //       

         if(tt->child[0]) q.push(tt->child[0]), ++nn;

         if(tt->child[1]) q.push(tt->child[1]), ++nn;

        ++i; 

        if(i>n){//        

             i=1;

             n = nn;

             nn = 0;

             printf("
");

             bool first = true;//             

             int ld, rd; 

             while(!qq.empty()){//         

                 TreeNode<T>* tt = qq.front();

                 qq.pop();

                 if(first){

                     cout<<setw(tt->d)<<tt->val;

                     pred = tt->d;

                     ld = tt->d;

                     if(tt->child[0])

                         ld = tt->child[0]->d; 

                 } else {

                     cout<<setw(tt->d - pred)<<tt->val;

                     pred = tt->d;

                 }

                first = false;

                if(qq.empty()){//           

                    rd = tt->d+1;

                    if(tt->child[1])

                        rd = tt->child[1]->d;

                }

             }

             printf("
");

             if(q.empty()) break;//       

             cout<<setw(ld-1)<<"";

             for(int i=ld; i<=rd; ++i)

                 printf("-") ;

             printf("
");

         }

     }

}



int main(){

    NearlyOptimalSearchTree<string> nost;

    nost.input();

    nost.init();

    return 0;

}

/*
　　//    
  
9A 1B 1C 2D 5E 3F 4G 4H 3I 5 조정 전의 순서 가 없 음:
 
   
 F
 -------
 | |
 D G
 -------------
 | | |
 B E H
-----------------
| | |
A C I
 
   
 
   
调整后的先序遍历:
 
   
 
   
 D
 -------
 | |
 C F
 -----------
 | | |
 B E G
-----------------
| |
A I
------------------
 |
 H
 
   

*/