Rodrigo E. Rodrigo E. - 7 months ago 13
Ruby Question

Losing references in an AVL tree

I have this class:

class AVLTree
class Node
attr_accessor :value, :height
attr_accessor :left, :right

def initialize(value, height)
@value = value
@height = height
end
end

attr_accessor :root

def initialize
@root = Node.new(nil, 0)
end

# Right rotation of the tree
def right_rotation(node = @root)
begin
root = node.left
node.left = root.right
root.height = node.height
root.right = node
update_subtrees_height(root.right, root.height)
update_subtrees_height(root.left, root.height)
rescue Exception => e
puts "Tree not able to do a right rotation: #{e.message}"
puts e.backtrace.inspect
end
root
end

# Left rotation of the tree
def left_rotation(node = @root)
begin
root = node.right
node.right = root.left
root.height = node.height
root.left = node
update_subtrees_height(root.right, root.height)
update_subtrees_height(root.left, root.height)
rescue Exception => e
puts "Tree not able to do a left rotation: #{e.message}"
puts e.backtrace.inspect
end
root
end

# Update the height of the elements of a sub-tree and all other sub-tree of its side
def update_subtrees_height(node, height)
return if node.nil?
node.height = height + 1
update_subtrees_height(node.left, node.height)
update_subtrees_height(node.right, node.height)
end

def balance_factor(node = @root)
leftSize = node.left.nil? ? 0 : deepest_node(node.left).height
rightSize = node.right.nil? ? 0 : deepest_node(node.right).height
rightSize - leftSize
end

def balance(node = @root)
balanceFactor = balance_factor(node)
return node if balanceFactor <= 1 && balanceFactor >= -1
if balanceFactor > 1
if balance_factor(node.right) < 0
node.right = right_rotation(node.right)
node = left_rotation(node)
else
node = left_rotation(node)
end
else
if balance_factor(node.left) > 0
node.left = right_rotation(node.left)
node = left_rotation(node)
else
node = right_rotation(node)
end
end
end

def print_tree(node = @root)
return if node.nil?
puts "#{node.left.nil? ? 'null' : node.left.value} - #{node.nil? ? 'null' : node.value}(L#{node.height}) - #{node.right.nil? ? 'null' : node.right.value}"
print_tree(node.left)
print_tree(node.right)
end

def deepest_node(node = @root, deepest = @root)
return deepest if node.nil?
if node.height > deepest.height then deepest = node else deepest end
right = deepest_node(node.left, deepest)
left = deepest_node(node.right, deepest)
right.height > left.height ? right : left
end

def insert(value, node = @root)
case value <=> node.value
when -1
if node.left.nil?
node.left = Node.new(value, node.height + 1)
else
insert(value, node.left)
node = balance(node.left)
end
when 1
if node.right.nil?
node.right = Node.new(value, node.height + 1)
else
insert(value, node.right)
node = balance(node)
end
else
node.value = value
end
end

end


I'm doing this test:

a = AVLTree.new

[1,2,3,4,5].each do |v|
a.insert v
end

a.print_tree a.root


My expected output is

1 - 2(H0) - 4
null - 1(H1) - null
3 - 4(H1) - 5
null - 3(H2) - null
null - 5(H2) - null


who represet the tree below:

2
/ \
1 4
/ \
3 5


The output that I have is:

null - 1(H2) - null


Debugging the code, I descovered that the problem occurs in my
insert
method, every time when I call the line
node = balance(node.left)
. At this time I lose the references of the tree.

The
balance
method it's ok in my tests. For example:

When I insert the 3 at the tree, I have

1
\
2
\
3


and then I call the balance with the node 1, receiving the expected tree

2
/ \
1 3


The logic that I thought is: every time when I insert a value in the tree, I will check its balance and fix it, if necessary. With the recursivity of my
insert
method, I will check the tree upwards, starting one point above from the inserted node. In the example above, when I go to node 1 and balance it, the
balance
method will return a new node with the 2 like the root of this sub-tree, with my old node receiving that.

That happens, but for some reason, the root node of the AVL tree lost references to other nodes. Any ideia of how can I fix that?

Answer

I'm not sure yet about the reason of my problem, but I reimplemented the AVL tree in what I believe to be a better way. It worked, and my main lesson is: if you are implementing a tree, it's a smart choice create the methods to manipulate a node (insert, update and so on) in the node class itself! That sound obvious, but is not so obvious at the first time you do.

Here is the new version of my class:

class AVLTree
  class Node
    attr_accessor :right, :left
    attr_accessor :key, :height

    def initialize(key = nil, height = nil)
      @key = key
      @height = height
      @left = @right = EmptyNode.new
    end

    def insert(key)
      case key <=> @key
      when -1
        @left = @left.insert(key)
        @left.height = self.height + 1
      when 0
        @value = value
      when 1
        @right = @right.insert(key)
        @right.height = self.height + 1
      else
        raise TypeError, "Cannot compare #{key} with #{@key}"
      end
      balance
    end

    def balance
      balanceFactor = balance_factor
      return self if balanceFactor >= -1 && balanceFactor <= 1
      if balanceFactor > 1
        if @right.balance_factor < 0
          @right = @right.rotate_right
          root = rotate_left
        else
          root = rotate_left
        end
      else
        if @left.balance_factor > 0
          @left = @left.rotate_left
          root = rotate_right
        else
          root = rotate_right
        end
      end
      root
    end

    def balance_factor
      leftSize = @left.nil? ? 0 : deepest_node(@left).height
      rightSize = @right.nil? ? 0 : deepest_node(@right).height
      rightSize - leftSize
    end

    def deepest_node(node = self, deepest = self)
      return deepest if node.nil?
      if node.height > deepest.height then deepest = node else deepest end
      right = deepest_node(node.left, deepest)
      left = deepest_node(node.right, deepest)
      right.height > left.height ? right : left
    end

    def rotate_left
      raise "The node have not right child to do a left rotation" if @right.key.nil?
      root = @right
      @right = root.left
      root.height = @height
      root.left = self
      root.left.update_height(1)
      root.right.update_height(-1)
      root
    end

    def rotate_right
      root = @left
      @left = root.right
      root.height = @height
      root.right = self
      root.left.update_height(-1)
      root.right.update_height(1)
      root
    end

    def update_height(value)
      @height += value
      @left.update_height(value)
      @right.update_height(value)
    end

    class EmptyNode < Node
      def initialize
        @key = nil
        @height = 0
      end

      def insert(key)
        Node.new(key, 0)
      end

      def update_height(value)
      end
    end
  end

  attr_accessor :root

  def initialize
    @root = Node::EmptyNode.new
  end

  def insert(key)
    @root = @root.insert(key)
  end

  def print_tree(node = @root)
    return if node.key.nil?
    puts "#{node.left.nil? || node.left.key.nil? ? 'null' : node.left.key} - #{node.nil? || node.key.nil? ? 'null' : node.key}(L#{node.height}) - #{node.right.nil? || node.right.key.nil? ? 'null' : node.right.key}"
    print_tree(node.left)
    print_tree(node.right)
  end

  # sequence = left, root and right of each sub-tree
  def in_order(node = @root, sequence = [])
    return sequence if node.key.nil?
    in_order(node.left, sequence)
    sequence << [node.key, node.height]
    in_order(node.right, sequence)
  end
end