class DSA::BasicBinarySearchTree
A basic binary search tree(or ordered map), with no specific self balancing
Public Class Methods
new()
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 18 def initialize @root = nil end
Public Instance Methods
[](key)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 38 def [](key) return nil if @root.nil? node = find_node @root, key if node node.value else nil end end
[]=(key, value)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 22 def []=(key, value) new_node = BasicBinarySearchTreeNode.new(key, value) if @root.nil? @root = new_node else insert(@root, new_node) end end
bfs_print()
click to toggle source
breadth first traversal
# File lib/DSA/binary_search_tree.rb, line 190 def bfs_print puts '=' * 100 level = [@root] until level.empty? next_level = [] level.each do |node| if node printf "<#{node.key}, #{node.value}>" printf "(parent_is_#{node.parent.key})\t" if node != @root next_level.push node.left next_level.push node.right else printf "<Nil>\t" next_level.push nil next_level.push nil end end puts if next_level.count(nil) < next_level.length level = next_level else level = [] end end puts '=' * 100 end
delete(key)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 31 def delete(key) return nil if @root.nil? node = find_node @root, key return nil if node.nil? delete_node(node).first.value end
each()
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 160 def each return if @root.nil? if block_given? in_order_traversal @root, Proc.new else Enumerator.new do |y| each do |key, value| y << [key, value] end end end end
ge(key) { |key, value| ... }
click to toggle source
yield the key/value pair for all those great than or equal to input key
# File lib/DSA/binary_search_tree.rb, line 103 def ge(key) return nil if @root.nil? if block_given? node = find_node @root, key yield [node.key, node.value] if node node = find_gt_node @root, key if node yield [node.key, node.value] loop do node = in_order_next_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| ge(key) do |key, value| y << [key, value] end end end end
gt(key) { |key, value| ... }
click to toggle source
yield the key/value pair for all those great than input key
# File lib/DSA/binary_search_tree.rb, line 49 def gt(key) return nil if @root.nil? if block_given? node = find_gt_node @root, key if node yield [node.key, node.value] loop do node = in_order_next_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| gt(key) do |key, value| y << [key, value] end end end end
le(key) { |key, value| ... }
click to toggle source
yield the key/value pair for all those great than or equal to input key
# File lib/DSA/binary_search_tree.rb, line 131 def le(key) return nil if @root.nil? if block_given? node = find_node @root, key yield [node.key, node.value] if node node = find_lt_node @root, key if node yield [node.key, node.value] loop do node = in_order_prev_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| le(key) do |key, value| y << [key, value] end end end end
lt(key) { |key, value| ... }
click to toggle source
yield the key/value pair for all those less than input key
# File lib/DSA/binary_search_tree.rb, line 77 def lt(key) return nil if @root.nil? if block_given? node = find_lt_node @root, key if node yield [node.key, node.value] loop do node = in_order_prev_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| lt(key) do |key, value| y << [key, value] end end end end
max()
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 181 def max if @root.nil? nil else max_node(@root).value end end
min()
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 173 def min if @root.nil? nil else min_node(@root).value end end
Protected Instance Methods
delete_node(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 282 def delete_node(node) if node.left.nil? && node.right.nil? # it's a leaf replace node, nil elsif ! node.left.nil? && node.right.nil? # only has a left child replace node, node.left elsif node.left.nil? && ! node.right.nil? # only has a right child replace node, node.right else # has both children next_node = min_node node.right node.key = next_node.key node.value = next_node.value delete_node next_node end end
find_gt_node(node, key)
click to toggle source
find first node that is greater than the key in a subtree
# File lib/DSA/binary_search_tree.rb, line 356 def find_gt_node(node, key) if key == node.key in_order_next_node node elsif key < node.key if node.left find_gt_node node.left, key else node end else if node.right find_gt_node node.right, key else in_order_next_node node end end end
find_lt_node(node, key)
click to toggle source
find first node that is less than the key in a subtree
# File lib/DSA/binary_search_tree.rb, line 376 def find_lt_node(node, key) if key == node.key in_order_prev_node node elsif key < node.key if node.left find_lt_node node.left, key else in_order_prev_node node end else if node.right find_lt_node node.right, key else node end end end
find_node(node, key)
click to toggle source
find a node through a key in a subtree
# File lib/DSA/binary_search_tree.rb, line 336 def find_node(node, key) if node.key == key node elsif key < node.key if node.left find_node node.left, key else nil end else if node.right find_node node.right, key else nil end end end
in_order_next_node(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 218 def in_order_next_node(node) # if it has a right subtree, take the left most of right subtree if !node.right.nil? return min_node node.right # if it is a left child, take the parent # if it is a right child, go up till we find a left child's parent, otherwise finished else while !node.nil? return node.parent if left_child? node node = node.parent end end nil end
in_order_prev_node(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 235 def in_order_prev_node(node) # if it has a left subtree, take the right most of left subtree if !node.left.nil? return max_node node.left # if it is a right child, take the parent # if it is a left child, go up till we find a right child's parent, otherwise finished else while !node.nil? return node.parent if right_child? node node = node.parent end end nil end
in_order_traversal(node, block)
click to toggle source
in-order traversal
# File lib/DSA/binary_search_tree.rb, line 272 def in_order_traversal(node, block) unless node.left.nil? in_order_traversal(node.left, block) end block.call(node.key, node.value) unless node.right.nil? in_order_traversal(node.right, block) end end
insert(node, new_node)
click to toggle source
insert a new node into the binary search (sub)tree
# File lib/DSA/binary_search_tree.rb, line 396 def insert(node, new_node) if node.key == new_node.key node.value = new_node.value return node elsif new_node.key < node.key if node.left.nil? node.left = new_node new_node.parent = node return new_node else insert( node.left, new_node ) end else if node.right.nil? node.right = new_node new_node.parent = node return new_node else insert( node.right, new_node ) end end end
left_child?(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 252 def left_child?(node) parent = node.parent if parent parent.left == node else false end end
max_node(node)
click to toggle source
find the maximum node of a subtree
# File lib/DSA/binary_search_tree.rb, line 327 def max_node(node) if node.right.nil? node else max_node node.right end end
min_node(node)
click to toggle source
find the minimum node of a subtree
# File lib/DSA/binary_search_tree.rb, line 318 def min_node(node) if node.left.nil? node else min_node node.left end end
replace(node, new_node)
click to toggle source
replace a node with another node, this includes the links that node has
# File lib/DSA/binary_search_tree.rb, line 298 def replace(node, new_node) if node == @root @root = new_node sibling = nil else parent = node.parent if parent.left == node parent.left = new_node sibling = parent.right else parent.right = new_node sibling = parent.left end new_node.parent = parent unless new_node.nil? end [node, new_node, sibling] end
right_child?(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 261 def right_child?(node) parent = node.parent if parent parent.right == node else false end end