非破壊操作型二分探索 AVL 木 - 高さ記録版

Rope もどきは、非破壊操作型の AVL 木を使いました。非破壊操作を実現するため、必ず根までパスを戻って木を作り直す性質を利用し、ノードを頂点とする部分木の高さを各ノードに記録するようにしたのでした。同じやりかたで、二分探索 AVL 木の挿入と削除を書いてみます。

class AVLtree
#@<高さ属性をもつ Nodeクラス@>
#@<高さゼロの NULL オブジェクト@>

  attr_reader :root
  def inspect() @root.inspect end

  def initialize(root = NULL)
    @root = root
  end

#@<x を挿入した木を新しく作る@>
#@<x を削除した木を新しく作る@>
#@<根までパスを戻りながら木を新しく作る@>
#@<左が重い node のバランス調整をする@>
#@<右が重い node のバランス調整をする@>
end

あるノードの部分木の高さは左右の部分木の高さの高い方に 1 を足したものになります。ノードを作るときに左右の部分木を与えるのは当然のことで、ノード生成時に自動的に自分の高さを求めることができます。

#@<高さ属性をもつ Nodeクラス@>=
  class Node
    attr_reader :left, :data, :right, :depth

    def initialize(left, data, right, depth = nil)
      @left, @data, @right = left, data, right
      @depth = depth || [left.depth, right.depth].max + 1
    end

    def null?() false end

    def inspect
      '(%s %s %s)' % [@left.inspect, @data.inspect, @right.inspect]
    end
  end

葉の NULL の高さはゼロにします。

#@<高さゼロの NULL オブジェクト@>=
  NULL = Object.new
  def NULL.depth() 0 end
  def NULL.null?() true end
  def NULL.inspect() 'null' end

値を挿入した木を新しく作る手順は、二分探索木の通りです。葉まで降りていき、根に逆戻りしながら新しく値を挿入した木を作ります。パスに、左右どちらかに降りたかをシンボルで記録しています。

#@<x を挿入した木を新しく作る@>=
  def insert(x)
    return self.class.new(Node.new(NULL, x, NULL)) if @root.null?
    path = []
    node = @root
    while not node.null?
      return self if x == node.data
      if x < node.data
        path.push [:left, node]
        node = node.left
      else
        path.push [:right, node]
        node = node.right
      end
    end
    backroot(:insert, path, Node.new(NULL, x, NULL))
  end

値を削除した木を新しく作る手順も、二分探索木の通りです。葉まで降りていき、途中に値をもったノードがあるなら、葉をもつノードの値を移し替えておいて、その後で根に逆戻りしながら新しく木を作ります。

#@<x を削除した木を新しく作る@>=
  def delete(x)
    return self if @root.null?
    path = []
    j, just, node = nil, nil, @root
    while not node.null?
      j, just = path.size, node if x == node.data
      if x <= node.data
        path.push [:left, node]
        node = node.left
      else
        path.push [:right, node]
        node = node.right
      end
    end
    return self if just.nil?
    _, n = path.pop
    if not just.equal?(n)
      path[j][1] = Node.new(just.left, n.data, just.right, just.depth)
    end
    node = if n.right.null? then n.left else n.right end
    backroot(:delete, path, node)
  end

挿入・削除の両方で、葉から根へパスを戻りながら新しく木を作ります。手をふれないノードは元の木と共用します。まず、降りた側の部分木が新しいものに変わっているので、新しい部分木につながるノードを作ります。続いて、バランスを調整します。左を更新したとき、挿入なら左が重くなり、削除なら右が重くなります。右を更新したときは逆になります。

#@<根までパスを戻りながら木を新しく作る@>=
  def backroot(d, path, node)
    balanced = false
    path.reverse_each do |fn, n|
      if fn == :left
        node = Node.new(node, n.data, n.right)
      else
        node = Node.new(n.left, n.data, node)
      end
      next if balanced
      if (d == :delete) ^ (fn == :left)
        node = balance_left_heavy(node)
      else
        node = balance_right_heavy(node)
      end
      balanced = (d == :delete) ^ (node.left.depth == node.right.depth)
    end
    self.class.new(node)
  end

左が重いときは、挿入・削除後の高さの差が 2 以上に増えています。その場合、部分木の配置を調整することでバランスをとります。

#@<左が重い node のバランス調整をする@>=
  def balance_left_heavy(node)
    if node.right.depth - node.left.depth < -1 and not node.left.null?
      ll, d1, lr, d3, p4 = node.left.left, node.left.data, node.left.right, node.data, node.right
      if ll.depth >= lr.depth
        node = Node.new(ll, d1, Node.new(lr, d3, p4))
      else
        node = Node.new(Node.new(ll, d1, lr.left), lr.data, Node.new(lr.right, d3, p4))
      end
    end
    node
  end

右が重いときも同様にバランスをとります。

#@<右が重い node のバランス調整をする@>=
  def balance_right_heavy(node)
    if node.right.depth - node.left.depth > 1 and not node.right.null?
      p0, d1, rl, d3, rr = node.left, node.data, node.right.left, node.right.data, node.right.right
      if rl.depth <= rr.depth
        node = Node.new(Node.new(p0, d1, rl), d3, rr)
      else
        node = Node.new(Node.new(p0, d1, rl.left), rl.data, Node.new(rl.right, d3, rr))
      end
    end
    node
  end