AVL 木なロープもどきの改訂

4 年前に書いたロープに手を入れました。

https://gist.github.com/tociyuki/10372481 avlrope.rb
AVL 木なロープもどき
Rope もどきの落ち穂拾い

算法は同じです。 このロープの木は、 部分木に含まれている文字数による Weight 木になっていて、 木の平衡は AVL 木でノードの左右の深さの差が 1 以下になるように調整しています。 2018 年の視点からは、 このロープは Join-based tree algorithm の一種だと言えます。 ロープ特有の操作は split で、 通常は木を 2 つに分ける操作を、 3 つに分けて真ん中だけを取り出すところに特徴があります。 4年前に作った木の graft メソッドは、 Blelloch et al. Just Join for Parallel Ordered Sets (2016) の AVL 木の join2 に相当します。 なので、 avlrope.rb のメソッド名を変更して join2_rope メソッドにしておきます。

今回の改訂で、 木の回転を破壊操作に変更し、 非破壊操作に伴っていた Node オブジェクトを作ってすぐに捨てていた無駄を省きました。 それに合わせて平衡調整の条件分岐部分の整理をおこないました。 手作業で静的単一代入に変換し、 変数の値伝播を整理しました。 その結果、 木の回転の結果を直接求める書き方に変わってます。 回転の組み合わせ方は読み取りにくくなってますが、 木をどのように書き換えるべきかが読み取りやすくなりました。

  def join_right(left, right)
    path = []
    while left.height > right.height
      path.push left
      left = left.right
    end
    node = Node.new(left, right)
    if ! path.empty?
      begin
        n = path.pop
        if n.left.height >= n.right.height
          node = Node.new(n.left, node)
        elsif node.left.height <= node.right.height
          node.left = Node.new(n.left, node.left)
          node.update
        else
          node.right = Node.new(node.left.right, node.right)
          node.left = Node.new(n.left, node.left.left)
          node.update
        end
      end while node.left.height != node.right.height && ! path.empty?
    end
    while ! path.empty?
      node = Node.new(path.pop.left, node)
    end
    node
  end

ノードを破壊操作するようにしたのに対応して、 深さと文字数の更新を update メソッドに分けました。

  class Node
    attr_accessor :left, :right, :size, :height

    def initialize(left, right)
      @left, @right = left, right
      update()
    end

    def update()
      @size = @left.size + @right.size
      @height = [@left.height, @right.height].max + 1
    end

    def leaf?() false end
    def inspect() '(%p %p)' % [@left, @right] end
  end

split の手順は前と同じですが、 継続リストを unshift/shift していたのを、 push/pop して memmove を省いています。 rubypush a, b, ca, b, c の順にプッシュして、 pop 3a, b, c とポップするため、 引数の後に手続き名を並べる書き方にしています。

  def get_rope(node, first, second)
    kont = [node, first, second, :split]
    while not kont.empty?
      case kont.last
      when :split
        node, first, second, _ = kont.pop(4)
        node = while true
                 if first >= second
                   break EMPTY
                 elsif 0 == first && node.size == second
                   break node
                 elsif node.leaf?
                   break Leaf.new(node.string, first, second - first)
                 else
                   left_size = node.left.size
                   if second <= left_size
                     node = node.left
                   elsif first < left_size
                     kont.push node, second, :split_right
                     second = left_size
                     node = node.left
                   else
                     first -= left_size
                     second -= left_size
                     node = node.right
                   end
                 end
               end
      when :split_right
        parent, second, _ = kont.pop(3)
        kont.push node, :join, parent.right, 0, second - parent.left.size, :split
      when :join
        left, _ = kont.pop(2)
        node = if    0 == node.size then left
               elsif 0 == left.size then node
               else join2_rope(left, node)
               end
      end
    end
    node
  end