class BSTNode
attr_accessor :key, :value, :left, :right, :size
def initialize(k = nil, v = nil, s = 1)
@key = k
@value = v
@size = s
@left = nil
@right = nil
end
end
class BST
attr_accessor :root
def initialize
@root = nil
end
def insert(k, v)
if @root
@root = BST.insert_helper!(@root, k, v)
else
@root = BSTNode.new(k, v, 1)
end
end
def delete(k)
if k
root = BST.delete_helper!(@root, k)
end
end
def get(k)
if k
BST.get_helper!(@root, k)
end
end
def inorder
BST.inorder!(@root)
end
private
def self.delete_min!(x)
return x.right if x.left == nil
x.left = delete_min!(x.left)
x.size = size(x.left) + size(x.right) + 1
end
def self.min!(x)
return x if x.left == nil
min(x.left)
end
def self.inorder!(x)
if x == nil
return
end
inorder!(x.left)
puts "Key: #{x.key}, Value: #{x.value}"
inorder!(x.right)
end
def self.get_helper!(x, k)
if x == nil
nil
elsif k > x.key
get_helper!(x.right, k)
elsif k < x.key
get_helper!(x.left, k)
else
x.value
end
end
def self.delete_helper!(x, k)
if x == nil
nil
elsif k < x.key
x.left = delete_helper!(x.left, k)
elsif k > x.key
x.right = delete_helper!(x.right, k)
else
# Handles case of one children or no children
return x.left if x.right == nil
return x.right if x.left == nil
# Handle case 3 of two children
# Find successor of x called succ, which should be in right subtree
# succ replaces x in tree, delete succ from tree and replace x
# x right subtree becomes succ right subtree
# x left subtree becomes succ left subtree
# if succ is x right child, then replace x with succ and leave succ right child
# if succ is not x right child but in right subtree
# replace succ with its own right child
temp = x
x = min!(temp.right)
x.left = temp.left # does order matter?
x.right = delete_min!(temp)
end
x = size!(x.left) + size!(x.right) + 1
x
end
def self.size!(x)
if x == nil
0
else
x.size
end
end
def self.insert_helper!(x, k, v)
if x == nil
return BSTNode.new(k, v, 1)
elsif k < x.key
x.left = insert_helper!(x.left, k, v)
elsif k > x.key
x.right = insert_helper!(x.right, k, v)
else
x.value = v
end
x.size = size!(x.left) + size!(x.right) + 1
x
end
end
b = BST.new
b.insert(5, "c")
b.insert(4, "b")
b.insert(6, "d")
b.insert(3, "a")
b.insert(7, "e")
b.inorder
p b.get(3)
b.delete(6)
b.inorder
def mirrored?(left, right)
return (left == nil && right == nil) if right == nil || left == nil
left.value == right.value && mirrored?(left.left, right.right) && mirrored(left.right, right.left)
end
# This code can be used to make BST into balanced BST
a = [5,7,12,15,18,20]
# Nondecreasing array to balanced BST
def arrtobst(a, bst)
if a.length == 1
p a[0]
bst.insert(a[0], "temp")
elsif a.length > 1
mid_idx = a.length/2
p a[mid_idx]
bst.insert(a[mid_idx], "temp")
arrtobst(a.take(mid_idx), bst)
arrtobst(a.drop(mid_idx + 1), bst)
end
end
a2 = [1,2,3,4,5]
p "Array to BST"
bstree = BST.new
arrtobst(a, bstree)
bstree.inorder
btt = BST.new
btt = arrtobst(a2, btt)
btt.inorder
Y2xhc3MgQlNUTm9kZQogICAgYXR0cl9hY2Nlc3NvciA6a2V5LCA6dmFsdWUsIDpsZWZ0LCA6cmlnaHQsIDpzaXplCiAgICBkZWYgaW5pdGlhbGl6ZShrID0gbmlsLCB2ID0gbmlsLCBzID0gMSkKICAgICAgICBAa2V5ID0gawogICAgICAgIEB2YWx1ZSA9IHYKICAgICAgICBAc2l6ZSA9IHMKICAgICAgICBAbGVmdCA9IG5pbAogICAgICAgIEByaWdodCA9IG5pbAogICAgZW5kCmVuZApjbGFzcyBCU1QKICAgIGF0dHJfYWNjZXNzb3IgOnJvb3QKICAgIGRlZiBpbml0aWFsaXplCiAgICAgICAgQHJvb3QgPSBuaWwKICAgIGVuZAogICAgCiAgICBkZWYgaW5zZXJ0KGssIHYpCiAgICAgICAgaWYgQHJvb3QKICAgICAgICAgICAgQHJvb3QgPSBCU1QuaW5zZXJ0X2hlbHBlciEoQHJvb3QsIGssIHYpCiAgICAgICAgZWxzZQogICAgICAgICAgICBAcm9vdCA9IEJTVE5vZGUubmV3KGssIHYsIDEpCiAgICAgICAgZW5kCiAgICBlbmQKICAgIAogICAgZGVmIGRlbGV0ZShrKQogICAgICAgIGlmIGsKICAgICAgICAgICAgcm9vdCA9IEJTVC5kZWxldGVfaGVscGVyIShAcm9vdCwgaykKICAgICAgICBlbmQKICAgIGVuZAogICAgCiAgICBkZWYgZ2V0KGspCiAgICAgICAgaWYgawogICAgICAgICAgICBCU1QuZ2V0X2hlbHBlciEoQHJvb3QsIGspCiAgICAgICAgZW5kCiAgICBlbmQKICAgIAogICAgZGVmIGlub3JkZXIKICAgICAgICBCU1QuaW5vcmRlciEoQHJvb3QpCiAgICBlbmQKICAgIAogICAgcHJpdmF0ZQogICAgZGVmIHNlbGYuZGVsZXRlX21pbiEoeCkKICAgICAgICByZXR1cm4geC5yaWdodCBpZiB4LmxlZnQgPT0gbmlsCiAgICAgICAgeC5sZWZ0ID0gZGVsZXRlX21pbiEoeC5sZWZ0KQogICAgICAgIHguc2l6ZSA9IHNpemUoeC5sZWZ0KSArIHNpemUoeC5yaWdodCkgKyAxCiAgICBlbmQKICAgIAogICAgZGVmIHNlbGYubWluISh4KQogICAgICAgIHJldHVybiB4IGlmIHgubGVmdCA9PSBuaWwKICAgICAgICBtaW4oeC5sZWZ0KQogICAgZW5kCiAgICAgICAgCiAgICAgICAgCiAgICBkZWYgc2VsZi5pbm9yZGVyISh4KQogICAgICAgIGlmIHggPT0gbmlsCiAgICAgICAgICAgcmV0dXJuIAogICAgICAgIGVuZAogICAgICAgIAogICAgICAgIGlub3JkZXIhKHgubGVmdCkKICAgICAgICBwdXRzICJLZXk6ICN7eC5rZXl9LCBWYWx1ZTogI3t4LnZhbHVlfSIKICAgICAgICBpbm9yZGVyISh4LnJpZ2h0KQogICAgZW5kCiAgICAKICAgIGRlZiBzZWxmLmdldF9oZWxwZXIhKHgsIGspCiAgICAgICAgaWYgeCA9PSBuaWwKICAgICAgICAgICAgbmlsCiAgICAgICAgZWxzaWYgayA+IHgua2V5CiAgICAgICAgICAgIGdldF9oZWxwZXIhKHgucmlnaHQsIGspCiAgICAgICAgZWxzaWYgayA8IHgua2V5CiAgICAgICAgICAgIGdldF9oZWxwZXIhKHgubGVmdCwgaykKICAgICAgICBlbHNlCiAgICAgICAgICAgIHgudmFsdWUKICAgICAgICBlbmQKICAgIGVuZAogICAgCiAgICBkZWYgc2VsZi5kZWxldGVfaGVscGVyISh4LCBrKQogICAgICAgIGlmIHggPT0gbmlsCiAgICAgICAgICAgIG5pbAogICAgICAgIGVsc2lmIGsgPCB4LmtleQogICAgICAgICAgICB4LmxlZnQgPSBkZWxldGVfaGVscGVyISh4LmxlZnQsIGspCiAgICAgICAgZWxzaWYgayA+IHgua2V5CiAgICAgICAgICAgIHgucmlnaHQgPSBkZWxldGVfaGVscGVyISh4LnJpZ2h0LCBrKQogICAgICAgIGVsc2UKICAgICAgICAgICAgIyBIYW5kbGVzIGNhc2Ugb2Ygb25lIGNoaWxkcmVuIG9yIG5vIGNoaWxkcmVuCiAgICAgICAgICAgIHJldHVybiB4LmxlZnQgaWYgeC5yaWdodCA9PSBuaWwKICAgICAgICAgICAgcmV0dXJuIHgucmlnaHQgaWYgeC5sZWZ0ID09IG5pbAogICAgICAgICAgICAKICAgICAgICAgICAgIyBIYW5kbGUgY2FzZSAzIG9mIHR3byBjaGlsZHJlbgogICAgICAgICAgICAjIEZpbmQgc3VjY2Vzc29yIG9mIHggY2FsbGVkIHN1Y2MsIHdoaWNoIHNob3VsZCBiZSBpbiByaWdodCBzdWJ0cmVlCiAgICAgICAgICAgICMgc3VjYyByZXBsYWNlcyB4IGluIHRyZWUsIGRlbGV0ZSBzdWNjIGZyb20gdHJlZSBhbmQgcmVwbGFjZSB4CiAgICAgICAgICAgICMgeCByaWdodCBzdWJ0cmVlIGJlY29tZXMgc3VjYyByaWdodCBzdWJ0cmVlCiAgICAgICAgICAgICMgeCBsZWZ0IHN1YnRyZWUgYmVjb21lcyBzdWNjIGxlZnQgc3VidHJlZQogICAgICAgICAgICAjIGlmIHN1Y2MgaXMgeCByaWdodCBjaGlsZCwgdGhlbiByZXBsYWNlIHggd2l0aCBzdWNjIGFuZCBsZWF2ZSBzdWNjIHJpZ2h0IGNoaWxkCiAgICAgICAgICAgICMgaWYgc3VjYyBpcyBub3QgeCByaWdodCBjaGlsZCBidXQgaW4gcmlnaHQgc3VidHJlZQogICAgICAgICAgICAgICAgIyByZXBsYWNlIHN1Y2Mgd2l0aCBpdHMgb3duIHJpZ2h0IGNoaWxkCiAgICAgICAgICAgIHRlbXAgPSB4CiAgICAgICAgICAgIHggPSBtaW4hKHRlbXAucmlnaHQpCiAgICAgICAgICAgIHgubGVmdCA9IHRlbXAubGVmdCAjIGRvZXMgb3JkZXIgbWF0dGVyPwogICAgICAgICAgICB4LnJpZ2h0ID0gZGVsZXRlX21pbiEodGVtcCkKICAgICAgICBlbmQKICAgICAgICB4ID0gc2l6ZSEoeC5sZWZ0KSArIHNpemUhKHgucmlnaHQpICsgMQogICAgICAgIHgKICAgIGVuZAogICAgCiAgICBkZWYgc2VsZi5zaXplISh4KQogICAgICAgIGlmIHggPT0gbmlsCiAgICAgICAgICAgIDAKICAgICAgICBlbHNlCiAgICAgICAgICAgIHguc2l6ZQogICAgICAgIGVuZAogICAgZW5kCiAgICAKICAgIGRlZiBzZWxmLmluc2VydF9oZWxwZXIhKHgsIGssIHYpCiAgICAgICAgaWYgeCA9PSBuaWwKICAgICAgICAgICAgcmV0dXJuIEJTVE5vZGUubmV3KGssIHYsIDEpCiAgICAgICAgZWxzaWYgayA8IHgua2V5CiAgICAgICAgICAgIHgubGVmdCA9IGluc2VydF9oZWxwZXIhKHgubGVmdCwgaywgdikKICAgICAgICBlbHNpZiBrID4geC5rZXkKICAgICAgICAgICAgeC5yaWdodCA9IGluc2VydF9oZWxwZXIhKHgucmlnaHQsIGssIHYpCiAgICAgICAgZWxzZQogICAgICAgICAgICB4LnZhbHVlID0gdgogICAgICAgIGVuZAogICAgICAgIHguc2l6ZSA9IHNpemUhKHgubGVmdCkgKyBzaXplISh4LnJpZ2h0KSArIDEKICAgICAgICB4CiAgICBlbmQKZW5kCgpiID0gQlNULm5ldwpiLmluc2VydCg1LCAiYyIpCmIuaW5zZXJ0KDQsICJiIikKYi5pbnNlcnQoNiwgImQiKQpiLmluc2VydCgzLCAiYSIpCmIuaW5zZXJ0KDcsICJlIikKYi5pbm9yZGVyCnAgYi5nZXQoMykKYi5kZWxldGUoNikKYi5pbm9yZGVyCgoKZGVmIG1pcnJvcmVkPyhsZWZ0LCByaWdodCkKICAgIHJldHVybiAobGVmdCA9PSBuaWwgJiYgcmlnaHQgPT0gbmlsKSBpZiByaWdodCA9PSBuaWwgfHwgbGVmdCA9PSBuaWwKICAgIGxlZnQudmFsdWUgPT0gcmlnaHQudmFsdWUgJiYgbWlycm9yZWQ/KGxlZnQubGVmdCwgcmlnaHQucmlnaHQpICYmIG1pcnJvcmVkKGxlZnQucmlnaHQsIHJpZ2h0LmxlZnQpCmVuZAoKCiMgVGhpcyBjb2RlIGNhbiBiZSB1c2VkIHRvIG1ha2UgQlNUIGludG8gYmFsYW5jZWQgQlNUCmEgPSBbNSw3LDEyLDE1LDE4LDIwXQojIE5vbmRlY3JlYXNpbmcgYXJyYXkgdG8gYmFsYW5jZWQgQlNUCmRlZiBhcnJ0b2JzdChhLCBic3QpCiAgICBpZiBhLmxlbmd0aCA9PSAxCiAgICAgICAgcCBhWzBdCiAgICAgICAgYnN0Lmluc2VydChhWzBdLCAidGVtcCIpCiAgICBlbHNpZiBhLmxlbmd0aCA+IDEKICAgICAgICBtaWRfaWR4ID0gYS5sZW5ndGgvMgogICAgICAgIHAgYVttaWRfaWR4XQogICAgICAgIGJzdC5pbnNlcnQoYVttaWRfaWR4XSwgInRlbXAiKQogICAgICAgIGFycnRvYnN0KGEudGFrZShtaWRfaWR4KSwgYnN0KQogICAgICAgIGFycnRvYnN0KGEuZHJvcChtaWRfaWR4ICsgMSksIGJzdCkKICAgIGVuZAplbmQKYTIgPSBbMSwyLDMsNCw1XQpwICJBcnJheSB0byBCU1QiCmJzdHJlZSA9IEJTVC5uZXcKYXJydG9ic3QoYSwgYnN0cmVlKQpic3RyZWUuaW5vcmRlcgpidHQgPSBCU1QubmV3CmJ0dCA9IGFycnRvYnN0KGEyLCBidHQpCmJ0dC5pbm9yZGVy