文档章节

预排序遍历树算法的图文解释

BearCatYN
 BearCatYN
发布于 2015/04/28 16:12
字数 548
阅读 741
收藏 2
点赞 1
评论 0

这个算法有如下几个数据结构 
1 lft 代表左 left 
2 rgt 代表右 right 
3 lvl 代表所在的层次 level 

下面这个图是一个典型的结构 
 

我们先看一些使用方法 
1 查看整个树(A)有多少节点(包含自己) 
直接看根节点就行了 (right-left+1)/2 = (20-1+1)/2 = 10 
这个数有10个节点 

2 查看从节点A到E的路径 
select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft 

得到的结果是A,B,D,E 这4个节点的数据,且按照访问路径的顺序 

如果2个节点之间不是上下级的关系,则查询没有结果 

反向也是一样的,可以拿到底部一个节点,到上级节点的路径 
select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft desc 
唯一的区别就是排序是反向的就行了。 

3 得到某个节点下面的所有节点,且按照树状结构返回 
我们用B做例子 
select * from tree where lft>2 and right<11 order by lft 
拿到的结果是 C,D,E,F,而且顺序也是正确的。 

4 拿到所有下2级的子节点 
我们A做例子,这次加上了lvl的参数,因为A的level是1,所以我们查询level不大于3的。 
select * from tree where lft>2 and right<11 and lvl<=3 order by lft 



下面看我们新增加一个节点的方法。 
我们在根节点的下面,G节点的右侧增加一个X节点 
 
我们要做的工作就是 
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 
3 新节点放在空位子上,lft=14,rgt=15 
这样就完成了一个新节点的增加操作。

本文转载自:http://blog.chinaunix.net/uid-21586638-id-3875107.html

共有 人打赏支持
BearCatYN
粉丝 27
博文 157
码字总数 11947
作品 0
朝阳
程序员
PHP+Mysql树型结构(无限分类)数据库设计的2种方式实例

我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种: 1. 领接表的方式; 2. 预排序遍历树方式; 假设树状结构如下图: 领接表方式 ...

我心中有猛狗 ⋅ 2016/10/29 ⋅ 0

树状分类结构,数据库构建(预排序历遍算法)

树状结构的数据保存在数据库中的常用方法有一下两种: 1、邻接表(adjacency list model) 2、预排序遍历树算法(modified preorder tree traversal algorithm) 用一下的例子讨论这两种方法的差...

liangyx ⋅ 2013/01/02 ⋅ 6

python机器学习案例系列教程——LightGBM算法

全栈工程师开发手册 (作者:栾鹏) python教程全解 安装 gitup网址:https://github.com/Microsoft/LightGBM 中文教程 http://lightgbm.apachecn.org/cn/latest/index.html lightGBM简介 xg...

luanpeng825485697 ⋅ 05/08 ⋅ 0

机器学习基础之 三大神器GBDT、XGBoost、LightGBM

本文主要简要的比较了常用的boosting算法的一些区别,从AdaBoost到LightGBM,包括AdaBoost,GBDT,XGBoost,LightGBM四个模型的简单介绍,一步一步从原理到优化对比。 AdaBoost原理 原始的AdaBo...

secondlieutenant ⋅ 04/23 ⋅ 0

面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛 ⋅ 2017/12/22 ⋅ 0

(转) 坚持完成这套学习手册,你就可以去 Google 面试了

C++ —— 不使用内建的数据类型。C++ —— 使用内建的数据类型,如使用 STL 的 std::list 来作为链表。Python —— 使用内建的数据类型(为了持续练习 Python),并编写一些测试去保证自己代...

wangxiaocvpr ⋅ 2016/10/12 ⋅ 0

Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer ⋅ 2017/12/20 ⋅ 0

Python: Trie树实现字典排序

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。T...

陈亦 ⋅ 2014/02/18 ⋅ 4

树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker ⋅ 2015/08/14 ⋅ 0

php:树形结构的算法

从喜悦村上转载,以前也读过此文,讲述得还是比较清楚的。 产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据? 在PHP的应用中,提供后台...

mac_zhao ⋅ 2015/06/25 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

R计算IV

参考文章 #读取文件 rawdata = read.csv("/path/to/csv/file",header=T) colnames(rawdata)[18] <- "y" //重命名因变量y #数据分区 训练集测试集 trainIdx <- sample(nrow(rawdata), round(......

火力全開 ⋅ 20分钟前 ⋅ 0

SQL老司机,在SQL中计算 array & map & json数据

摘要: 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primitive类型的数据。 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primi...

阿里云云栖社区 ⋅ 20分钟前 ⋅ 0

SQL老司机,在SQL中计算 array & map & json数据

摘要: 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primitive类型的数据。 场景 通常,我们处理数据,一列数据类型要么是字符串,要么是数字,这些都是primi...

猫耳m ⋅ 31分钟前 ⋅ 0

关于ireport自定义变量类型为list的时候

自己摸石头过河,我真的应该去趟市中心图书馆,借本真正靠谱的教材 网上的东西,只有0.01%是有用的,还有0.99%是垃圾,剩下的99%是垃圾的复制品。。 哎!~ 问题是这样的,报表带sql,从db中获...

炑炑milina ⋅ 32分钟前 ⋅ 0

Spring mvc ContextLoaderListener 原理解析

对于熟悉Spring MVC功能,首先应从web.xml 开始,在web.xml 文件中我们需要配置一个监听器 ContextLoaderListener,如下。 <!-- 加载spring上下文信息,最主要的功能是解析applicationContex...

轨迹_ ⋅ 32分钟前 ⋅ 0

阿里云发布企业数字化及上云外包平台服务:阿里云众包平台

摘要: 阿里云正式发布旗下众包平台业务(网址:https://zhongbao.aliyun.com/),支持包括:网站定制开发,APP、电商系统等软件开发,商标、商品LOGO、VI、产品包装设计、营销推广、大数据人...

阿里云官方博客 ⋅ 34分钟前 ⋅ 0

Redis安装异常解决办法

官网地址:http://redis.io/ 官网下载地址:http://redis.io/download 1. 下载Redis源码(tar.gz),并上传到Linux 2. 解压缩包:tar zxvf redis-2.8.17.tar.gz 3. 进入解压缩后的文件夹:c...

slagga ⋅ 38分钟前 ⋅ 0

006. 深入JVM学习—年轻代

1. 年轻代图片 年轻代(Young)属于JVM堆内存空间的一个组成部分 所有使用关键字new新实例化的对象一定会在伊甸园区进行保存,而对于存活区保存的一定是已经在伊甸园区存在一段时间并且经过了...

影狼 ⋅ 39分钟前 ⋅ 0

如何成为一个合格的程序员

偶尔的,我会被人问道:如何成为一名优秀的程序员,更或者,如何成为一名程序员。每次人们问起,我都力图给出不同的答案。因此,我的答案是各种各样的。下面就是我认为的成为一名优秀的程序员...

柳猫 ⋅ 40分钟前 ⋅ 0

cups error_log日志暴增

日志内容 File \"/usr/lib/cups/notifier/dbus\" has insecure permissions 解决(未验证适用范围) sudo service cups stopsudo rm /etc/cups/subscriptions.conf*sudo rm -r /var/cac......

一介码夫_Hum ⋅ 44分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部