Class: DS::Tree

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

Overview

Tree class

Direct Known Subclasses

BinaryTree, Trie

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil, parent = nil) ⇒ Tree

Returns a new tree.



10
11
12
13
14
 
# File 'lib/ds/trees/tree.rb', line 10

def initialize(value = nil, parent = nil)
  @data = value
  @parent = parent
  @children = []
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



7
8
9
 
# File 'lib/ds/trees/tree.rb', line 7

def children
  @children
end

#data ⇒ Object

Returns the value of attribute data.



6
7
8
 
# File 'lib/ds/trees/tree.rb', line 6

def data
  @data
end

#parent ⇒ Object (readonly)

Returns the value of attribute parent.



7
8
9
 
# File 'lib/ds/trees/tree.rb', line 7

def parent
  @parent
end

Class Method Details

.h(tree) ⇒ Object

Returns subtree height.



71
72
73
74
75
76
77
 
# File 'lib/ds/trees/tree.rb', line 71

def self.h(tree)
  if tree.leaf?
    1
  else
    tree.children.map { |t| h(t) }.max + 1
  end
end

Instance Method Details

#<<(value) ⇒ Object

Inserts a new subtree.



17
18
19
20
21
 
# File 'lib/ds/trees/tree.rb', line 17

def <<(value)
  subtree = Tree.new(value, self)
  @children << subtree
  subtree
end

#each ⇒ Object

Iterates tree in BFS order.



110
111
112
113
 
# File 'lib/ds/trees/tree.rb', line 110

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

#get_leaves(tree = self) ⇒ Object

Returns leaf list.



33
34
35
36
37
38
 
# File 'lib/ds/trees/tree.rb', line 33

def get_leaves(tree = self)
  list = List.new
  walker = TreeWalker.new(tree, order: :postorder)
  walker.traverse { |t| list.append(t) if t.leaf? }
  list
end

#height ⇒ Object

Returns tree height.



80
81
82
 
# File 'lib/ds/trees/tree.rb', line 80

def height
  Tree.h(self)
end

#izometric?(other) ⇒ Boolean

Checks if tree is isometric to another tree.

Returns:

  • (Boolean) 


97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/ds/trees/tree.rb', line 97

def izometric?(other)
  tree = self
  unless tree.leaf? && other.leaf?
    if tree.children.size == other.children.size
      tree.children.each_with_index { |t, i| return false unless t.izometric?(other.children[i]) }
    else
      return false
    end
  end
  true
end

#leaf? ⇒ Boolean

Checks if node is leaf.

Returns:

  • (Boolean) 


28
29
30
 
# File 'lib/ds/trees/tree.rb', line 28

def leaf?
  children.empty?
end

#leaf_count(tree = self) ⇒ Object

Returns the number of leaves for given subtree.



41
42
43
44
45
46
47
 
# File 'lib/ds/trees/tree.rb', line 41

def leaf_count(tree = self)
  if tree.leaf?
    1
  else
    tree.children.inject(0) { |a, e| a + leaf_count(e) }
  end
end

#levels ⇒ Object

Returns number of nodes for each tree level. 2=>4, 3=>5



51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/ds/trees/tree.rb', line 51

def levels
  walker = TreeWalker.new(self)
  nodes = {}

  walker.traverse_with_h(self, 1) do |_t, level|
    if nodes[level]
      nodes[level] += 1
    else
      nodes[level] = 1
    end
  end
  nodes
end

#lowest_height ⇒ Object

Returns node which lies closest to the root.



85
86
87
 
# File 'lib/ds/trees/tree.rb', line 85

def lowest_height
  find(&:leaf?)
end

#mirror!(tree = self) ⇒ Object

Mirrors tree.



90
91
92
93
94
 
# File 'lib/ds/trees/tree.rb', line 90

def mirror!(tree = self)
  return if tree.leaf?
  tree.children.reverse!
  tree.children.each { |t| mirror!(t) }
end

#sibblings ⇒ Object 



23
24
25
 
# File 'lib/ds/trees/tree.rb', line 23

def sibblings
  parent.children.reject { |node| node == self }
end

#to_a ⇒ Object 



115
116
117
 
# File 'lib/ds/trees/tree.rb', line 115

def to_a
  map(&:data)
end

#width ⇒ Object

Returns tree width.



66
67
68
 
# File 'lib/ds/trees/tree.rb', line 66

def width
  levels.values.max
end