Class: DataStructures::BinarySearchTree::Node

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

Constant Summary collapse

LESS_THAN_OTHER = 
-1
GREATER_THAN_OTHER = 
1

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(element) ⇒ Node

Returns a new instance of Node.



83
84
85
 
# File 'lib/data_structures/binary_search_tree.rb', line 83

def initialize(element)
  @element = element
end

Instance Attribute Details

#element ⇒ Object

Returns the value of attribute element.



81
82
83
 
# File 'lib/data_structures/binary_search_tree.rb', line 81

def element
  @element
end

#left_child ⇒ Object

Returns the value of attribute left_child.



81
82
83
 
# File 'lib/data_structures/binary_search_tree.rb', line 81

def left_child
  @left_child
end

#right_child ⇒ Object

Returns the value of attribute right_child.



81
82
83
 
# File 'lib/data_structures/binary_search_tree.rb', line 81

def right_child
  @right_child
end

Instance Method Details

#has_left_child? ⇒ Boolean

Returns:

  • (Boolean) 


155
156
157
 
# File 'lib/data_structures/binary_search_tree.rb', line 155

def has_left_child?
  not left_child.nil?
end

#has_right_child? ⇒ Boolean

Returns:

  • (Boolean) 


159
160
161
 
# File 'lib/data_structures/binary_search_tree.rb', line 159

def has_right_child?
  not right_child.nil?
end

#has_two_children? ⇒ Boolean

Returns:

  • (Boolean) 


141
142
143
 
# File 'lib/data_structures/binary_search_tree.rb', line 141

def has_two_children?
  has_left_child? and has_right_child?
end

#insert(element) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/data_structures/binary_search_tree.rb', line 87

def insert(element)
  case @element <=> element
  when LESS_THAN_OTHER
    if has_left_child?
      left_child.insert(element)
    else
      @left_child = DataStructures::BinarySearchTree::Node.new(element)
      return true
    end
  when GREATER_THAN_OTHER
    if has_right_child?
      right_child.insert(element)
    else
      @right_child = DataStructures::BinarySearchTree::Node.new(element)
      return true
    end
  else
    return false
  end
end

#left_ancestors ⇒ Object 



145
146
147
148
149
150
151
152
153
 
# File 'lib/data_structures/binary_search_tree.rb', line 145

def left_ancestors
  left_ancestors = []
  node = self
  until node.nil?
    left_ancestors << node
    node = node.left_child
  end
  left_ancestors
end

#remove(element) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/data_structures/binary_search_tree.rb', line 108

def remove(element)
  case @element <=> element
  when LESS_THAN_OTHER
    if has_left_child?
      @left_child = left_child.remove(element)
    else
      nil
    end
  when GREATER_THAN_OTHER
    if has_right_child?
      @right_child = right_child.remove(element)
    else
      nil
    end
  else
    if has_two_children?
      node = left_child
      while(node.has_right_child?)
        node = node.right_child
      end
      @left_child = left_child.remove(node.element)


    elsif has_left_child?
      left_child
    elsif has_right_child?
      right_child
    else
      nil
    end
  end
end