静态查找静态树表

一、基本思想

静态树表为的是解决查找概率不等的记录。一般情况下&＃xff0c;我们都是默认各个记录等概率查找的&＃xff0c;但是有些记录可能不是等概率的。我们可能会首先搜索一些概率大的记录。

二、构造过程

次优查找树和最优查找树的查找性能仅差1%-2%&＃xff0c;而构造最优查找树花费时间代价较高。现构造一棵二叉树&＃xff0c;使得二叉树的带权内的路径长度PH值在所有具有同样权值的二叉树中近似最小&＃xff0c;称为次优查找树。
构造原理如下&＃xff1a;

三、事例