blob: eb5de612bb179a7ee21b0afb1bc1e0db01efbef6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
class AVLTree
attr_reader :root
def push(item)
if @root
@root = @root.push(item)
else
@root = Node.new(item)
end
end
def size
return 0 unless @root
@root.size
end
def height
return 0 unless @root
@root.height
end
alias_method :add, :push
class Node
attr_accessor :data, :left, :right
def initialize(data)
@data = data
end
def push(item)
if (item <=> @data) == -1
@left.push(item) if @left
@left = Node.new(item) unless @left
else
@right.push(item) if @right
@right = Node.new(item) unless @right
end
re_balance
end
def size
result = 1
result += @left.size if @left
result += @right.size if @right
result
end
def height
result = 1
result += left_height >= right_height ? left_height : right_height
result
end
def re_balance
if balance_factor < -1
if @right.balance_factor == 1
right_left_case
else
right_right_case
end
elsif balance_factor > 1
if @left.balance_factor == -1
left_right_case
else
left_left_case
end
else
self
end
end
def balance_factor
(left_height - right_height) || 0
end
private
def right_left_case
right = @right
@right = right.left
@right.right = right
right.left = nil
right_right_case
end
def right_right_case
@right.left = self
new_root = @right
@right = nil
new_root
end
def left_right_case
left = @left
@left = @left.right
@left.left = left
left.right = nil
left_left_case
end
def left_left_case
@left.right = self
new_root = @left
@left = nil
new_root
end
def left_height
@left ? @left.height : 0
end
def right_height
@right ? @right.height : 0
end
end
end
|
