您现在的位置是:首页 > 正文

数据结构和算法:预排序遍历树算法(MPTT)

2024-01-31 00:18:06阅读 0

一、多级分类问题

在实际开发的过程中,会经常遇到多级分类的问题。譬如,导航栏、菜单、商品种类、多级联动、字典表等等的多级分类问题。这时可以新增一个 pid 字段进行数据关联,它本质上其实就是一棵树。树就可以很好的解决多级分类的子分类查询。

在这里插入图片描述

但是这种方式有一个致命的问题:查询效率过低!!!

当我们在程序里查询某个子节点时,要先从根节点进行递归查询,时间复杂度是 O(n)

那么有没有一种方式,改进树的查询效率呢?答案是肯定的!很多树都在标准的树上进行改进过,比如二叉树、红黑树、堆等等。但这都不是重点,今天要分享的是 预排序遍历树算法(MPTT)

MPTT 正是为了解决多层级关系数据的查询效率问题,它的时间复杂度竟然能高效到一个常量,即 O(1)。是不是很不可思议,接下来就让我们一起学习预排序遍历树算法,看下它到底是如何实现的。

二、预排序遍历树

预排序遍历树算法全称是:Modified Preorder Tree Traversal 简称 MPTT

1. ORM 映射
class Tree(Base, BaseNestedSets):

    __tablename__ = 'tree'

    id = Column(Integer, primary_key=True, autoincrement=True)
    name = Column(String(8), nullable=True, default=None)

    def __repr__(self):
        return f'<Tree(id={self.id}, name={self.name})>'
2. MPTT 分析

在上述代码中,只定义了两个字段: idname。但是数据库里面却额外多出了 5个字段,分别是: lftrgtleveltree_idparent_id

这些多出来的字段就是为了定义树的结构和层级。下面我们就来分析一下,每个字段的作用是什么。

  • tree_id:树的 id,用来区分数据库中众多树的某一颗树。

  • level:一颗标准的树会有高度、深度、层级,根节点的层级是 1,子节点的层级是父节点层级加 1

  • parent_id:父 id,节点的父级 id,根节点没有父节点,所以值为 NULL

  • lft:节点左值。

  • rgt:节点右值。

节点的左值和右值是 MPTT 的核心,也是这个算法实现特别巧妙的地方,将树遍历的时间复杂度降为 O(1)。接下来就重点分析一下左值与右值是如何进行树遍历的。

一颗标准的树结构:

在这里插入图片描述

数据库数据对应关系:

在这里插入图片描述

数据层次结构:

- 【1】
- - 【2】
- - - 【3】
- - 【4】
- - - 【5】
- - - 【6】
- - 【7】
- - - 【8】
- - - - 【9】
- - - 【10】
- - - - 【11】

遍历整棵树

遍历整棵树只需要查找 tree_id 等于 1 的条件即可

找到某节点下所有的子孙节点

查找节点 4 的所有子孙节点,以 4 作为参考点。左值大于 6 且右值小于 11 的所有子孙节点,就是节点 4 的所有子孙节点。

找到某节点下所有的子节点

查找节点 1 的所有子节点,以 1 作为参考点。tree_id 等于 1level 等于 2

查找某节点的路径

