class AVLTree::BSTree

Attributes

root[R]

Public Class Methods

new(root = nil) click to toggle source
# File lib/ruby-avl/bs_tree.rb, line 6
def initialize(root = nil)
  @root = root  
end

Public Instance Methods

depth_of_tree() click to toggle source

Starts the count of the depth at the root node.

# File lib/ruby-avl/bs_tree.rb, line 28
def depth_of_tree
  tree_depth(@root, 0)
end
insert_item(item) click to toggle source

Starts the search for the insertion at the root of the tree. Set the new root at the end if it has changed.

# File lib/ruby-avl/bs_tree.rb, line 12
def insert_item(item)
  @root = add_to_tree(item, @root)      
end
number_of_nodes() click to toggle source

Starts the count at the root node.

# File lib/ruby-avl/bs_tree.rb, line 23
def number_of_nodes
  node_count(@root)
end
remove_item(item) click to toggle source

Starts the search for the deletion at the root of the tree. Set the new root at the end if it has changed.

# File lib/ruby-avl/bs_tree.rb, line 18
def remove_item(item)
  @root = remove_from_tree(item, @root)
end

Private Instance Methods

add_to_tree(item, node) click to toggle source

If the current node is null then a new Node object is created and item is passed in as a constructor. If item is smaller than the data stored in the current node then :add_to_tree is called recursively to traverse the left-sub tree until the node is null. The same thing happens if the item is larger, but the right sub-tree is traversed. If item is neither larger nor smaller then it must be equal, in which case an error will be raised to inform the user of duplication.

# File lib/ruby-avl/bs_tree.rb, line 41
def add_to_tree(item, node)
  if node.nil?
    return Node.new(item)
  elsif compare(item, node.data) < 0
    node.left = add_to_tree(item, node.left)
  elsif compare(item, node.data) > 0
    node.right = add_to_tree(item, node.right)
  else
    puts 'Duplicate entry. Skipping: %s' % item
  end
  return node
end
compare(item_one, item_two) click to toggle source

Comparison of two objects. Will return -1 if item_one is less than item_two, 0 if they are equal, and 1 if item_one is greater than item_two. First checks if object has it's own comparison logic, if not, uses core Ruby comparision.

# File lib/ruby-avl/bs_tree.rb, line 80
def compare(item_one, item_two)
  begin
    item_one.compare_to(item_two)
  rescue NoMethodError
    item_one <=> item_two
  end
end
height(node) click to toggle source

Calculates the height of the node using it's leaves. Initial check to see if node is nil which means it has a height of 0.

# File lib/ruby-avl/bs_tree.rb, line 107
def height(node)
  node.nil? ? 0 : 1 + max(height(node.left), height(node.right))
end
least_item(node) click to toggle source

Recursively finds the lowest item in a nodes left subtree.

# File lib/ruby-avl/bs_tree.rb, line 89
def least_item(node)
  return unless node
  return node unless node.left
  least_item(node.left)
end
max(*values) click to toggle source

Converts parameters to an Array then calls Enumerable#max on them to return the largest element.

# File lib/ruby-avl/bs_tree.rb, line 113
def max(*values)
  values.max
end
node_count(node) click to toggle source

Traverses the tree and returns the sum of the nodes.

# File lib/ruby-avl/bs_tree.rb, line 96
def node_count(node)
  node.nil? ? 0 : 1 + node_count(node.left) + node_count(node.right)
end
remove_from_tree(item, node) click to toggle source

If the current node is null then the tree is empty or the item isn't in it. If item is smaller or larger than current node like above, if it's neither then it must be equal so checks are made to see how many children that node has. If it has two then a the value of the node is swapped with the value of the smallest item in it's right-sub tree, then removeItem is called again but this time on the value in the right sub-tree. If the node has less than two children another check is made: if the left child is not null, the value of the node is equal to that value, otherwise it's equal to the value of the right child.

# File lib/ruby-avl/bs_tree.rb, line 62
def remove_from_tree(item, node)
  return if node.nil?      
  if compare(item, node.data) < 0
    node.left = remove_from_tree(item, node.left)
  elsif compare(item, node.data) > 0
    node.right = remove_from_tree(item, node.right)
  elsif node.left && node.right
    node.data = least_item(node.right).data
    node.right = remove_from_tree(node.data, node.right)
  else
    node = node.left ? node.left : node.right
  end
  return node
end
tree_depth(node, depth) click to toggle source

Traverses the tree and calculates the depth of the longest sub-tree

# File lib/ruby-avl/bs_tree.rb, line 101
def tree_depth(node, depth)
  node.nil? ? 0 : depth + max(height(node.left), height(node.right))
end