2-3查找树的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value

put(key):插入一个键值为key的节点

插入操作的基本做法跟BST一样,先对key进行查找。2-3树不同之处在于,key要与查找的结束节点相结合,即:key-value值要先存于结束查找时的那个节点中,而不是挂到那个节点之下。这样就会形成3-节点或4-节点,其中4-节点是临时节点,一旦出现,就要拆分掉。

2-3树插入操作可分为几种情况:1. 向2-节点中插入新键;2. 向孤立(没有双亲,也没有孩子)的3-节点插入新键;3. 向一个双亲节点为2-节点的3-节点插入新键;4. 向一个双亲节点为3-节点的3-节点插入新键。3、4处理方式类似,3-节点变4-节点,4-节点拆成2-节点,中间2-节点再与其双亲节点结合,若结合出4-节点,就再拆分。

  • put(9)
    空树,插入首个节点,没什么特别的地方:

  • put(3)
    向2-节点中插入新键,结合成3-节点:

  • put(8)
    向一个孤立的3-节点插入新键,先结合成4-节点,然后进行拆分成2-节点:

  • put(1)
    向2-节点中插入新键,结合成3-节点:

  • put(2)
    向一个双亲节点为2-节点的3-节点插入新键,先结合成4-节点,然后拆分成2-节点,拆分前的中间节点再与其双亲节点结合,若又结合成4-节点,则再拆分之。这里的双亲节点本身是2-节点,结合后演变为3-节点:

  • put(10)
    向2-节点中插入新键,结合成3-节点:

  • put(4)
    向2-节点中插入新键,结合成3-节点:

  • put(5)
    向一个双亲节点为3-节点的3-节点插入新键,当前节点变为4-节点,4-节点拆分后,中间节点与其双亲节点再结合,又得到了一个4-节点,然后继续拆分:

  • put(7)
    向2-节点中插入新键,结合成3-节点:

  • put(6)
    向一个双亲节点为2-节点的3-节点插入新键,插入后得4-节点,然后再拆分:

del(key):删除一个键值为key的节点

与BST的删除操作是同样的流程,先找到键为key的节点,然后再删除它。在进行操作的时候可以把3-节点看成是两个2-节点,将3-节点中后到的那个2-节点视为子,另外一个为双亲。这样就可以完全按照BST的删除操作来处理了。

同样有三种情况:1. 节点为叶子;2. 节点只有一个孩子(左或右孩子);3. 节点有两个孩子。节点有两个孩子的情况,采取用待删节点的后继节点去取代它的办法来处理。

  • del(5):待删节点为叶子节点,由于叶子无后代,可以干净利落的将其删除。

  • del(9):待删节点仅有一个右孩子,删除节点后需要对该子进行安置。由于只有这一个孩子,直接让其“坐”到其双亲的位置即可。

  • del(8):待删节点有两个孩子,删除节点后,让其后继节点填补其位置,孩子无需特殊安置。

get(key):查询键值为key的节点,查询操作与BST一样。

  • get(6)