键树

来自计算思维百科
跳转至: 导航搜索
键树1.png

键树,又称数字查找树。它是一棵度大于等于2的树,树中的每个结点中包含了组成关键字的部分符号。这种树会给某种类型关键字的表的查找带来方便。

基本概念

键树是一种特殊的查找树,它的某个节点不是包含一个或多个关键字,而是只包含组成关键字的一部分(字符或数字),比如:如果关键字是数值,则节点中只包含一个数位;如果关键字是单词,则节点中只包含一个字母字符。

根结点不代表任何字符,根以下第一层的结点对应于字符串的第一个字符,第二层的结点对应于字符串的第二个字符,…,每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针,指向该关键字所对应的元素。

以下用一个例子来说明键树的含义:假设有如下10个关键字的集合:

{ CAI CAO CHA CHANG WEN CHAO WANG ZHAO WU CHEN}

首先按首字符的不同将他们分成三个子集:

{ CAI CAO CHA CHANG CHAO}  ,  { WEN WANG WU} ,  { ZHAO },

然后对2个关键字个数大于1的子集再按其第二个字符不同进行分割。依次类推,直到每个小子集中只含有一个关键字为止。例如对其中首字符为C的集合可进行如下的分割:

{ (CAI) (CAO) } ,{{ (CHA),(CHANG),(CHAO) } , { (CHEN) }

用键树表示如下:

键树2.png

应用范围

所有分类存储的问题都可以应用键树,例如图书馆书籍管理等。

使用方法及步骤

  1. 对需要处理的数据关键字进行分类;
  2. 同一类的关键字在一棵子树上;从根节点到子节点可以形成一个关键字。

应用案例

应用1- 基于键树索引的实时计费

案例:随着市场竞争日益激烈,运营商的运营策略正逐步从以业务为中心向以客户为中心转变,开展新业务,推出灵活的资费策略,多业务集中统一管理,提供准确的账单,让客户明明白白地消费。其中,重要的一环就是要求计费准确,实时。经研究发现,基于键树索引的数据组织方法用在实时计费处理中,能显著提高实时计费性能。对于客户资料也是采用键树索引进行组织,可以快速的查找到用户。

可以体现的计算思维

键树把关键字的查找转化为一棵树,通过树的搜索可以确定关键字,这个方法能够将一个问题由难化易,由繁化简,体现了计算思维的转化特点。