SUNY Geneseo Department of Computer Science

Trees in Arrays

Return to List of Lectures

Misc

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo
• 2 responses now

Problem Set 13 due today

Lab 12 due tomorrow

Questions?

A Representation for Complete Trees

Section 14.2.4

• Using arrays to represent rows/levels of nodes in trees
• Easy to keep track of where next spot is
  • Rows start at 1, 2, generally 2^k-1 for row k
  • Row k ends at 2^k - 1
• Parents and children easy to find
  • Left child of node n is 2n
  • Right child is 2n + 1
  • Parent is floor( n/2 )

What would the equations for left, right, and parent look like if array indices started at 0 rather than 1?

• Left child of n = 2(n + 1) -1 = 2n + 1
• Right child = 2(n+1) = 2n + 2
• Parent = floor( (n-1)/2 )

Develop equations for mapping trinary trees into arrays.

• Left child of node n = 3n + 1
• Center child = 3n + 2
• Right child = 3n + 3
• Parent = floor( (n-1) / 3 )
• 0-origin indexing
• k-ary tree
  • Child i of node n = kn + i
  • Parent of node n = floor( (n-1)/k )
  • How do you know this "works"?
    • Criteria:
    • Each node can have k children
    • No two parents have same child
      • Node n-1's children can't collide with node n's because k(n-1) + i < kn + j as long as 1 <= i,j <= k
      • Generalize to nodes n, m, either by an inductive argument based on the above, or by extending the algebra to arbitrary node numbers n and m.

Hand out Problem Set 14

Hand out Lab 13

Next

More on heap insertion

Finish section 14.4

• Read from "Insertion" (page 500) through end (page 503)