AVL Tree
The following is definition of AVL Tree according to Wikipedia
In computer science, an AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
Big-O Complexity
Note: N is the number of nodes in the tree prior to the operation
Lookup, insertion, and deletion all take O(log N) time in both the average and worst cases because it is self-balancing. The diffrence between heights of left and right sub-trees are not more than one for all nodes.
Implementation
class AVLTree
class Node
attr_reader :value, :left, :right
def initialize(value)
@value = value
@left = nil
@right = nil
end
def insert(v)
case @value <=> v
when -1 # insert into right subtree
@right.nil? ? @right = Node.new(v) : @right.insert(v)
when 1 # insert into left subtree
@left.nil? ? @left = Node.new(v) : @left.insert(v)
end
end
end
def initialize(v)
@root = Node.new(v)
end
def insert(v)
@root.insert(v)
end
def is_balanced?(node=@root)
h_left = get_height(node.left)
h_right = get_height(node.right)
h_diff = h_left - h_right
return h_diff.abs > 1 ? false : true
end
def get_height(node=@root)
return 0 if node.nil? # base case
h_left = get_height(node.left)
h_right = get_height(node.right)
return [h_left, h_right].max + 1
end
end
# Create an AVL Tree
avl_tree = AVLTree.new(10)
avl_tree.insert(5)
avl_tree.insert(15)
puts avl_tree.get_height
puts avl_tree.is_balanced?
puts avl_tree.inspect
