Skip to content

Instantly share code, notes, and snippets.

@davissp14
Created April 25, 2015 02:01
Show Gist options
  • Save davissp14/5e4619c9369823999bfb to your computer and use it in GitHub Desktop.
Save davissp14/5e4619c9369823999bfb to your computer and use it in GitHub Desktop.
Binary Search Tree
class Node
attr_accessor :left, :right, :parent, :key
def initialize(key)
@parent = @left = @right = nil
@key = key
end
end
class BST
attr_accessor :root
def initialize(key)
@root = Node.new(key)
end
def insert(key)
z = Node.new(key)
y = nil
x = @root
until x.nil?
y = x # maintain the trailer
if z.key > x.key
x = x.right
else
x = x.left
end
end
z.parent = y # Set parent.
if y.nil? # The table was empty
@root = z
elsif z.key > y.key
y.right = z
else
y.left = z
end
z
end
def successor(key)
x = search(key)
unless x.nil? || x.right.nil?
return min(x.right)
end
y = x.parent
while y != nil && y.right == x
x = y
y = y.parent
end
y
end
def inorder_traversal(x=@root)
unless x.nil?
inorder_traversal(x.left)
puts x.key
inorder_traversal(x.right)
end
end
def search(key)
x = @root
until x.nil? || x.key == key
if key > x.key
x = x.right
else
x = x.left
end
end
x
end
def min(x=@root)
until x.left.nil?
x = x.left
end
x
end
def max(x=@root)
until x.right.nil?
x = x.right
end
x
end
def depth(x=@root)
return 0 if x.nil?
left_height = depth(x.left)
right_height = depth(x.right)
[left_height, right_height].max + 1
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment