数据结构——2-3查找树特性(二)

简介: 数据结构——2-3查找树特性

3.4 向一个父结点为3-结点的3-结点中插入新键


当我们插入的结点是3-结点的时候,我们将该结点拆分,中间元素提升至父结点,但是此时父结点是一个3-结点,插入之后,父结点变成了4-结点,然后继续将中间元素提升至其父结点,直至遇到一个父结点是2-结点,然后将其变为3-结点,不需要继续进行拆分。

1.png


3.5 分解根结点


当插入结点到根结点的路径上全部是3-结点的时候,最终我们的根结点会编程一个临时的4-结点,此时,就需要将根结点拆分为两个2-结点,树的高度加1。

1.png


4. 2-3树的性质


通过对2-3树插入操作的分析,我们发现在插入的时候,2-3树需要做一些局部的变换来保持2-3树的平衡。


一棵完全平衡的2-3树具有以下性质:


任意空链接到根结点的路径长度都是相等的。

4-结点变换为3-结点时,树的高度不会发生变化,只有当根结点是临时的4-结点,分解根结点时,树高+1。

2-3树与普通二叉查找树最大的区别在于,普通的二叉查找树是自顶向下生长,而2-3树是自底向上生长。


5. 2-3树的应用


直接实现2-3树比较复杂,因为:


需要处理不同的结点类型,非常繁琐;

需要多次比较操作来将结点下移;

需要上移来拆分4-结点;

拆分4-结点的情况有很多种;


2-3查找树实现起来比较复杂,在某些情况插入后的平衡操作可能会使得效率降低。但是2-3查找树作为一种比较重要的概念和思路对于红黑树、B树和B+树非常重要。

相关文章
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
108 64
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
2月前
|
存储
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(一)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
2月前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
|
3月前
|
JSON 前端开发 JavaScript
一文了解树在前端中的应用,掌握数据结构中树的生命线
该文章详细介绍了树这一数据结构在前端开发中的应用,包括树的基本概念、遍历方法(如深度优先遍历、广度优先遍历)以及二叉树的先序、中序、后序遍历,并通过实例代码展示了如何在JavaScript中实现这些遍历算法。此外,文章还探讨了树结构在处理JSON数据时的应用场景。
一文了解树在前端中的应用,掌握数据结构中树的生命线