class DSA::RedBlackTree
Public Instance Methods
[]=(key, value)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 448 def []=(key, value) new_node = RedBlackTreeNode.new(key, value) if @root.nil? new_node.set_black! @root = new_node else node = insert(@root, new_node) fix_variance node if node.red? # when it is an existing node, it could be black end end
bfs_print()
click to toggle source
breadth first traversal
# File lib/DSA/binary_search_tree.rb, line 467 def bfs_print puts '=' * 100 level = [@root] until level.empty? next_level = [] level.each do |node| if node printf "<#{node.key}, #{node.value}>" printf "(#{node.parent.key}|" if node != @root if node.red? printf "R)\t" else printf "B)\t" end 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 459 def delete(key) return nil if @root.nil? node = find_node @root, key return nil if node.nil? rb_delete_node(node).first.value end
Private Instance Methods
deletion_restructure(node)
click to toggle source
rotations and re-color in different cases(zig-zig and zig-zag) for deletion
# File lib/DSA/binary_search_tree.rb, line 581 def deletion_restructure(node) parent = node.parent grand_parent = parent.parent if left_child?(node) && left_child?(parent) right_up_rotation parent if grand_parent.red? parent.set_red! else parent.set_black! end node.set_black! grand_parent.set_black! elsif right_child?(node) && left_child?(parent) left_up_rotation node right_up_rotation node if grand_parent.red? node.set_red! else node.set_black! end parent.set_black! grand_parent.set_black! elsif right_child?(node) && right_child?(parent) left_up_rotation parent if grand_parent.red? parent.set_red! else parent.set_black! end node.set_black! grand_parent.set_black! else right_up_rotation node left_up_rotation node if grand_parent.red? node.set_red! else node.set_black! end parent.set_black! grand_parent.set_black! end end
fix_deficit(sibling)
click to toggle source
the heavier side after a black leaf deleted
# File lib/DSA/binary_search_tree.rb, line 517 def fix_deficit(sibling) parent = sibling.parent if sibling.black? x = has_red_child? sibling if x deletion_restructure(x) else # if sibling does not have a red child sibling.set_red! if parent.red? parent.set_black! else fix_deficit sibling_of(parent) end end else # when my sibling is red if left_child? sibling heavy_node = sibling.right right_up_rotation sibling else heavy_node = sibling.left left_up_rotation sibling end sibling.set_black! parent.set_red! fix_deficit heavy_node end end
fix_variance(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 555 def fix_variance(node) # for root, recolor to black when necessary if node == @root node.set_black! if node.red? return end parent = node.parent return if parent.black? # we are good # otherwise we have the double red grand_parent = parent.parent uncle = sibling_of parent if uncle && uncle.red? parent.set_black! uncle.set_black! grand_parent.set_red! fix_variance grand_parent else restructure( node ) end end
has_red_child?(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 545 def has_red_child?(node) if node.left && node.left.red? node.left elsif node.right && node.right.red? node.right else nil end end
left_up_rotation(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 685 def left_up_rotation(node) parent = node.parent grand_parent = parent.parent node.parent = grand_parent if left_child? parent grand_parent.left = node elsif right_child? parent grand_parent.right = node else @root = node end parent.right = node.left node.left.parent = parent if node.left node.left = parent parent.parent = node end
rb_delete_node(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 500 def rb_delete_node(node) node, replace_node, sibling = delete_node(node) value = [node, replace_node] return value if node.red? # red is always fine if node.black? if replace_node # if it has a child(the replace_node), it must be red replace_node.set_black! else # it is a black leaf, it is complicated fix_deficit sibling end end value end
restructure(node)
click to toggle source
rotations and re-color in different cases(zig-zig and zig-zag) for insertion
# File lib/DSA/binary_search_tree.rb, line 626 def restructure(node) parent = node.parent grand_parent = parent.parent if left_child?(node) && left_child?(parent) right_up_rotation parent parent.set_black! node.set_red! grand_parent.set_red! elsif right_child?(node) && left_child?(parent) left_up_rotation node right_up_rotation node node.set_black! parent.set_red! grand_parent.set_red! elsif right_child?(node) && right_child?(parent) left_up_rotation parent parent.set_black! node.set_red! grand_parent.set_red! else right_up_rotation node left_up_rotation node node.set_black! parent.set_red! grand_parent.set_red! end end
right_up_rotation(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 664 def right_up_rotation(node) parent = node.parent grand_parent = parent.parent node.parent = grand_parent if left_child? parent grand_parent.left = node elsif right_child? parent grand_parent.right = node else @root = node end parent.left = node.right node.right.parent = parent if node.right node.right = parent parent.parent = node end
sibling_of(node)
click to toggle source
# File lib/DSA/binary_search_tree.rb, line 654 def sibling_of(node) parent = node.parent return nil if parent.nil? if left_child? node parent.right else parent.left end end