Class: DS::RedBlackTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/ds/trees/red_black_tree.rb,
lib/ds/trees/red_black_tree/node.rb

Overview

Class implements Red Black Tree

Defined Under Namespace

Classes: Node

Constant Summary collapse

RED = 
true
BLACK = 
false

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(hash = nil) ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



12
13
14
15
16
17
 
# File 'lib/ds/trees/red_black_tree.rb', line 12

def initialize(hash = nil)
  @root = nil
  @size = 0
  @iterator = TreeWalker.new(root)
  hash.each { |k, v| insert(k, v) } if hash
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



9
10
11
 
# File 'lib/ds/trees/red_black_tree.rb', line 9

def root
  @root
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



10
11
12
 
# File 'lib/ds/trees/red_black_tree.rb', line 10

def size
  @size
end

Instance Method Details

#[](key) ⇒ Object 



42
43
44
 
# File 'lib/ds/trees/red_black_tree.rb', line 42

def [](key)
  get(key)
end

#[]=(key, value) ⇒ Object 



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

def []=(key, value)
  insert(key, value)
end

#each ⇒ Object 



46
47
48
49
 
# File 'lib/ds/trees/red_black_tree.rb', line 46

def each
  iterator = TreeWalker.new(root)
  iterator.traverse(:inorder) { |t| yield t }
end

#get(key, node = root) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/ds/trees/red_black_tree.rb', line 28

def get(key, node = root)
  x = node
  while x
    case key <=> x.key
    when -1
      x = x.left
    when 1
      x = x.right
    else
      return x.data
    end
  end
end

#insert(key, value) ⇒ Object 



19
20
21
22
 
# File 'lib/ds/trees/red_black_tree.rb', line 19

def insert(key, value)
  self.root = put(root, key, value)
  root.color = BLACK
end

#to_h ⇒ Object 



51
52
53
 
# File 'lib/ds/trees/red_black_tree.rb', line 51

def to_h
  each_with_object({}) { |n, h| h[n.key] = n.data }
end