From charlesreid1

Definitions and Variations

Definitions

tree - collection of nodes that is either empty, or consists of a root node with 0 or more non-empty subtrees connected to the root by a directed edge

node - element of a tree that stores data and has a directed edge connecting it to a parent (unless it is the root node) and one or more children

parent - the node above a given node that is referred to directly

child - the node below a given node that is referred to directly

root - top-level root in tree, only node with no parent

siblings - two nodes that share a parent

internal - a node with one or more children

external/leaf - a node with no children

descendant - a node is a descendant of another node if it is a child of that node or a child of its children

ancestor - a node is an ancestor of another node if it is a parent of that node or its parent

abstract class - clas that is intended to be implemented and lacks implementation details

concrete class - actually implements details of the class

depth of node p - number of ancestors of p, excluding p (depth of root is 0)

Recursive definition of depth: if p is root, 0; otherwise, 1 + depth of parent

height of node - number (max) of nodes to get to a leaf

Recursive definition of height: if p is a leaf, height is 0; otherwise, max( 1 + depth(child)) for child in children

binary tree - ordered tree with left or right children

proper binary tree - each node has 0 or 2 children

full binary tree - same thing as proper

complete binary tree - (think heaps) each hierarchical level of the tree is populated completely before moving on to the next hierarchical level

level numbering - utilized for array-based binary tree storage

traversal - way of accessing each node

preorder traversal - traversal in which ROOT node is visited FIRST

postorder traversal - traversal in which CHILDREN nodes are visited FIRST

breadth-first traversal - traversal that visits all nodes of depth d before visiting any nodes of depth d+1

in-order traversal - traversal in which LEFT children are visited, then NODE is visited, then RIGHT children are visited

binary search tree - binary tree in which left node value > this node value > right node value

Euler tour - walks around the entire tree, moving left, visiting each node twice (pre-traversal and post-traversal)

template method pattern - describes a generic computation method that can be specialized for certain steps or parts

ADTs and Interfaces

Tree navigation and node methods:

  • getRoot(p) - gets root node of tree containing p
  • getParent(p) - returns node that is parent of p
  • getChildren(p) - iterator over children of p
  • isRoot(p) - boolean, is p the root node
  • isLeaf(p) - boolean, is p a leaf node
  • numChildren(p) - int, number of children of p


Tree construction methods:

  • add root
  • add left/right/child
  • replace
  • delete
  • attach

Tree utility/general methods:

  • size
  • empty
  • clone
  • clear
  • equals

Binary tree methods:

  • left
  • right
  • sibling

Implementations

Tree Position/Node class:

  • parent
  • left/right/container for children
  • protected attributes - accessible to parent or exposed via get/set
  • get/set for element
  • get/set for parent
  • get/set for children

Tree class:

  • root
  • size
  • make position (protected)
  • validate (protected)

Strategy:

  • public methods call private recursive methods
  • insert/remove/contains have public/private versions
  • traversal methods all private

Algorithms for Operations

Algorithms for tree operations:

height(p) method:

  • if p is root:
    • return 0
  • else:
    • return 1+height(parent)

depth(p) method:

  • if p is leaf:
    • return 0
  • else:
    • return 1+max( depth(child1), depth(child2), ... )

clone method (public):

  • new tree
  • root = clone this root
  • return tree

clone method (private recursive):

  • if node null:
    • return null
  • else:
    • create new Node
    • set left to clone node left
    • set right to clone node element right
    • return new node

addRoot method:

  • deal with non empty case
  • root = new node
  • update

addLeft or addRight method:

  • deal with non-empty case
  • left = new node or right = new node

replace method:

  • node element =new element

attach(p,tree1,tree2) method:

  • deal with internal node case
  • set parent of tree 1 root node to p
  • set left child of p to tree 1 root
  • set parent of tree 2 root node to p
  • set right child of p to tree 2 root
  • tree1 root = null, size = 0
  • tree2 root = null, size = 0

delete method:

  • deal with 2 child case
  • get correct child
  • deal with root case
  • get cursed node's parent
  • update parent's left/right child to point to replacement
  • convention: node parent = node

