Class: CompSci::BinarySearchTree

Inherits:
BinaryTree show all
Defined in:
lib/compsci/binary_search_tree.rb

Instance Attribute Summary

Attributes inherited from NaryTree

#child_slots

Attributes inherited from Tree

#root

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from NaryTree

#open_parent, #open_parent?, #open_sibling, power_of?, #push

Methods inherited from Tree

#bf_search, #df_search, #df_search_generic

Constructor Details

#initialize(root_node) ⇒ BinarySearchTree

Returns a new instance of BinarySearchTree.



28
29
30
31
32
33
34
35
36
 
# File 'lib/compsci/binary_search_tree.rb', line 28

def initialize(root_node)
  @node_class = root_node.class
  @child_slots = 2
  if root_node.children.size == @child_slots
    @root = root_node
  else
    raise "bad root: #{root_node}; expected #{@child_slots} child slots"
  end
end

Class Method Details

.display_level(nodes: [], width: 80) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
 
# File 'lib/compsci/binary_search_tree.rb', line 6

def self.display_level(nodes: [], width: 80)
  unless self.power_of?(nodes.size, 2)
    raise "unexpected node count: #{nodes.size}"
  end
  block_width = [width / nodes.size, 1].max
  nodes.map { |node|
    str = node ? node.to_s : '_'
    space = [(block_width + str.size) / 2, str.size + 1].max
    str.ljust(space, ' ').rjust(block_width, ' ')
  }.join
end

.new_node(key, val) ⇒ Object

helper method; any object which responds to key, value, and children may be used



20
21
22
 
# File 'lib/compsci/binary_search_tree.rb', line 20

def self.new_node(key, val)
  CompSci::KeyNode.new(val, key: key, children: 2)
end

.new_with_kv(key, val) ⇒ Object 



24
25
26
 
# File 'lib/compsci/binary_search_tree.rb', line 24

def self.new_with_kv(key, val)
  self.new(self.new_node(key, val))
end

Instance Method Details

#display(node: @root, width: 80) ⇒ Object Also known as: to_s 



71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/compsci/binary_search_tree.rb', line 71

def display(node: @root, width: 80)
  levels = [self.class.display_level(nodes: [node], width: width)]
  nodes = node.children
  while nodes.any? { |n| !n.nil? }
    levels << self.class.display_level(nodes: nodes, width: width)
    children = []
    nodes.each { |n|
      children += n ? n.children : Array.new(@child_slots)
    }
    nodes = children
  end
  levels.join("\n")
end

#insert_recursive(key, val, node: @root) ⇒ Object Also known as: insert 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/compsci/binary_search_tree.rb', line 52

def insert_recursive(key, val, node: @root)
  return nil if node.nil? or node.key == key
  if key < node.key
    if node.children[0]
      insert_recursive(key, val, node: node.children[0])
    else
      node.children[0] = @node_class.new(val, key: key, children: 2)
    end
  else
    if node.children[1]
      insert_recursive(key, val, node: node.children[1])
    else
      node.children[1] = @node_class.new(val, key: key, children: 2)
    end
  end
end

#search_iterative(key, node: @root) ⇒ Object 



44
45
46
47
48
49
50
 
# File 'lib/compsci/binary_search_tree.rb', line 44

def search_iterative(key, node: @root)
  while !node.nil?
    return node if node.key == key
    node = key < node.key ? node.children[0] : node.children[1]
  end
  node
end

#search_recursive(key, node: @root) ⇒ Object 



38
39
40
41
42
 
# File 'lib/compsci/binary_search_tree.rb', line 38

def search_recursive(key, node: @root)
  return node if node.nil? or node.key == key
  child = key < node.key ? node.children[0] : node.children[1]
  search_recursive(key, node: child)
end