算法5-1:平衡查找树之二三树

平衡查找树的目标是实现查找、插入、删除操作在最坏情况下的复杂度均为logN。

本节将介绍二三查找树。

二三树中有两种节点:

  • 二节点对应一个键,有两个子节点
  • 三节点对应两个键,有三个子节点

二三查找树非常平衡,每个空节点到根节点的距离都是一样的 。

查找操作

在二三树中查找一个键的时候有以下规则:

  • 如果是二节点,二节点对应1个值,如果要查找的值比该节点对应的值小,就往左侧深入,反之亦成
  • 如果是三节点,三节点对应2个值,如果比两个值都小,就往左侧深入,如果介于两个值之间,就往中间深入,如果比两个值都大,就往右侧深入。

插入操作

根据查找操作的规则,先定位到需要插入的节点。如果是二节点,那么将二节点中增加一个键成为三节点。如果是三节点,在三节点中增加1个键成为四节点。由于四节点不允许在二三树中出现,因此需要分解成两个二节点,并且把中间的键提取到父节点中。下图展示四节点分解的过程:

现在要在这棵树中插入一个值7

首先根据查找操作的规则定位到要插入的节点,定位之后是如图所示的节点

由于该节点是三节点,因此插入一个键,使它成为四节点

由于四节点不允许在2-3树中存在,因此需要将其分解为两个二节点,并把中间的键7提到父节点中

这样插入操作就完成了

性能

2-3树的高度介于lgN和log_3(N)之间,因此能够保证所有的操作复杂度均在logN以下

实现

二三树的实现非常复杂,因为要判断每个节点的类型,插入节点的时候还需要判断插入节点的位置,需要考虑的情况非常多。

算法5-1:平衡查找树之二三树,布布扣,bubuko.com

时间: 06-17

算法5-1:平衡查找树之二三树的相关文章

转 浅谈算法和数据结构: 十 平衡查找树之B树

前面讲解了平衡查找树中的2-3树以及其实现红黑树.2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key. 维基百科对B树的定义为"在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树.与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作.B-tree算法减少定位记录时所经历的中间过程,从而

浅谈算法和数据结构: 十 平衡查找树之B树

转载自 http://www.cnblogs.com/yangecnu/p/3632027.html 浅谈算法和数据结构: 十 平衡查找树之B树 前面讲解了平衡查找树中的2-3树以及其实现红黑树.2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key. 维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可以拥

浅谈算法和数据结构: 七 二叉查找树 八 平衡查找树之2-3树 九 平衡查找树之红黑树 十 平衡查找树之B树

http://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html 前文介绍了符号表的两种实现,无序链表和有序数组,无序链表在插入的时候具有较高的灵活性,而有序数组在查找时具有较高的效率,本文介绍的二叉查找树(Binary Search Tree,BST)这一数据结构综合了以上两种数据结构的优点. 二叉查找树具有很高的灵活性,对其优化可以生成平衡二叉树,红黑树等高效的查找和插入数据结构,后文会一一介绍. 一 定义 二叉查找树(B

【经典数据结构】B树与B+树

本文转载自:http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html 维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树.与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作.B-tree算法减少定位记录时

B树与B+树

转自:http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html 前面讲解了平衡查找树中的2-3树以及其实现红黑树.2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key. 维基百科对B树的定义为"在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可

【经典数据结构】B树与B+树(转)

本文转载自:http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html 维基百科对B树的定义为"在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据.对其进行排序并允许以O(log n)的时间复杂度运行进行查找.顺序读取.插入和删除的数据结构.B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树.与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作.B-tree算法减少定位记录时

浅谈算法和数据结构: 九 平衡查找树之红黑树

原文:浅谈算法和数据结构: 九 平衡查找树之红黑树 前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度.但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息.红黑树中将节点之间的链接分为两种不同类型,

《 常见算法与数据结构》平衡查找树(1)—— 2-3查找树(附动画)

本系列文章主要介绍常用的算法和数据结构的知识,记录的是<Algorithms I/II>课程的内容,采用的是"算法(第4版)"这本红宝书作为学习教材的,语言是java.这本书的名气我不用多说吧?豆瓣评分9.4,我自己也认为是极好的学习算法的书籍. 通过这系列文章,可以加深对数据结构和基本算法的理解(个人认为比学校讲的清晰多了),并加深对java的理解. 2-3树介绍 我们上回说到二叉查找树已经很接近我们的目标了,在很多情况下性能都很不错,但是唯独在删除上不行,一旦删除操作做

【转】浅谈算法和数据结构: 九 平衡查找树之红黑树

http://www.cnblogs.com/yangecnu/p/3627386.html 前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度.但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息.