Class: WindingPolygon::AVLTree

Inherits:
Object
  • Object
show all
Defined in:
lib/winding-polygon/avltree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array = []) ⇒ AVLTree

Returns a new instance of AVLTree.



4
5
6
7
8
9
10
 
# File 'lib/winding-polygon/avltree.rb', line 4

def initialize(array = [])
  #create root
  @root = nil
  array.each do |n|
    insert n
  end
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



3
4
5
 
# File 'lib/winding-polygon/avltree.rb', line 3

def root
  @root
end

Instance Method Details

#delete(v) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/winding-polygon/avltree.rb', line 60

def delete(v)
  d = search(v)
  return nil if d.nil?

  if @root.height==1 && @root.value==v
    @root = nil
    return nil
  end

  if d.left == nil or d.right == nil
    n = d
  else #both children exist
    n = d.next
  end

  if !n.left.nil?
    b = n.left
  else
    b = n.right
  end

  b.parent = n.parent unless b.nil?

  if n.parent.nil?
    @root = b
  elsif n == n.parent.left
    n.parent.left = b
  else
    n.parent.right = b
  end

  d.value = n.value unless n == d

  if b.nil?
    n.parent.update_height if !n.parent.nil?
    @root = n.balance
  else
    b.update_height
    @root = b.balance
  end
  n
end

#insert(v) ⇒ Object 



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/winding-polygon/avltree.rb', line 12

def insert(v)
  i_node = create_node(v)

  prev_node = nil
  curr_node = @root
  while !curr_node.nil?
    prev_node = curr_node
    if i_node.value < curr_node.value
      curr_node = curr_node.left
    else
      curr_node = curr_node.right
    end
  end

  if prev_node.nil?
    @root = i_node
  else
    i_node.parent = prev_node
    if i_node.value < prev_node.value
      prev_node.left = i_node
    else
      prev_node.right = i_node
    end
  end
  i_node.update_height
  @root = i_node.balance
  i_node
end

#max ⇒ Object 



118
119
120
 
# File 'lib/winding-polygon/avltree.rb', line 118

def max
  @root.max
end

#min ⇒ Object 



114
115
116
 
# File 'lib/winding-polygon/avltree.rb', line 114

def min
  @root.min
end

#print ⇒ Object 



103
104
105
106
 
# File 'lib/winding-polygon/avltree.rb', line 103

def print
  result = sort
  puts result.inspect
end

#scan(v) ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/winding-polygon/avltree.rb', line 45

def scan(v)
  current_node = @root
  while !current_node.nil?
    return current_node if current_node.value == v
    current_node = current_node.next
  end

  current_node = @root.prev
  while !current_node.nil?
    return current_node if current_node.value == v
    current_node = current_node.prev
  end
  current_node
end

#search(v) ⇒ Object 



41
42
43
 
# File 'lib/winding-polygon/avltree.rb', line 41

def search(v)
  search_node(@root, v)
end

#sort ⇒ Object 



108
109
110
111
112
 
# File 'lib/winding-polygon/avltree.rb', line 108

def sort
  result = Array.new
  sort_node(@root, result )
  result
end