Module: Lite::Containers::AvlTree::Balance

Included in:
Implementation
Defined in:
lib/lite/containers/avl_tree/balance.rb

Instance Method Summary collapse

Instance Method Details

#balance_factor(node) ⇒ Object 



64
65
66
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 64

def balance_factor(node)
  height(node.right) - height(node.left)
end

#height(node) ⇒ Object 



68
69
70
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 68

def height(node)
  node&.height || 0
end

#rebalance(node) ⇒ Object

rubocop:disable Metrics/AbcSize



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 7

def rebalance(node) # rubocop:disable Metrics/AbcSize
  case balance_factor(node)
  when -2
    if height(node.left.right) > height(node.left.left)
      rotate_left_right(node)
    else
      rotate_right(node)
    end
  when 2
    if height(node.right.left) > height(node.right.right)
      rotate_right_left(node)
    else
      rotate_left(node)
    end
  else
    update_height(node)
    node
  end
end

#rotate_left(node) ⇒ Object 



27
28
29
30
31
32
33
34
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 27

def rotate_left(node)
  right = node.right
  node.right = right.left
  right.left = node
  update_height node
  update_height right
  right
end

#rotate_left_right(node) ⇒ Object 



50
51
52
53
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 50

def rotate_left_right(node)
  node.left = rotate_left(node.left)
  rotate_right(node)
end

#rotate_right(node) ⇒ Object 



36
37
38
39
40
41
42
43
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 36

def rotate_right(node)
  left = node.left
  node.left = left.right
  left.right = node
  update_height node
  update_height left
  left
end

#rotate_right_left(node) ⇒ Object 



45
46
47
48
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 45

def rotate_right_left(node)
  node.right = rotate_right(node.right)
  rotate_left(node)
end

#update_height(node) ⇒ Object 



55
56
57
58
59
60
61
62
 
# File 'lib/lite/containers/avl_tree/balance.rb', line 55

def update_height(node)
  left_height = height(node.left)
  right_height = height(node.right)
  # rubocop:disable Style/MinMaxComparison
  max = left_height > right_height ? left_height : right_height
  # rubocop:enable Style/MinMaxComparison
  node.height = max + 1
end