数据结构——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+树非常重要。

相关文章
|
2月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
58 0
|
3月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
128 64
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
73 5
|
2月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
111 16
|
2月前
|
算法
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
66 0
|
3月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
33 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
3月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
3月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
3月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
3月前
|
存储
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(一)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解