Class: AVLTree::Node

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

Direct Known Subclasses

EmptyNode

Defined Under Namespace

Classes: EmptyNode

Constant Summary collapse

UNDEFINED = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value) ⇒ Node

Returns a new instance of Node.



10
11
12
13
14
 
# File 'lib/avl_tree.rb', line 10

def initialize(key, value)
  @key, @value = key, value
  @left = @right = EMPTY
  @height = 1
end

Instance Attribute Details

#height ⇒ Object (readonly)

Returns the value of attribute height.



7
8
9
 
# File 'lib/avl_tree.rb', line 7

def height
  @height
end

#key ⇒ Object (readonly)

Returns the value of attribute key.



7
8
9
 
# File 'lib/avl_tree.rb', line 7

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



8
9
10
 
# File 'lib/avl_tree.rb', line 8

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



8
9
10
 
# File 'lib/avl_tree.rb', line 8

def right
  @right
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



7
8
9
 
# File 'lib/avl_tree.rb', line 7

def value
  @value
end

Instance Method Details

#check_height ⇒ Object

for debugging



131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/avl_tree.rb', line 131

def check_height
  @left.check_height
  @right.check_height
  lh = @left.height
  rh = @right.height
  if (lh - rh).abs > 1
    puts dump_tree(STDERR)
    raise "height unbalanced: #{lh} #{height} #{rh}"
  end
  if (lh > rh ? lh : rh) + 1 != height
    puts dump_tree(STDERR)
    raise "height calc failure: #{lh} #{height} #{rh}"
  end
end

#delete(key) ⇒ Object

returns [deleted_node, new_root]



81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/avl_tree.rb', line 81

def delete(key)
  case key <=> @key
  when -1
    deleted, @left = @left.delete(key)
    [deleted, self.rotate]
  when 0
    [self, delete_self.rotate]
  when 1
    deleted, @right = @right.delete(key)
    [deleted, self.rotate]
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
end

#delete_max ⇒ Object 



105
106
107
108
109
110
111
112
 
# File 'lib/avl_tree.rb', line 105

def delete_max
  if @right.empty?
    [self, delete_self]
  else
    deleted, @right = @right.delete_max
    [deleted, rotate]
  end
end

#delete_min ⇒ Object 



96
97
98
99
100
101
102
103
 
# File 'lib/avl_tree.rb', line 96

def delete_min
  if @left.empty?
    [self, delete_self]
  else
    deleted, @left = @left.delete_min
    [deleted, rotate]
  end
end

#dump_sexp ⇒ Object 



120
121
122
123
124
125
126
127
128
 
# File 'lib/avl_tree.rb', line 120

def dump_sexp
  left = @left.dump_sexp
  right = @right.dump_sexp
  if left or right
    '(' + [@key, left || '-', right].compact.join(' ') + ')'
  else
    @key
  end
end

#dump_tree(io, indent = '') ⇒ Object 



114
115
116
117
118
 
# File 'lib/avl_tree.rb', line 114

def dump_tree(io, indent = '')
  @right.dump_tree(io, indent + '  ')
  io << indent << sprintf("#<%s:0x%010x %d %s> => %s", self.class.name, __id__, height, @key.inspect, @value.inspect) << $/
  @left.dump_tree(io, indent + '  ')
end

#each {|[@key, @value]| ... } ⇒ Object

inorder

Yields:



25
26
27
28
29
 
# File 'lib/avl_tree.rb', line 25

def each(&block)
  @left.each(&block)
  yield [@key, @value]
  @right.each(&block)
end

#each_key ⇒ Object 



31
32
33
34
35
 
# File 'lib/avl_tree.rb', line 31

def each_key
  each do |k, v|
    yield k
  end
end

#each_value ⇒ Object 



37
38
39
40
41
 
# File 'lib/avl_tree.rb', line 37

def each_value
  each do |k, v|
    yield v
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


16
17
18
 
# File 'lib/avl_tree.rb', line 16

def empty?
  false
end

#insert(key, value) ⇒ Object

returns new_root



52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/avl_tree.rb', line 52

def insert(key, value)
  case key <=> @key
  when -1
    @left = @left.insert(key, value)
  when 0
    @value = value
  when 1
    @right = @right.insert(key, value)
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  rotate
end

#keys ⇒ Object 



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

def keys
  collect { |k, v| k }
end

#retrieve(key) ⇒ Object

returns value



67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/avl_tree.rb', line 67

def retrieve(key)
  case key <=> @key
  when -1
    @left.retrieve(key)
  when 0
    @value
  when 1
    @right.retrieve(key)
  else
    nil
  end
end

#size ⇒ Object 



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

def size
  @left.size + 1 + @right.size
end

#values ⇒ Object 



47
48
49
 
# File 'lib/avl_tree.rb', line 47

def values
  collect { |k, v| v }
end