preorder subtree traversal:

  • perform visit action for p
  • for each child of p:
    • preorder(c)

postorder subtree traversal:

  • for each child of p:
    • postorder(p)
  • perform visit action for p

inorder subtree traversal:

  • if p has left:
    • inorder(left)
  • perform visit action for p
  • if p has right:
    • inorder (right)

breadth-first traversal:

  • deal with empty case
  • create queue
  • while queue not empty:
    • pop node from queue
    • perform visit action on node
    • add children to queue

postfix expression tree builder:

  • create tree node stack (last pop will be root)
  • while next char in expression:
    • take next char
    • if numeric:
      • make new node
      • add to stack
    • if operator:
      • new node
      • left = pop
      • right = pop
      • add node to stack

infix expression tree builder:

  • create tree node stack
  • set start new expression is true
  • while next char in expression:
    • take next char
    • 4 cases: numeric, operator, (, or )
    • if numeric:
      • make new node
      • if start of new expression:
        • push node onto stack
        • start new expression is false
      • else if expression on stack:
        • if peek stack is operator and peek stack has 1 child,
          • add to right child of peek
        • else error
      • else error
    • if operator:
      • new node
      • set left to stack pop
      • stack push node
    • if (:
      • start new expression is true
    • if ):
      • if stack size > 1:
        • pop top
        • add to keep's right
  • when finished,
  • while stack size > 1:
    • pop top
    • seek peek right to top

Properties of Binary Trees

For a non-empty tree T with n nodes and the following characteristics:

  • n number of nodes
  • n_E number of external nodes
  • n_I number of internal nodes
  • h height of nodes

Then the following properties hold.

General Binary Tree Properties

General trees - height/number nodes


\log{(n+1)} - 1 \leq h \leq n-1


h+1 \leq n \leq 2^{h+1}-1

This is a natural maximum/minimum limit on the number of nodes that any given level can hold. The lower limit corresponds to the case of a binary tree that looks like a linked list, the upper limit corresponds to a full binary tree.

General trees - number of internal/external nodes

Limit on the number of external nodes:


1 \leq n_E \leq 2^h

Limit on the number of internal nodes:


h \leq n_E \leq 2^h - 1

Proper Binary Tree Properties

Recall from definitions above that proper binary tree is one in which each node has 0 or 2 children.

Proper trees - height/number nodes

The following properties relate the height of a complete/proper binary tree to the number of nodes.


\log{(n+1)} - 1 \leq h \leq \dfrac{n-1}{2}

and rearranging, we get:


2h + 1 \leq n \leq 2^{h+1} - 1

Proper trees - number of internal/external nodes

The property mentioned above is


n_E = n_I + 1


h+1 \leq n_E \leq 2^h


h \leq n_I \leq 2^h - 1

Complexity and Cost

Big-O Complexity of Lists


Linked Binary Tree

depth O(d)
height O(h) (O(n) worst case)
children O(c)
tree traversal, euler tour O(n)
add/replace/attach O(1) (given a position)
root/parent/child/sibling O(1) (given a position)
is root/is leaf O(1)
length O(1)
empty O(1)

OOP Principles

Delegating responsibility for tasks:

  • Many decisions to make about inheritance, protection, ownership of operations
  • Example: should the method for getting the left/right node be node.left? node.getLeft()? tree.left(node)?
  • When designing a data structure, have to think ahead to concrete implementations. What will you need to override, and what will stay the same?
  • Trees have a complicated potential inheritance diagram.
    • Different concrete implementations (linked vs array)
    • Different functionality (AVL vs BTree vs Red Back)
    • Further, internal classes and utilities might need to change (e.g., AVL trees keeping count)
    • Trees are used by other data structures (priority queue, set, sort, etc)
  • Nail down the scope before you start, to keep from (a) putting in way more work and formality than is required, or (b) putting together a slapdash design that has to be completely refactored
  • Seems better to build functionality into the tree - more self-contained - although if you can get away with node.left, why wouldn't you

Adaptability and reusability:

  • Hook methods - pseudo-virtual methods
  • Template method pattern
  • Generic types for node data
  • Generic types extend from nodes to trees

Flags