Class: BinarySearch::RedBlackTree

Inherits:
Object
  • Object
show all
Defined in:
lib/binary_search/red_black_tree.rb,
lib/binary_search/red_black_tree/node.rb

Overview

Implements a Red-Black Tree, a self-balancing binary search tree

A Red-Black Tree is a type of self-balancing binary search tree that maintains balance through the use of node colors (red and black) and a set of properties:

  1. Every node is either red or black.

  2. The root is black.

  3. Every leaf (NIL) is black.

  4. If a node is red, then both its children are black.

  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

These properties ensure that the tree remains approximately balanced during insertions and deletions, guaranteeing O(log n) time complexity for basic operations like search, insert, and delete.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RedBlackTree

Initializes an empty Red-Black Tree



24
25
26
 
# File 'lib/binary_search/red_black_tree.rb', line 24

def initialize
  @root = nil
end

Instance Attribute Details

#root ⇒ Node? (readonly)

Returns The root node of the tree.

Returns:

  • (Node, nil) —

    The root node of the tree



21
22
23
 
# File 'lib/binary_search/red_black_tree.rb', line 21

def root
  @root
end

Instance Method Details

#find(key) ⇒ Node?

Finds a node with the given key

This method performs a standard binary search tree lookup.

Parameters:

  • key (Comparable) —

    The key to find

Returns:

  • (Node, nil) —

    The node with the given key, or nil if not found



109
110
111
112
113
114
115
116
117
 
# File 'lib/binary_search/red_black_tree.rb', line 109

def find(key)
  current = @root
  while current
    comparison = key <=> current.key
    return current if comparison == 0
    current = comparison < 0 ? current.left : current.right
  end
  nil
end

#insert(key) ⇒ void

This method returns an undefined value.

Inserts a new key into the tree

The insertion process involves:

  1. Performing a standard BST insertion

  2. Coloring the new node red

  3. Rebalancing the tree to maintain Red-Black properties

Parameters:

  • key (Comparable) —

    The key to insert



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
 
# File 'lib/binary_search/red_black_tree.rb', line 37

def insert(key)
  new_node = Node.new(key)
  if @root.nil?
    @root = new_node
    @root.color = :black
  else
    current = @root
    parent = nil
    while current
      parent = current
      comparison = key <=> current.key
      case comparison
      when -1
        current = current.left
      when 1
        current = current.right
      else
        # For duplicates, we'll add to the right
        current = current.right
      end
    end
    new_node.parent = parent
    comparison = key <=> parent.key
    if comparison <= 0
      parent.left = new_node
    else
      parent.right = new_node
    end
    fix_insert(new_node)
  end
end

#remove(key) ⇒ Node?

Removes a key from the tree

The removal process involves:

  1. Finding the node to be removed

  2. If the node has two children, replacing it with its successor

  3. Removing the node (or its successor)

  4. Rebalancing the tree if the removed node was black

Parameters:

  • key (Comparable) —

    The key to remove

Returns:

  • (Node, nil) —

    The removed node, or nil if the key was not found



79
80
81
82
83
84
 
# File 'lib/binary_search/red_black_tree.rb', line 79

def remove(key)
  node = find(key)
  return nil unless node

  remove_node(node)
end

#update(old_key, new_key) ⇒ Boolean?

Updates a key in the tree

This operation ensures that the tree structure remains valid after updating a key. It’s implemented as a removal of the old key followed by an insertion of the new key.

Parameters:

  • old_key (Comparable) —

    The key to update

  • new_key (Comparable) —

    The new key value

Returns:

  • (Boolean, nil) —

    true if updated, false if new_key already exists, nil if old_key not found



94
95
96
97
98
99
100
101
 
# File 'lib/binary_search/red_black_tree.rb', line 94

def update(old_key, new_key)
  node = find(old_key)
  return nil unless node
  return false if find(new_key)

  node.key = new_key
  true
end