Module: Lite::Containers::AvlTree::Delete

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

Instance Method Summary collapse

Instance Method Details

#delete(key, node) ⇒ Object

rubocop:disable Metrics/AbcSize, Metrics/CyclomaticComplexity



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

def delete(key, node) # rubocop:disable Metrics/AbcSize, Metrics/CyclomaticComplexity
  return [nil, nil] if node.nil?

  case compare(key, node.key)
  when -1
    deleted, node.left = delete(key, node.left)
    [deleted, rebalance(node)]
  when 0
    if node.left.nil? || node.right.nil?
      new_root = node.left.nil? ? node.right : node.left
      [node, new_root]
    else
      new_root = leftmost_child(node.right)
      _, new_root.right = delete(new_root.key, node.right)
      new_root.left = node.left
      [node, rebalance(new_root)]
    end
  when 1
    deleted, node.right = delete(key, node.right)
    [deleted, rebalance(node)]
  end
end