首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

Forward, Backward, Backward+三种求SLCA的步骤

2013-10-08 
Forward, Backward, Backward+三种求SLCA的方法Asimple XML document给出k个关键字的IDList,记录所有包含(

Forward, Backward, Backward+三种求SLCA的方法

 Forward, Backward, Backward+三种求SLCA的步骤

                          A   simple XML document    

     

给出k个关键字的IDList,记录所有包含(直接、间接包含)关键字的ID号

对于上面的XML文档,给出查询Q={XML, Tom},关键字的IDList如下图所示

Forward, Backward, Backward+三种求SLCA的步骤

求SLCA的本质就是在K个IDLlist中求集合交集

(1)Forward:

         从前往后进行扫描,从K个IDList里选取最大的id号到其他k-1个IDList里进行二

         分查找,如果都找到了,说明当前的id是一个CA结点,接着找下一个CA结点,

         用下一个CA结点判断前一个CA结点是否为SLCA结点,具体方法是判断祖先后

         代关系。

 

(2)Backward:

         从后往前进行扫描,从K个IDList里选取最小的id号到其他k-1个IDList里进行二

         分查找,如果都找到了,说明当前的id是一个CA结点,且一定为SLCA结点,

         当找到一个CA结点,则从最短倒排中删除其所有的祖先结点。。。接着找下

         一个CA结点。
 

(3)Backward+:

         对Backward进行改进,缩小二分查找的范围,通过找父亲结点ID号,直到找

         到某个父亲节点的ID号比当前要查找的ID号小为止。

热点排行