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:

  • (Integer) 


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:

  • (String) 


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:



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



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



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:

  • (Boolean) 


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



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



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



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:

  • (Integer) 


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

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