平衡查找树(1)—— 2-3查找树(附动画)

2016-05-25   |     |     |  

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


2-3树介绍

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

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

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

它有几个特性:

  1. 符合中序遍历的顺序:左孩小于最左key,中间孩子在左右key之间,右孩子大于最右key
  2. 绝对平衡:从根节点到所有null节点的路径一样长(我们后面会讲如何维护)

2-3树查找

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

  • 如果小于左孩子:go left
  • 如果小于右孩子:go mid
  • 如果大于右孩子:go right
  • 如果等于key,返回value
  • 如果为null,返回null

看动画:

2-3树的插入

插入分几种情况:

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

  • 如果插入的是一个3-节点:
    • 把key加入3-节点变成一个临时4-节点
    • 把4节点的中间key上移到父亲节点
    • 重复操作。
    • 如果到达了root,形成了一个临时4节点,则root节点分裂成3个节点,树高增加1层

看动画:

构造动画

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

实现方案

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