Class: Albizia::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/albizia/node.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(v = nil) ⇒ Node 



7
8
9
10
 
# File 'lib/albizia/node.rb', line 7

def initialize(v=nil)
  @value = v
  @parent = nil
end

Instance Attribute Details

#left_child ⇒ Object

Returns the value of attribute left_child.



5
6
7
 
# File 'lib/albizia/node.rb', line 5

def left_child
  @left_child
end

#parent ⇒ Object

Returns the value of attribute parent.



5
6
7
 
# File 'lib/albizia/node.rb', line 5

def parent
  @parent
end

#right_child ⇒ Object

Returns the value of attribute right_child.



5
6
7
 
# File 'lib/albizia/node.rb', line 5

def right_child
  @right_child
end

#value ⇒ Object

Returns the value of attribute value.



5
6
7
 
# File 'lib/albizia/node.rb', line 5

def value
  @value
end

Instance Method Details

#<(other) ⇒ Object 



70
71
72
 
# File 'lib/albizia/node.rb', line 70

def <(other)
  @value < other.value
end

#<=>(other) ⇒ Object 



74
75
76
77
78
79
80
81
82
 
# File 'lib/albizia/node.rb', line 74

def <=>(other)
  if @value < other.value
    -1
  elsif @value == other.value
    0
  else
    1
  end
end

#>(other) ⇒ Object 



66
67
68
 
# File 'lib/albizia/node.rb', line 66

def >(other)
  @value > other.value
end

#add(v) ⇒ Object Also known as: <<

Add a node with value equals to v in the tree



142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/albizia/node.rb', line 142

def add(v)
  if empty?
    @value = v
  elsif v > @value
    if(@right_child.nil?)
      node = Node.new(v).tap { |n| n.parent = self }
      @right_child = node
      # return node
    else
      @right_child.add(v)
    end
  else
    if @left_child.nil?
      node = Node.new(v).tap { |n| n.parent = self }
      @left_child = node
      # return node
    else
      @left_child.add(v)
    end
  end
end

#ancestors ⇒ Object

All nodes above current node



89
90
 
# File 'lib/albizia/node.rb', line 89

def ancestors
end

#balanced? ⇒ Boolean 



109
110
 
# File 'lib/albizia/node.rb', line 109

def balanced?
end

#degenerated? ⇒ Boolean 



112
113
 
# File 'lib/albizia/node.rb', line 112

def degenerated?
end

#depth ⇒ Object

The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.



34
35
36
 
# File 'lib/albizia/node.rb', line 34

def depth
  root? ? 0 : 1 + parent.depth
end

#draw ⇒ Object

Draw the tree in the console example :

  5
/  \

2 10

 / \
6  12



204
205
206
 
# File 'lib/albizia/node.rb', line 204

def draw

end

#empty? ⇒ Boolean 



12
13
14
 
# File 'lib/albizia/node.rb', line 12

def empty?
  leaf? && @value.nil?
end

#full? ⇒ Boolean

A tree is full if every nodes except leaves has 2 children



106
107
 
# File 'lib/albizia/node.rb', line 106

def full?
end

#height(opts = {}) ⇒ Object

The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.

Available options :

initial : this will mark the current node as a root.



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/albizia/node.rb', line 45

def height(opts={})
  if empty?
    -1
  elsif (root? && leaf?) || (opts[:initial] && leaf?)
    0
  elsif leaf?
    1
  else
    current_height = (root? || opts[:initial]) ? 0 : 1
    if @left_child.nil? && @right_child != nil
      current_height + @right_child.height
    elsif @left_child != nil && @right_child.nil?
      current_height + @left_child.height
    elsif @left_child != nil && @right_child != nil
      current_height + [@left_child.height, @right_child.height].max
    else
      raise "Unhandled depth case"
    end
  end
end

#leaf? ⇒ Boolean

A leaf node has no children



17
18
19
 
# File 'lib/albizia/node.rb', line 17

def leaf?
  @left_child.nil? && @right_child.nil?
end

#max ⇒ Object

Return the highest value in the tree



116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/albizia/node.rb', line 116

def max
  if @right_child.nil?
    if empty?
      nil
    else
      self
    end
  else
    @right_child.max
  end
end

#min ⇒ Object

Return the lowest value in the tree



129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/albizia/node.rb', line 129

def min
  if @left_child.nil?
    if empty?
      nil
    else
      self
    end
  else
    @left_child.min
  end
end

#root ⇒ Object

Return the root element of the tree



27
28
29
 
# File 'lib/albizia/node.rb', line 27

def root
  root? ? self : @parent.root
end

#root? ⇒ Boolean

A root has no parent



22
23
24
 
# File 'lib/albizia/node.rb', line 22

def root?
  @parent.nil?
end

#siblings ⇒ Object

Siblings are nodes that share the same parent node.



85
86
 
# File 'lib/albizia/node.rb', line 85

def siblings
end

#size ⇒ Object

The size of a node is the number of descendants it has including itself.



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/albizia/node.rb', line 93

def size
  if leaf?
    1
  elsif @left_child.nil?
    1 + @right_child.size
  elsif @right_child.nil?
    1 + @left_child.size
  else
    1 + @left_child.size + @right_child.size
  end
end

#to_a ⇒ Object

Traverse the tree and returns the list of elements For the following tree :

  5
/  \

2 10

 / \
6  12

It return [2, 5, 6, 10, 12]



176
177
178
 
# File 'lib/albizia/node.rb', line 176

def to_a

end

#to_hash ⇒ Object

Traverse the tree and return elements in a hash: For the following tree :

  5
/  \

2 10

 / \
6  12

It returns { :“5” => { :“2” => nil, :“10” => { :“6” => nil, :“12” => nil } } }



191
192
193
 
# File 'lib/albizia/node.rb', line 191

def to_hash

end