your text

本系列文章主要介绍常用的算法和数据结构的知识,记录的是《Algorithms I/II》课程的内容,采用的是“算法(第4版)”这本红宝书作为学习教材的,语言是java。这本书的名气我不用多说吧?豆瓣评分9.4,我自己也认为是极好的学习算法的书籍。
通过这系列文章,可以加深对数据结构和基本算法的理解(个人认为比学校讲的清晰多了),并加深对java的理解。


2-3树介绍

我们上回说到二叉查找树已经很接近我们的目标了,在很多情况下性能都很不错,但是唯独在删除上不行,一旦删除操作做多了就会失去平衡,那么,这回,我们来说说如何做一个平衡查找树,首先介绍一下2-3查找树

2-3树是一种特殊的二叉树,它允许一个节点中出现2个key。

  • 2节点:1个key,2个孩子

  • 3节点,2个key,3个孩子

your text

它有几个特性:

  1. 符合中序遍历的顺序:左孩小于最左key,中间孩子在左右key之间,右孩子大于最右key

  2. 绝对平衡:从根节点到所有null节点的路径一样长(我们后面会讲如何维护)

2-3树查找

根据它的特性,我们可以很容易知道如何查找,和二叉树的查找差不多,只是多了一个节点。

  • 如果小于左孩子:go left

  • 如果小于右孩子:go mid

  • 如果大于右孩子:go right

  • 如果等于key,返回value

  • 如果为null,返回null

看动画:

your text

2-3树的插入

插入分几种情况:

  • 如果插入的节点是一个2-节点:直接把2节点变成3节点

your text

  • 如果插入的是一个3-节点:
    • 把key加入3-节点变成一个临时4-节点

    • 把4节点的中间key上移到父亲节点

    • 重复操作。

    • 如果到达了root,形成了一个临时4节点,则root节点分裂成3个节点,树高增加1层

your text

your text

看动画:

your text

构造动画

讲了这么多,我们就来看看如何构造一棵2-3树吧。

your text

实现方案

这里就先卖个关子,这里不写代码实现,大家先了解下,后面会用红黑树的方案实现2-3树

        <div>
            作者:hk2291976 发表于2016/5/25 10:45:16 <a href="http://blog.csdn.net/hk2291976/article/details/51496616">原文链接</a>
        </div>
        <div>
        阅读:3041 评论:2 <a href="http://blog.csdn.net/hk2291976/article/details/51496616#comments" target="_blank">查看评论</a>
        </div>