Forward, Backward, Backward+三种求SLCA的方法
A simple XML document
给出k个关键字的IDList,记录所有包含(直接、间接包含)关键字的ID号
对于上面的XML文档,给出查询Q={XML, Tom},关键字的IDList如下图所示
求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号小为止。