Geek asks and answers

How to split a rope tree?

I came across a rope tree as an alternative data structure for a string.

http://en.wikipedia.org/wiki/Rope_ (data_structure)

For concat is easy, but I'm stuck on split operations. The Wikipedia article reads:

For example, to split the 22-character rope shown in Figure 2.3 into two equal component ropes of length 11, query for the 12th character to find node K at the lower level. Remove the connection between K and the right child of G. Go to the parent G and subtract the weight of K from the weight of G. Climb the tree and remove all the correct links by subtracting the weight of K from these nodes (only node D, in this case). Finally, create newborn nodes K and H, combining them together and creating a new parent P with a weight equal to the length of the left node K.

Character search and orphan recombination is not a problem. But I don’t understand "Travel the tree and remove any regular links by subtracting the weight K from these nodes." The example stops at D, but if you follow these instructions verbatim, you continue at B and delete D. What is the correct stop requirement in this algorithm? And how do you avoid nodes with one (left or right) child?

A pseudo-code algorithm explaining this part will help a lot.

+3
source share
3 answers

. node X, Y, , X Y. , .

+1

, , :

.

A) node (node A), node. node A. node - . node .

B), node ( ), node node: split node (= > node) parent node .

C), node ( ), node node: node (= > node) node .

D), node ( ), node node: node

D), node ( ), node node: node .

: node - node: node .

node node: ( A), node. (, , node node A. node A - . node.)

node. rootNode. .

, , .

0

Ruby . . Ruby , . , , .

split . .

class Rope

  # Cat two ropes by building a new binary node.
  # The parent count is the left child length.
  def cat(s)
    if self.len == 0
      s
    elsif s.len == 0
      self
    else
      Node.new(self, s, len)
    end
  end

  # Insert a new string into a rope by splitting it
  # and concatenating twice with a new leaf in the middle.
  def insert(s, p)
    a, b = split_at(p)
    a.cat(Leaf.new(s)).cat(b)
  end

end

class Leaf < Rope
  # A leaf holds characters as a string.
  attr_accessor :chars

  # Construct a new leaf with given characters.
  def initialize(chars)
    @chars = chars
  end

  # The count in this rope is just the number of characters.
  def count
    chars.length
  end

  # The length is kind of obvious.
  def len
    chars.length
  end

  # Convert to a string by just returning the characters.
  def to_s
    chars
  end

  # Split by dividing the string.
  def split_at(p)
    [ Leaf.new(chars[0...p]), Leaf.new(chars[p..-1]) ] 
  end
end

class Node < Rope
  # Fields of the binary node.
  attr_accessor :left, :right, :count

  # Construct a new binary node.
  def initialize(left, right, count)
    @left = left
    @right = right
    @count = count
  end

  # Length is our count plus right subtree length. Memoize for efficiency.
  def len
    @len ||= count + right.len
  end

  # The string rep is just concatenating the children string reps.
  def to_s
    left.to_s + right.to_s
  end

  # Split recursively by splitting the left or right 
  # subtree and recombining the results.
  def split_at(p)
    if p < count
      a, b = left.split_at(p)
      [ a, b.cat(right) ]
    elsif p > count 
      a, b = right.split_at(p - count)
      [ left.cat(a), b ]
    else
      [ left, right ]
    end
  end
end
0
source

More articles:


All Articles