Class: SplayTree::Node

Inherits:
Object
  • Object
show all
Includes:
Comparable
Defined in:
lib/splay_tree/node.rb

Overview

A single tree node representation

Direct Known Subclasses

EmptyNode

Defined Under Namespace

Classes: EmptyNode

Constant Summary collapse

UndefinedValue = 
Module.new
EMPTY =

EmptyNode

Node::EmptyNode.new.freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value) ⇒ Node

Returns a new instance of Node.



18
19
20
21
 
# File 'lib/splay_tree/node.rb', line 18

def initialize(key, value)
  @key, @value = key, value
  @left = @right = Node::EMPTY
end

Instance Attribute Details

#key ⇒ Object (readonly)

Returns the value of attribute key.



10
11
12
 
# File 'lib/splay_tree/node.rb', line 10

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



14
15
16
 
# File 'lib/splay_tree/node.rb', line 14

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



16
17
18
 
# File 'lib/splay_tree/node.rb', line 16

def right
  @right
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



12
13
14
 
# File 'lib/splay_tree/node.rb', line 12

def value
  @value
end

Instance Method Details

#<=>(other) ⇒ Integer

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Compare node keys

Returns:

API:

  • private



42
43
44
 
# File 'lib/splay_tree/node.rb', line 42

def <=>(other)
  @key <=> other.key
end

#dump ⇒ String

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Dump the subtree structure starting from this node

Returns:

API:

  • private



74
75
76
77
78
79
80
81
82
 
# File 'lib/splay_tree/node.rb', line 74

def dump
  left = @left.dump
  right = @right.dump
  if !@left.empty? || !@right.empty?
    "(" + [@key, left || "-", right || "-"].compact.join(" ") + ")"
  else
    @key || ""
  end
end

#each {|[@key, @value]| ... } ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Iterate over subtree nodes

Yields:

API:

  • private



49
50
51
52
53
 
# File 'lib/splay_tree/node.rb', line 49

def each(&block)
  @left.each(&block)
  yield [@key, @value]
  @right.each(&block)
end

#each_key ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Iterate over subtree nodes

API:

  • private



58
59
60
 
# File 'lib/splay_tree/node.rb', line 58

def each_key
  each { |k, _| yield k }
end

#each_value ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Iterate over subtree nodes

API:

  • private



65
66
67
 
# File 'lib/splay_tree/node.rb', line 65

def each_value
  each { |_, v| yield v }
end

#empty? ⇒ Boolean

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns:

API:

  • private



24
25
26
 
# File 'lib/splay_tree/node.rb', line 24

def empty?
  false
end

#insert(key, value) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Insert new root

API:

  • private



119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/splay_tree/node.rb', line 119

def insert(key, value)
  case key <=> @key
  when -1
    @left = @left.insert(key, value)
    rotate_right
  when 0
    @value = value
    self
  when 1
    @right = @right.insert(key, value)
    rotate_left
  else
    raise TypeError, "Cannot compare: #{key} with #{@key}"
  end
end

#rotate_left ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Rotate left

 Y            X
/ \          / \

A X => Y C

 / \      / \
B   C    A   B

API:

  • private



109
110
111
112
113
114
 
# File 'lib/splay_tree/node.rb', line 109

def rotate_left
  tmp      = @right
  @right   = tmp.left
  tmp.left = self
  tmp
end

#rotate_right ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Rotate right

   Y         X
  / \       / \
 X   C  => A   Y
/ \           / \

A B B C

API:

  • private



93
94
95
96
97
98
 
# File 'lib/splay_tree/node.rb', line 93

def rotate_right
  tmp       = @left
  @left     = tmp.right
  tmp.right = self
  tmp
end

#size ⇒ Integer

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Number of nodes in this subtree

Returns:

API:

  • private



33
34
35
 
# File 'lib/splay_tree/node.rb', line 33

def size
  left.size + 1 + right.size
end