Class: DataStructures::BinarySearchTree

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures/binary_search_tree.rb

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



3
4
5
 
# File 'lib/data_structures/binary_search_tree.rb', line 3

def root
  @root
end

Instance Method Details

#get(element) ⇒ Object 



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/data_structures/binary_search_tree.rb', line 22

def get(element)
  if has_root?
    node = root
    until(node.element == element)
      case(node.element <=> element)
      when Node::LESS_THAN_OTHER
        if node.has_left_child?
          node = node.left_child
        end
      when Node::GREATER_THAN_OTHER
        if node.has_right_child?
          node = node.right_child
        end
      end
    end
    node.element
  else
    nil
  end
end

#in_order ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/data_structures/binary_search_tree.rb', line 47

def in_order
  if has_root?
    stack = Array.new
    node = root
    in_order_array = []
    in_order_array += node.left_ancestors.map(&:element)

    while(not stack.empty?)
      node = stack.pop
      in_order_array.push(node.element)
      if node.has_right_child?
        stack.push(node.right_child)
        node = node.right_child
        node.left_ancestors.each do |node|
          stack.push(node)
        end
      end
    end

    in_order_array
  else
    []
  end
end

#insert(element) ⇒ Object 



5
6
7
8
9
10
11
12
 
# File 'lib/data_structures/binary_search_tree.rb', line 5

def insert(element)
  if has_root?
    root.insert(element)
  else
    @root = DataStructures::BinarySearchTree::Node.new(element)
    true
  end
end

#remove(element) ⇒ Object 



14
15
16
17
18
19
20
 
# File 'lib/data_structures/binary_search_tree.rb', line 14

def remove(element)
  if has_root?
    @root = root.remove(element)
  else
    false
  end
end

#size ⇒ Object 



43
44
45
 
# File 'lib/data_structures/binary_search_tree.rb', line 43

def size
  in_order.size
end