专栏首页算法无遗策动画 | 什么是2-3-4树?

动画 | 什么是2-3-4树?

画了一系列树的动画,从二分搜索树,到AVL树,再到2-3树,再到基于2-3树的红黑树,都可以发现这些树都跟二叉查找树很像啊。

嘿嘿!二分搜索树就是二叉查找树;AVL树也是一颗二分搜索树,只多了高度差的限制;2-3树虽满足二分搜索树的性质,但不是一颗二分搜索树,2-3树由2-节点和3-节点组成的,满足了完美平衡性;基于2-3树的红黑树就是希望不要有3-节点,将3-节点转换成二叉,两个元素之间由红链接相连,并约定谁是子节点谁是红的,如下图:

本篇文章还会继续介绍满足二分搜索树性质的一棵树,它是2-3-4树,和2-3树一样也不是一颗二分搜索树。它在2-3树的基础上可以存储4-节点,4-节点由三个元素组成,有四个子树。

查找元素

和二分搜索树一样,根据元素的大小来决定查找的方向。要判断一个元素是否存在,我们首先将待查找元素和根节点逐一比较,如果它和当前节点中的一个元素相等,就返回查找命中;如果它比当前节点任一元素要大,就选择右递归进行下一个节点;如果它比当前节点任一元素要小,就选择左递归进行下一个节点;直到树底下的空节点,返回查找未命中。

插入元素

我们知道2-3树树底下最多是3-节点,可以直接插入元素然后再判断是否是4-节点,如果是向2-节点插入一个元素,变成3-节点无需分解;如果是向3-节点插入一个元素变成4-节点,进行向上变换将中间的键合并到父节点,如果父节点也变成4-节点,也接着继续分解4-节点,直到根节点,根节点也是4-节点,也接着分解,树高+1。

而2-3-4树的插入算法不一样,它没有向上进行变换分解4-节点的过程,因为2-3-4树可以存储4-节点。不过插入之前,进行查找命中的时候所过路径都要分解4-节点,如果查找未命中,则在此空节点插入一个元素;如果查找命中,说明2-3-4树是存在这个数的,则直接返回,之前的4-节点分解就分解了,没有必要再次合并4-节点。

插入算法同样也需要进行分解4-节点算法,不过是由向上变换变成了向下变换。

沿着链接向下进行变换分解4-节点,分为三种情况:

1)4-节点作为根节点,分解;

2)父节点为2-节点,当前节点为4-节点;

3)父节点为3-节点,当前节点为4-节点。

树底下插入一个元素只有两种情况了:向2-节点中插入元素和向3-节点中插入元素。

动画:插入算法

http://mpvideo.qpic.cn/0bf2yqaaaaaaayaopfqkgjpfbrgdadcaaaaa.f10002.mp4?dis_k=84ff6b6477299881a02a9e8a9c4d436e&dis_t=1579076956

删除元素

既然是2-3-4树满足二分搜索树性质的,查找算法、插入算法和删除算法很多都是相似的。我们回忆一下二分搜索树的删除算法,它在删除任何一个非叶子节点时,都会获取右子树的最小叶子节点去代替待删除元素,然后进行右子树的删除最小叶子节点。

所以,2-3-4树也是一样,先进行命中查找,如果查找命中,就获取待删除元素的直接后继节点去替换待删除元素,然后进行右子树的删除最小元素。不过在查找待删除元素的同时,需要沿着左链接或者右链接向下进行变换,所过路径分解4-节点。

删除最小元素

从树底下删除一个元素,如果不是2-节点是很好删除的,从3-节点删除一个元素变成2-节点和从4-节点删除一个元素变成3-节点,都不会影响整个2-3-4树的绝对平衡性。如果从2-节点删除一个元素,而这个2-节点只有一个元素,删除之后这个节点变成一条空链接,会破坏树的绝对平衡性。

所以在沿着左链接向下进行变换的时候,确保当前节点不是2-节点(除了根节点)。如果当前节点是2-节点,可以先向兄弟节点借一个位置;如果兄弟节点也是2-节点,没法借,可以借父节点的一个位置。

但借的先后顺序不能弄错了,如果先向父节点借来一个位置,不清楚兄弟节点有多少子树会到时候没法分解的。例如兄弟节点是4-节点,当前节点、父节点一个位置和兄弟节点合并就变成了6-节点,比4-节点分解更加麻烦。

沿着左链接向下进行变换可以分为三种情况:

1)当前节点不是2-节点,跳过;

2)当前节点是2-节点,兄弟节点是2-节点,将当前节点、父节点的最小元素和兄弟节点合并成4-节点;

3)当前节点是2-节点,兄弟节点不是2-节点,将兄弟节点的最小元素移到父节点,父节点的最小元素移到当前节点(兄弟节点的最小元素要比父节点的最小元素要大,不是同一个元素)。

动画:删除最小算法

http://mpvideo.qpic.cn/0bf2xyaaaaaameaoomikgjpfbpwdac7aaaaa.f10002.mp4?dis_k=b94d502d682b39056ff23bfd4d9885ef&dis_t=1579076956

删除任意元素

删除任意元素首先要查找到这个元素,如果查找未命中则忽略之;如果查找命中,通过右子树中序遍历找到第一个元素(右子树最小元素),将这个元素直接替换掉待删除元素。

删除任意元素除了沿着左链接向下进行变换,还需要沿着右链接向下进行变换。沿着右链接向下进行变换也分为三种情况,将最小元素改为最大元素:

1)当前节点不是2-节点,跳过;

2)当前节点是2-节点,兄弟节点是2-节点,将当前节点、父节点的最大元素和兄弟节点合并成4-节点;

3)当前节点是2-节点,兄弟节点不是2-节点,将兄弟节点的最大元素移到父节点,父节点的最大元素移到当前节点(父节点的最大元素要比兄弟节点的最大元素要大,不是同一个元素)。

动画:删除任意算法

http://mpvideo.qpic.cn/0bf23qaaaaaa3aaoriikgfpfbxgdadoaaaaa.f10002.mp4?dis_k=7488c4584dd48678705e924c2ff3629d&dis_t=1579076956

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    我脱下短袖
  • 动画 | 什么是2-3树?(修改删除操作方式)

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

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

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

    我脱下短袖
  • ignite TCP发现原理

    节点顺序 - 每个节点的内部属性(对于TcpDiscoverySpi,它只是一个统一增加的数字)。

    lilihongjava
  • 《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配

    《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配 (原创内容,转载请注明来源,谢谢) 一、概述 redis集群是...

    用户1327360
  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移

    《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移 (原创内容,转载请注明来源,谢谢) 1、概述 redis集群的...

    用户1327360
  • 红黑树算法

    前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

    机器学习算法工程师
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月
  • 像管理 Pod 一样管理 Node | TKE 节点池全面上线

    晏子怡,腾讯云产品经理,目前负责TKE集群、网络及调度模块。 从 K8s 的声明式设计理念谈起 Pod 模板 K8s 最优雅精妙的一个设计理念在于声明式  A...

    腾讯云原生

扫码关注云+社区

领取腾讯云代金券