查找节点 9 的所有上级路径,以 9 作为参考点。左值小于 14 且右值大于 15 的所有节点,就是节点 ``9的路径。结果是:1 -> 7 -> 8 -> 9`。

3. MPTT 平衡算法

MPTT 在遍历的时候很快,但是其他的操作就会变得很慢,所以使用 MPTT 要尽量避免查询之外的其他操作。

在这里插入图片描述

那为什么除了查询操作其他的操作会很慢呢?

这是因为节点在插入、更新(移动)、删除会破坏树的平衡。所以在做这些操作的时候需要对数进行调整,达到新的平衡。

新增

以新增节点操作为例,算法可分解为以下几个步骤:

  • 如果要在不存在的树中新增节点,即要创建一颗新树。那么它是没有 parent_id 的,所以 parent_id 值为 NULLlevel1tree_id 是根据已有树的最大 tree_id1

  • 如果要在已存在的树中新增节点。那么它的 parent_id 是父节点的 idlevel 是父节点的 level1tree_id 和父节点保持一致。

  • 修复被破坏平衡的其他节点的左值。大于 parent_id 右值的所有节点的左值加 2

  • 修复被破坏平衡的其他节点的右值。大于等于 parent_id 右值的所有节点的右值加 2

删除

和增加类似,只不过删除一个节点以后对左值和右值进行相反的操作,即减 2

更新(移动)

更新(移动)其实就是删除一个老节点,再新增一个新节点,具体算法参考上面的例子。

三、标准树和预排序遍历树的优劣对比

  • 标准树:适用于增删 操作较多的场景,每次删改只需要修改一条数据。在查询方面,随着分类层级的增加邻接表的递归查询效率逐渐降低。

  • 预排序遍历树:适用于查询操作较多的场景,查询的效率不受分类层级的增加的影响,但是随着数据的增多,每增删数据,都要同时操作多条受影响数据,执行效率逐渐下降。

没有完美的算法,在实际开发过程中具体要选择哪一种存储结构和算法,需要根据具体的应用场景来做选择。

网站文章

  • 华为matebook重装系统后,指纹模块失效,无法识别指纹设备,华为电脑管家无法解决

    Windows hello 指纹无法使用,重新安装指纹驱动没用。 解决方法,按如下顺序重新安装驱动,每次安装时如果需要重启,请立即重启,确保按顺序安装完成。 1-主板芯片组驱动程序 2-串口驱动程序 3-ME驱动程序(注意不是ME固件) 4-SGX驱动程序 5-指纹驱动程序 指纹驱动安装成功后,重启,即可正常使用指纹,设备管理器里可以看到生物识别设备。

    2024-01-31 00:18:01
  • Python + Requests + Scrapy + Fcntl: 双引擎下载小说(简述)

    Python + Requests + Fcntl: 双引擎下载小说前言关于双引擎原理流程库RequestsScrapyFcntl前言略关于双引擎原理流程库Requests导入包含requests、自...

    2024-01-31 00:17:53
  • function处理所有通道

    调用时(规则)select row2fft(channelall,info) from streamReadWavsources以前返回的map有4个元素:channel0, channel1,cha...

    2024-01-31 00:17:24
  • JS获取两个日期间的月份和天数

    【代码】JS获取两个日期间的月份和天数。

    2024-01-31 00:17:17
  • Linux技巧

    0001 修改主机名(bjchenxu) vi /etc/sysconfig/network,修改HOSTNAME一行为&quot;HOSTNAME=主机名&quot;(没有这行?那就添加这一行吧),...

    2024-01-31 00:17:11
  • (故障集)——新安装的Ubuntu系统重启后ens33没了

    (故障集)——新安装的Ubuntu系统重启后ens33没了

    net-tools是一个工具包,其中包含构成Linux网络基础的一系列程序。从网上看到使用ifconfig -a可以显示lo和ens33网卡,然后使用。如果习惯使用旧的ifconfig命令,则需要安装。因为我的ubuntu版本是22.04版本,使用。...

    2024-01-31 00:17:06
  • Linux——搭建Samba服务器 最新发布

    为实现linux和windows文件共享,可以在linux安装Samba服务,可实现在windows上打开linux共享目录的功能。

    2024-01-31 00:16:36
  • 个人技能总结10:微信开发

    参考:http://www.cnblogs.com/fengzheng/p/5023678.html 一.开始前准备 1.公网服务器的准备 尽量不要使用ip那种的会影响后面好多功能。实际开发可自行购买云服务器和域名。域名不可以有端口号即只可用80端口。 附录1:使用ngrok做内网穿透 A)登录ngrok国内网址:https://www.ngrok.cc/注册账号,申请隧道。 B...

    2024-01-31 00:16:29
  • VueJs的组件化

    VueJs的组件化

    组件化: 目的:让页面的元素的使用性和复用性更高。 使用: 1.通过Vue.extend()声明组件 2.将组件注册到Vue容器里面 3.声明Vue管理边界 定义: 组件就是将一些html+css+js封装成了一个整体,通过整体之间嵌套实现页面构建 1.声明组件: Vue.extend({}) 实现对象里面的一些参数 达到组装组件过程 Vue.extend() Vue是个构造

    2024-01-31 00:16:21
  • 《Effective Java》阅读笔记 13使类和成员的可访问性最小化

    《Effective Java》阅读笔记 13使类和成员的可访问性最小化

    1.信息隐藏区分一个组件设计得好不好,唯一重要的因素在于,它对于外部的其他组件而言,是否隐藏了其内部数据和其他实现细节。设计良好的组件会隐藏所有的实现细节,把API与实现清晰地隔离开来。然后模块之间只...

    2024-01-31 00:15:51