次优查找树的建立

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

　　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<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;
}

/*
　　演示结果如下:
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<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("\n");
             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("\n");
             if(q.empty()) break;//这是最后一层
             cout<<setw(ld-1)<<"";
             for(int i=ld; i<=rd; ++i)
                 printf("-") ;
             printf("\n");
         }
     }
}

int main(){
    NearlyOptimalSearchTree<string> 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     G
 -------------
 |     |     |
 B     E     H
-----------------
|   |           |
A   C           I

调整后的先序遍历:

 D
   -------
   |     |
   C     F
 -----------
 |     |   |
 B     E   G
-----------------
|               |
A               I
------------------
             |
             H

*/
时间： 2024-05-18 05:33:01

次优查找树的建立的相关文章

浅谈算法和数据结构 十 平衡查找树之B树

前面讲解了平衡查找树中的2-3树以及其实现红黑树.2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key. 维基百科对B树的定义为"在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树.与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作.B-tree算法减少定位记录时所经历的中间过程,从而

浅谈算法和数据结构 九 平衡查找树之红黑树

前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度.但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息.红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个

浅谈算法和数据结构 八 平衡查找树之2-3树

前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低.本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态,这就是平衡查找树(Balanced Search Tree).在一棵具有N 个节点的树中,我们希望该树的高度能够维持在lgN左右,这样我们就能保证只需要lgN次比较操作就可以查找到想要的值.不幸的是,每次插

C语言实现输入一颗二元查找树并将该树转换为它的镜像_C 语言

本文实例讲述了C语言实现输入一颗二元查找树并将该树转换为它的镜像的方法,分享给大家供大家参考.具体实现方法如下: 采用递归方法实现代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <algorithm> using namespace std; struct Node { Node(int

并发数据结构-1.7 查找树

原文链接,译文链接,译者:iDestiny,校对:周可人 任何查找树的并发实现都可以通过用一个独占锁保护来完成.通过使用读写锁对并发性能有一定提升,读写锁允许所有只读(查找)操作并发地执行,因为读操作是以共享模式持有锁,然而更新(插入或删除)操作持有独占模式的锁,从而排斥其他所有操作.如果更新操作比较少,这还能接受,但是只要有适量的更新操作,那么更新操作所持有的独占锁将产生线性的瓶颈,从而大大降低性能.通过使用细粒度的锁策略--比如每个节点一个锁,而不是整棵树使用同一个锁--这样我们进一步地提升

判断整数序列是否为二元查找树的后序遍历结果的解决方法_C 语言

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false.例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果.    8    / \  6   10 / \    / \ 5  7 9 11因此返回true.如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false.本题网上已经有用递归单纯判断的解法. 个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断. 相比

C#实现平衡多路查找树(B树)

搞了SQL Server时间也不短了,对B树的概念也算是比较了解.去网上搜也搜不到用C#或java实现的B树,干脆自己写一个.实现B树的过程中也对很多细节有了更深的了解. 简介 B树是一种为辅助存储设计的一种数据结构,在1970年由R.Bayer和E.mccreight提出.在文件系统和数据库中为了减少IO操作大量被应用.遗憾的是,他们并没有说明为什么取名为B树,但按照B树的性质来说B通常被解释为Balance.在国内通常有说是B-树,其实并不存在B-树,只是由英文B-Tree直译成了B-树.

hbase源码系列（五）Trie单词查找树

在上一章中提到了编码压缩,讲了一个简单的DataBlockEncoding.PREFIX算法,它用的是前序编码压缩的算法,它搜索到时候,是全扫描的方式搜索的,如此一来,搜索效率实在是不敢恭维,所以在hbase当中单独拿了一个工程出来实现了Trie的数据结果,既达到了压缩编码的效果,亦达到了方便查询的效果,一举两得,设置的方法是在上一章的末尾提了. 下面讲一下这个Trie树的原理吧. 树里面有3中类型的数据结构,branch(分支).leaf(叶子).nub(节点) 1.branch 分支节点,比

数据结构－二分查找树(C描述)

tree.h typedef int ElementType; #ifndef TREE_H_INCLUDED #define TREE_H_INCLUDED struct TreeNode; typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; SearchTree MakeEmpty(SearchTree T); Position Find(ElementType X, SearchTree T); P