普通BST的基本操作过程

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

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

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

依次插入上面的那10个key:

  • put(9)

  • put(3)

  • put(8)

  • put(1)

  • put(2)

  • put(10)

  • put(4)

  • put(5)

  • put(7)

  • put(6)

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

这个操作分为两大部分:一是找到键为key的节点,二是删除它。在删除节点的时候要讨论三种情况:1. 节点为叶子;2. 节点只有一个孩子(左或右孩子);3. 节点有两个孩子。

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

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

  • del(4):待删节点仅有一个右孩子,处理方式同上。

  • del(3):待删节点有两个孩子,删除节点后需要对两个孩子进行安置。此时,双亲节点留下的空位只有一个,到底让哪个孩子去“坐”呢?让其中一个孩子去“坐”了,另外一个怎么处理?对此有两种处理方法。

    方法一:选一个孩子“坐”到其被删双亲的位置,然后对另一个孩子及其子孙后代节点实施put操作,将它们按规则依次插入到以其兄弟为根的这个子树当中。

    这是一种容易想到的办法,但却要进行多次额外的操作:插入,遍历(图示中对被删节点的右子树进行了先根序遍历)操作。重点是,使用这种方法有可能导致树长高,如果进行频繁的删除操作,这个缺点就会变的显著。这不是一个好的方法。

    方法二:删除带有两个孩子的节点时,纠结之处就是只有一个空位,而有两个孩子需要安置。如果找一个与被删节点地位相当的节点去“坐”这个空位,让它去做这两个孩子的新双亲,有了双亲的孩子就不用再操心如何去安置了。关键是,这么做可以保持删除前后,树的结构基本不变,树不会长高。

    那么,这个新的双亲节点如何确定呢?二叉查找树的特性是保证了key的有序性,对其进行中根序遍历就会得到key的升序序列,不论我们做何种操作,都要去维护二叉查找树的这个特性。对这个以键值为3的节点作为根节点的子树进行中根序遍历得到:{ 1, 2, 3, 4, 5, 6, 7, 8 }。其中3是待删节点的key,key为2的节点是其前驱节点,key为4的节点是其后继节点。把key为3的节点删除了,我们若用其后继或者前驱去“坐”它的位置,有序性是不会被破坏的,因此,新的双亲节点可以是被删节点的前驱或者后继节点,这里使用后继节点。

    一个节点的后继节点,其key值肯定比该节点的key值要大。而后继节点的key值又是与该节点的key值最接近的,因此,这个后继节点的key值是所有比该节点大的key值中最小的那个key值。

    所以,应该在节点的右子树中找寻其后继节点,在右子树中递归地访问左孩子,直到访问到空节点。这个空节点的双亲节点即为我们要找的后继节点,显然,该节点是没有左孩子的。它去填补被删节点的位置后,其自身空出的位置,将由其右孩子来填补。

get(key):查询键值为key的节点。查询过程与插入节点的过程类似。

  • get(7)