专栏首页算法无遗策动画 | 什么是2-3树?(修改删除操作方式)

动画 | 什么是2-3树?(修改删除操作方式)

我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平衡状态。频繁的左旋转和右旋转操作一定会影响整个AVL树的性能,除非是平衡与不平衡变化很少的情况下,否则AVL树所带来的搜索性能提升不足以弥补平衡树所带来的性能损耗。

那有没有绝对平衡的一种树呢?没有高度差也不会有平衡因子,没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树,任意节点到它所有的叶子节点的深度都是相等的。

2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质,但它不属于二分搜索树。

2-3树定义

一颗2-3树或为一颗空树,或有以下节点组成:

2-节点,含有一个元素和两个子树(左右子树),左子树所有元素的值均小于它父节点,右子树所有元素的值均大于它父节点;

3-节点,还有两个元素和三个子树(左中右子树),左子树所有元素的值均小于它父节点,中子树所有元素的值都位于父节点两个元素之间,右子树所有元素的值均大于它父节点。

2-3树查找元素

2-3树的查找类似二分搜索树的查找,根据元素的大小来决定查找的方向。要判断一个元素是否存在,我们先将待查找元素和根节点比较,如果它和其中任意一个相等,那查找命中;否则根据比较的结果来选择查找的方向。

2-3树插入元素

插入元素首先进行查找命中,若查找命中则不予插入此元素,如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中,则在叶子节点中插入这个元素。

空树的插入很简单,创建一个节点即可。如果不是空树,插入的情况分为4种:

1. 向2-节点中插入元素;

2. 向一颗只含有一个3-节点的树中插入元素;

3. 向一个父节点为2-节点的3-节点中插入元素;

4. 向一个父节点为3-节点的3-节点中插入元素。

向2-节点中插入元素

如果未命中查找结束于2-节点,直接将2-节点替换为3-节点,并将待插入元素添加到其中。

向一颗只含有一个3-节点的树中插入元素

如果命中查找结束于3-节点,先临时将其成为4-节点,把待插入元素添加到其中,然后将4-节点转化为3个2-节点,中间的节点成为左右节点的父节点。如果之前临时4-节点有父节点,就会变成向一个父节点为2-节点的3-节点中插入元素,中间节点与父节点为2-节点的合并。

向一个父节点为3-节点的3-节点中插入元素

插入元素后一直向上分解临时的4-节点,直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点,则进行分解根节点,此时树高+1(只有分解根节点才会增加树高),下面动画2-3树插入会出这个例子。

动画:2-3树插入

2-3树删除

算法4红黑树删除最小键这一小结里没有特别详细地介绍,但给到了沿着左链接向下进行变换的三种情况:

1. 如果左子节点不是2-节点,完成;

2. 如果左子节点是2-节点,而兄弟节点不是2-节点,将兄弟节点的最小元素移到父节点,父节点的最小元素移到左子节点;

3. 如果左子节点是2-节点,而兄弟节点是2-节点,则左子结点、父节点中最小的元素和兄弟结点合并成4-结点。

删除最小元素

我们注意到在叶子节点不是2-节点的时候,删除一个元素是很简单的,而且删除时不考虑自平衡处理。如果删除一个2-节点会留下一个空节点,破坏了2-3树的绝对平衡。所以,为了保证不会删除一个2-节点,可以设定最左边或者最右边进行向下变换节点。这里设置沿最左边的链接,进行向下变换的三种情况正是如上图中,左子节点的父节点除了根节点都会变换成3-节点或4-节点。

删除任意元素

删除任意元素需要进行命中查找。如果查找未命中则忽略之;如果查找命中则像二分搜索树删除任意元素,将带删除元素右子树的最小元素替换到待删除元素上,然后对右子树进行删除最小元素。

动画:2-3树删除

-----END-----

本文分享自微信公众号 - 算法无遗策(gh_6519e8c0cb55),作者:我脱下短袖

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动画 | 什么是红黑树?(基于2-3树)

    学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

    我脱下短袖
  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是红黑树?(与2-3-4树等价)

    二分搜索树是为了快速查找而生,它是一颗二叉树,每一个节点只有一个元素(值或键值对),左子树所有节点的值均小于父节点的值,右子树所有的值均大于父节点的值,左右子树...

    我脱下短袖
  • 【从二叉树到红黑树】清晰理解红黑树的演变---红黑的含义

    网上关于红黑树的博文很多,但是多是上来即讲定义,未说其所以然,难以理解且无所营养,甚者示例图有误且概念模糊的比比即是;

    云服务器最新
  • Zookeeper系列(5) —— Zookeeper 常用的客户端操作命令

    创建节点的命令格式 create [-s] [-e] /path data acl

    求和小熊猫
  • 第15期:索引设计(索引组织方式 B+ 树)

    谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。

    爱可生开源社区
  • 动图展示,让你彻底理解红黑树!

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    业余草
  • 数据结构:堆(Heap)

    堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

    sunsky
  • 动图演示:如何彻底理解红黑树?

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    架构师修炼
  • 使用图进行特征提取:最有用的图特征机器学习模型介绍

    从图中提取特征与从正常数据中提取特征完全不同。图中的每个节点都是相互连接的,这是我们不能忽视的重要信息。幸运的是,许多适合于图的特征提取方法已经创建,这些技术...

    deephub

扫码关注云+社区

领取腾讯云代金券