文章目录
  1. 1. 预排序遍历树算法

预排序遍历树算法


如题所示,这是一种为查询而生的遍历树算法,如果业务需求要求查询的场景高于、多于增删改,可以考虑此算法,该算法会牺牲掉一些插入、删除的性能。

算法简单概括:类二叉树先序遍历,将树上的每个节点标示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节点

通过图可以看到,新增点位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递归画出树结构,需要多次遍历。但是更新会更加方便。

资料参考:
http://my.oschina.net/bootstrap/blog/166805

http://m.oschina.net/blog/99604

文章目录
  1. 1. 预排序遍历树算法