预排序遍历树算法
更新日期:
预排序遍历树算法
如题所示,这是一种为查询而生的遍历树算法,如果业务需求要求查询的场景高于、多于增删改,可以考虑此算法,该算法会牺牲掉一些插入、删除的性能。
算法简单概括:类二叉树先序遍历,将树上的每个节点标示left、right、level、parent属性(parent可以更方便画出树结构),查询通过left和right取值,一般情况可以通过一条sql查询和排序出整个需要的树节点。
该算法在网络上有很多资源。
- 查询某段树的节点数
- 查询整树
- 新增、删除节点
- 比较常用的树结构——邻接表
通过先序遍历算法,预置每个节点left、right后的树如下图所示:图片转自网络
1.查询某段树的节点数
(顶点right-顶点left+1)/2
例如图中B、C、D、E、F段树的节点数:(11-2+1)/2=5
2.查询整树
顶点left <= left && 顶点right >= right
例如图中B、C、D、E、F树:
select * from tree where left>=2 and right<=11 order by left
然后根据level可以和父子关系可以很清晰的画出整个树。
3.新增、删除节点
如下图新增X节点:图片转自网络
通过图可以看到,新增点位X左边的left和right都不变,右边所有节点都需要update。
更新公式:
X右边所有节点的left+2、right+2,
X节点由于没有子节点,所有left=左边临界点right+1、right=自己的left+1
1 G节点的右参数为13
2 变更所有的受影响的节点,给新节点腾出空位子
所有左节点比G节点大的,都增加2
update tree set lft=lft+2 where lft>12
所有右节点比G节点大的,都增加2
update tree set rgt=rgt+2 where rgt>13
4.比较常用的树结构——邻接表
这种结构是现实中最常用而且最容易理解的,简单来讲就是每个节点标示一下自己的parent ,根据parent递归画出树结构,需要多次遍历。但是更新会更加方便。