CS101 - Discrete Math

Robert Batzinger
Dec 2 17

Unit 4 - Trees

Unit 4
Trees

\[ \]

Contents

Some basic properties of Trees

  • There is a single entry (ROOT)
  • The ORDER of the tree is the number of branches per node
  • Each branch acts as an independant subtree
  • Recursion is the most common programming technique for creating tree support functions

plot of chunk unnamed-chunk-1

Filling Trees

  • Minimum number of levels required: \[ L = \left\lceil \log_2(n) \right\rceil \]
  • Capacity of a binary tree: \[ N = 2^L - 1 \]
  • Number of remainder in the last row of a balanced tree \[ R = n - 2^{L-1} - 1 \]

A Balanced Tree

  • fill all lower levels before opening a new one
  • Uses the smallest number of levels

plot of chunk unnamed-chunk-2

Trees of different orders

plot of chunk unnamed-chunk-3

plot of chunk unnamed-chunk-4

Capacities for Different Order of Tree

\[ \begin{array}{lllllc} Order & 2 & 3 & 4 & 5\\ \hline 1 & 1 & 1 & 1 & 1 \\ 2 & 3 & 4 & 5 & 6 \\ 3 & 7 & 13 & 21 & 31 \\ 4 & 15 & 40 & 85 & 156 \\ 5 & 31 & 121 & 341 & 781 \\ 6 & 63 & 364& 1365 & 3906 \\ 7 & 127 & 1093 & 4461 & 19531 \\ 8 & 255 & 3280 & 20845 & 97656 \\ \end{array} \]

plot of chunk unnamed-chunk-5

Nodes

attr_accessor :value, :leftNode, :rightNode

def initialize(value)
  @value = value
  @leftNode = nil
  @rightNode = nil
end

Sorted Trees

Data order: 

6 5 7 8 2 4 9 3 1

Tree Shape Animation

Creating Sorted Trees

def addnode(n)
  if @root.nil?
    @root = n
  else
    locate_Addnode(n)
  end
end

def locate_addNode(n)
  next = @root
  last = nil
  until next.nil?
    last = next
    if next.value > n.value
      next = leftNode
    else
      next = rightNode
  end
  if last.value > n.value
    last.leftNode = n
  else
    last.rightNode = n
  end
end

Printing a sorted tree

def printtree(node)
  if !node.nil?
    printTree(node.leftnode)
    puts node.value
    printTree(node.rightnode)
  end
end

Self balancing BTrees

BTree Animation

BTree of Order 3 BTree of Order 5

  • Self-balancing
  • Most efficent if the nodes are 75% full
  • Search performance improves with size of node
  • Insertion delays occurs only when full

Minimal Spanning Trees

Dendrogram

Minimal Spanning Tree

spanning

Simple Dendrogram

plot of chunk unnamed-chunk-10

\[ 1,3,4,8,13,17,18,19 \]

Dendrogram of Old Faithful

plot of chunk unnamed-chunk-11

Old Faithful

Draw a hull around a set of points

  • Start with the leftmost point (and lowest point if there is a tie)
  • Assume a vector pointed down as the key vector
  • Repeat the following until we arrive back at the original point
    • Measure the angle to all of the points
    • Choose the point with the smallest angle
    • The new line becomes the key vector

plot of chunk unnamed-chunk-12