Tree structure refresher

  • There are label on vertices and labels on branches
  • The labels on the branches (either 0 or 1) yield a vertex label which is the record of the path through a series of labeled branches that leads to that vertex.
  • Standard Binary tree
    • the branch labels follow a two bit pattern …0-1 | 0-1 | 0-1 | 0-1…
    • starting with row 1 (the row that has just two vertices labeled 0 and 1…we label the top [e]) copy the vertex labels from row n into the left and right halves of row n+1 and append a 0 to the front of the strings copied into the left half of row n+1 and a 1 to the front of the strings in the right half.
    • Row 2 vertices read 00-01-10-11.
    • Row 3 reads 000-001-010-011 | 100-101-110-111
    • etc.
  • The Discrete Derivative Tree
    • the branch labels follow the four bit pattern …0-1-1-0 | 0-1-1-0 | 0-1-1-0…
    • starting with row 1 (the row that has just two vertices labeled 0 and 1), copy the labels from row n into the left half of row n+1 and append a 0 to the front of each label, then copy the labels from row n in reverse order into the right half and append a 1 to the front of each string.
    • Row 2 labels read 00-01-11-10.
    • Row 3 reads 000-001-011-010 | 110-111-101-100
    • etc.

Published by Bob H

worker bee

Leave a comment