D. Knuth の二分探索木の削除アルゴリズム

D. KnuthThe Art of Computer Programming Volume 3 の二分探索木の削除アルゴリズムは、 その場書き換え方式です。 左右の子ノードへのポインタの欄とキーの欄だけを持つノードを使います。 親ノードへのポインタも、 再帰も、 継続ループも使いません。 削除対象のキーを持つノードの右側から最左ノードを探しだして、 最左ノードで削除対象ノードを置き換えるやりかたを採用しています。 下記のコメントの削除例では、 キー A を削除しており、 入れ子リスト表記でキー A とそのすぐ右隣にある nil を合わせて木から取り除きます。 起こりうる状況は 3 通りあります。

  1. 右隣 nil がキー A を持つノード t の右ポインタのとき。 このときは、 ノード t の左ノードで t を置き換えます。
  2. 右隣 nil がキー A を持つノード t の右側の直下の子ノード r の左ポインタのとき。 このときは、 ノード t の左ノードをノード r の左子ノードに移して、 r で t を置き換えます。
  3. それ以外のとき。 右隣 nil を持つノード s とその親ノード r を探します。 具体的には、 ノード t の右側の左ポインタが nil の最も左にあるノード s を探します。 子ノードの配置を変えてから、 このノード s でノード t を置き換えます。 このとき、 ノード s の親ノード r も一緒に探します。 ノード r の左がノード s です。 ノード r のノード s は、 ノード s の右ノードで置き換えます。

なお、 アルゴリズムでは左辺値変数 Q を使っており、 Ruby でてっとり早く左辺値を真似するのに手続き setq で、 ごまかしています。

class BinarySearchTree
  attr_accessor :root
  def initialize() @root = nil end

  def erase(key)
    not @root.nil? or return self
    parent = @root
    setq_left, setq_right = ->(x){ parent.left = x }, ->(x){ parent.right = x }
    node, setq = @root, ->(x){ @root = x }
    while key != node.key
      parent = node
      if key < node.key
        not node.left.nil? or break
        node, setq = node.left, setq_left
      else
        not node.right.nil? or break
        node, setq = node.right, setq_right
      end
    end
    if key == node.key
      # D. Knuth, ``The Art of Computer Programming Vol. 3'', page 432
      # Algorithm D (Tree deletion)
      if node.right.nil?            # (#t=(a A nil) B c)
        setq.call(node.left)        # (a B c)
      elsif node.right.left.nil?    # (#t=(a A #r=(nil B c)) C d)
        node.right.left = node.left # (#t=(a A #r=(a B c)) C d)
        setq.call(node.right)       # (#r=(a B c) C d)
      else
        r = node.right
        while true
          s = r.left
          break if s.left.nil?
          r = s
        end                         # (#t=(a A (#r=(#s=(nil B c) C d) D e)) E f)
        s.left = node.left          # (#t=(a A (#r=(#s=(a B c) C d) D e)) E f)
        r.left = s.right            # (#t=(a A (#r=(c C d) D e)) E f)
        s.right = node.right
        setq.call(s)                # (#s=(a B (#r=(c D d) D e)) E f)
      end
    end
    self
  end

  class Node
    attr_accessor :left, :key, :right
    def initialize(left, key, right) @left, @key, @right = left, key, right end
  end
end