次优查找树的建立-白红宇

　　查找效率最高即平均查找长度最小，根据前面所学知识，我们可以给出有序表在非等概率情况下应遵循的两个原则：

　　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，则：

由于在构造次优查找树时没有考虑前面说的原则一，因此被选为根的结点的权值可能比其邻近结点的权值小，此时应对查找树作适当的调整，将相邻权值大的结点作为根结点。

次优查找树的查找方法与折半查找类似，其平均查找长度与 log n 成正比。

注意：利用上述算法构造好次优二叉树之后，可能并不是最优的，因为在构造过程中，没有考虑单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与

　　　它相邻的关键字的权值小。此时应做适当的调整：选取邻近的权值较大的关键字作为次优查找树的根节点（也就是左旋和右旋子树

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
           #include
          
           #define N 100#define MAXN 0x3f3f3f3fusing namespace std;template
           
            class TreeNode{ public: TreeNode* child[2]; T val; int w; TreeNode(){ child[0] = child[1] = NULL; }};template
            
             class NearlyOptimalSearchTree{ //次优查找树 public: int n; T val[N]; int w[N]; int sw[N]; TreeNode
             
               *t; void input(); void init(); void outT(TreeNode
              
               * t); private: void buildT(int ld, int rd, TreeNode
               
                * &t);//建立次优查找树 void adjustment(TreeNode
                
                 * &t);//调整次优查找树 void rotateT(TreeNode
                 
                  * &t, int x);};template
                  
                   void NearlyOptimalSearchTree
                   
                    ::input(){ cin>>n; for(int i=1; i<=n; ++i) cin>>val[i]>>w[i];}template
                    
                     void NearlyOptimalSearchTree
                     
                      ::init(){ sw[0] = 0; for(int i=1; i<=n; ++i) sw[i] = sw[i-1]+w[i]; buildT(1, n, t); cout<<"没有调整前的先序遍历:"<
                      
                       void NearlyOptimalSearchTree
                       
                        ::buildT(int ld, int rd, TreeNode
                        
                         * &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->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
                          
                           void NearlyOptimalSearchTree
                           
                            ::adjustment(TreeNode
                            
                             * &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
                             
                              void NearlyOptimalSearchTree
                              
                               ::rotateT(TreeNode
                               
                                * &o, int x){ TreeNode
                                
                                 * k = o->child[x^1]; o->child[x^1] = k->child[x]; k->child[x] = o; o = k; }template
                                 
                                  void NearlyOptimalSearchTree
                                  
                                   ::outT(TreeNode
                                   
                                    * t){ if(!t) return; cout<
                                    
                                     val<<" "; outT(t->child[0]); outT(t->child[1]);}int main(){ NearlyOptimalSearchTree
                                     
                                       nost; nost.input(); nost.init(); return 0;} /* 　　演示结果如下:

A 1

B 1

C 2

D 5

E 3

F 4

G 4

H 3

I 5

没有调整前的先序遍历:

F D B A C E G H I

调整后的先序遍历:

D C B A F E G I H

A 1

B 30

C 2

D 29

E 2

没有调整前的先序遍历:

C B A D E

调整后的先序遍历:

B A D C E

*/

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
           #include
          
           #include
           
            #include
            
             #define N 100#define MAXN 0x3f3f3f3fusing namespace std;template
             
              class TreeNode{ public: TreeNode* child[2]; T val; int w; int d;//距离屏幕左端的宽度 TreeNode(){ child[0] = child[1] = NULL; }};template
              
               class NearlyOptimalSearchTree{ //次优查找树 public: int n; T val[N]; int w[N]; int sw[N]; TreeNode
               
                 *t; void input(); void init(); void outT(TreeNode
                
                 * t); private: int width; int step; void buildT(int ld, int rd, TreeNode
                 
                  * &t);//建立次优查找树 void adjustment(TreeNode
                  
                   * &t);//调整次优查找树 void rotateT(TreeNode
                   
                    * &t, int x); void widthT(TreeNode
                    
                     * t);//计算每个节点到屏幕左端的距离 };template
                     
                      void NearlyOptimalSearchTree
                      
                       ::input(){ cin>>n; for(int i=1; i<=n; ++i) cin>>val[i]>>w[i];}template
                       
                        void NearlyOptimalSearchTree
                        
                         ::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<<"没有调整前的先序遍历:"<
                         
                          void NearlyOptimalSearchTree
                          
                           ::buildT(int ld, int rd, TreeNode
                           
                            * &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->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
                             
                              void NearlyOptimalSearchTree
                              
                               ::adjustment(TreeNode
                               
                                * &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
                                
                                 void NearlyOptimalSearchTree
                                 
                                  ::rotateT(TreeNode
                                  
                                   * &o, int x){ TreeNode
                                   
                                    * k = o->child[x^1]; o->child[x^1] = k->child[x]; k->child[x] = o; o = k; }template
                                    
                                     void NearlyOptimalSearchTree
                                     
                                      ::widthT(TreeNode
                                      
                                       * t){ if(!t) return; widthT(t->child[0]); t->d = width; width+=step; widthT(t->child[1]);}template
                                       
                                        void NearlyOptimalSearchTree
                                        
                                         ::outT(TreeNode
                                         
                                          * t){ width=0; widthT(t); queue
                                          
                                           
                                            *> q, qq; q.push(t); int n=1;//当前层的节点个数 int i=1;//当前层第几个节点 int nn=0;//统计下一次的节点的个数 int pred;//前一个节点距离左屏幕的距离 while(!q.empty()){ TreeNode
                                            
                                             * 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("\n"); bool first = true;//是否是这一行的第一个节点 int ld, rd; while(!qq.empty()){ //打印上层节点字符 TreeNode
                                             
                                              * tt = qq.front(); qq.pop(); if(first){ cout<
                                              
                                               d)<
                                               
                                                val; pred = tt->d; ld = tt->d; if(tt->child[0]) ld = tt->child[0]->d; } else { cout<
                                                
                                                 d - pred)<
                                                 
                                                  val; pred = tt->d; } first = false; if(qq.empty()){ //这一层的最后一个节点 rd = tt->d+1; if(tt->child[1]) rd = tt->child[1]->d; } } printf("\n"); if(q.empty()) break;//这是最后一层 cout<
                                                  
                                                   <<""; for(int i=ld; i<=rd; ++i) printf("-") ; printf("\n"); } }}int main(){ NearlyOptimalSearchTree
                                                   
                                                     nost; nost.input(); nost.init(); return 0;} /* 　　//演示结果

A 1

B 1

C 2

D 5

E 3

F 4

G 4

H 3

I 5

没有调整前的先序遍历:

-------

| |

D G

-------------

| | |

B E H

-----------------

| | |

A C I

调整后的先序遍历:

-------

| |

C F

-----------

| | |

B E G

-----------------

| |

A I

------------------

*/