Class: AVLTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ AVLTree

Returns a new instance of AVLTree.



5
6
7
 
# File 'lib/nswtopo/avl_tree.rb', line 5

def initialize(&block)
  empty!
end

Instance Attribute Details

#height ⇒ Object

Returns the value of attribute height.



3
4
5
 
# File 'lib/nswtopo/avl_tree.rb', line 3

def height
  @height
end

#left ⇒ Object

Returns the value of attribute left.



3
4
5
 
# File 'lib/nswtopo/avl_tree.rb', line 3

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



3
4
5
 
# File 'lib/nswtopo/avl_tree.rb', line 3

def right
  @right
end

#value ⇒ Object

Returns the value of attribute value.



3
4
5
 
# File 'lib/nswtopo/avl_tree.rb', line 3

def value
  @value
end

Instance Method Details

#ancestors(node) ⇒ Object 



41
42
43
44
45
46
47
 
# File 'lib/nswtopo/avl_tree.rb', line 41

def ancestors(node)
  node.empty? ? [] : case [@value, @value.object_id] <=> [node.value, node.value.object_id]
  when +1 then [*@left.ancestors(node), self]
  when  0 then []
  when -1 then [*@right.ancestors(node), self]
  end
end

#balance ⇒ Object 



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

def balance
  empty? ? 0 : @left.height - @right.height
end

#delete(value) ⇒ Object 



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/nswtopo/avl_tree.rb', line 94

def delete(value)
  case [@value, @value.object_id] <=> [value, value.object_id]
  when +1 then @left.delete value
  when 0
    @value.tap do
      case
      when leaf? then empty!
      when @left.empty?
        node = @right.first_node
        @value = node.value
        node.replace_with node.right
        ancestors(node).each(&:rebalance) unless node.empty?
      else
        node = @left.last_node
        @value = node.value
        node.replace_with node.left
        ancestors(node).each(&:rebalance) unless node.empty?
      end
    end
  when -1 then @right.delete value
  end.tap { rebalance } unless empty?
end

#each(&block) ⇒ Object 



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

def each(&block)
  unless empty?
    @left.each &block
    block.call @value
    @right.each &block
  end
end

#empty! ⇒ Object 



13
14
15
 
# File 'lib/nswtopo/avl_tree.rb', line 13

def empty!
  @value, @left, @right, @height = nil, nil, nil, 0
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @value.nil?
end

#first_node ⇒ Object 



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

def first_node
  empty? || @left.empty? ? self : @left.first_node
end

#insert(value) ⇒ Object Also known as: << 



75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/nswtopo/avl_tree.rb', line 75

def insert(value)
  if empty?
    @value, @left, @right = value, AVLTree.new, AVLTree.new
  else
    case [@value, @value.object_id] <=> [value, value.object_id]
    when +1 then @left.insert value
    when  0 then @value = value
    when -1 then @right.insert value
    end
  end
  rebalance
end

#last_node ⇒ Object 



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

def last_node
  empty? || @right.empty? ? self : @right.last_node
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


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

def leaf?
  [@left, @right].all?(&:empty?)
end

#merge(values) ⇒ Object 



89
90
91
92
 
# File 'lib/nswtopo/avl_tree.rb', line 89

def merge(values)
  values.each { |value| insert value }
  self
end

#pop ⇒ Object 



117
118
119
 
# File 'lib/nswtopo/avl_tree.rb', line 117

def pop
  delete first_node.value unless empty?
end

#rebalance ⇒ Object 



63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/nswtopo/avl_tree.rb', line 63

def rebalance
  update_height
  case balance
  when +2
    @left.rotate_left if @left.balance == -1
    rotate_right
  when -2
    @right.rotate_right if @right.balance == 1
    rotate_left
  end unless empty?
end

#replace_with(node) ⇒ Object 



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

def replace_with(node)
  @value, @left, @right, @height = node.value, node.left, node.right, node.height
end

#rotate_left ⇒ Object 



49
50
51
52
53
54
 
# File 'lib/nswtopo/avl_tree.rb', line 49

def rotate_left
  a, b, c, v, @value = @left, @right.left, @right.right, @value, @right.value
  @left = @right
  @left.value, @left.left, @left.right, @right = v, a, b, c
  [@left, self].each(&:update_height)
end

#rotate_right ⇒ Object 



56
57
58
59
60
61
 
# File 'lib/nswtopo/avl_tree.rb', line 56

def rotate_right
  a, b, c, v, @value = @left.left, @left.right, @right, @value, @left.value
  @right = @left
  @left.value, @left, @right.left, @right.right = v, a, b, c
  [@right, self].each(&:update_height)
end

#update_height ⇒ Object 



29
30
31
 
# File 'lib/nswtopo/avl_tree.rb', line 29

def update_height
  @height = empty? ? 0 : [@left, @right].map(&:height).max + 1
end