Class: DSA::RedBlackTree

Inherits:
BasicBinarySearchTree show all
Defined in:
lib/DSA/binary_search_tree.rb

Instance Method Summary collapse

Methods inherited from BasicBinarySearchTree

#[], #each, #ge, #gt, #initialize, #le, #lt, #max, #min

Constructor Details

This class inherits a constructor from DSA::BasicBinarySearchTree

Instance Method Details

#[]=(key, value) ⇒ Object 



448
449
450
451
452
453
454
455
456
457
 
# 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 ⇒ Object

breadth first traversal



467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
 
# 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) ⇒ Object 



459
460
461
462
463
464
 
# 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