Data Structures & Algorithms Lecture Notes

10 November 2010 • Trees

---

Outline

Motivation Tree properties. Tree data structures. Tree implementations. Extension and details.

Linked Lists Again

• List element access is non-uniform.
  • It’s quicker to access end elements than it is middle elements.
• Stacks and queues (and friends) come from embracing and exploiting this disparity.
• How can this disparity be reduced? What’s the result?
  • Eliminating the disparity comes later in the semester.

Fast Interior Access

• What’s the quickest way to the middle list element?
  • Have a reference to it.

    

• What about the other elements?
  • Have references to them.

    

• And so on.

Fast-Access Structure

• To gain advantage, the references have to be layered.

  Each layer reference points to half of the next layer.

• Assuming accurate halving, any one of n elements can be uniformly accessed in O(log n) time.
  • That assumption’s going to be a problem.

Trees

• The divided-list data structure is known as a tree.
• A tree is a set of zero or more nodes or vertices.
• Nodes are linked by edges or arcs, sometimes arrows, sometimes lines.
• A distinguished node is known as the root.

  

Node Relations

Nodes exist in parent-child relations. Children of the same parent are siblings.

• A leaf node has no children.
  • The root is the only node with no parent.
• Each node in an n-ary tree can have at most n children.
  • A binary (2-ary) tree.

Tree Properties

• Desirable ADT properties include:
  • Hold arbitrarily many elements.
  • Add and remove elements at will.
  • Efficiently traverse elements.
    • “Efficiently” means sub-linearly to improve on linked lists.
    • This applies to query and navigation operations.

The Tree ADT

• The usual maintenance operations.
• add() and remove() manipulation operations.
  • But add and remove where?
• The usual query operators: size(), empty(), find(), …
  • Navigation operators are going to be tricky.

Implementing Trees

• Trees can be implemented either statically or dynamically.
  • Static implementations involve arrays.
  • Dynamic implementations involve dynamic storage.
• Static array implementations are useful and common.

Tree ADT Data

	The tree-node ADT is inaccessible outside the tree ADT.

Dynamic Implementation

• A tree node is represented by a node structure.

  class BinaryTree<E> {
    private class Node {
      E value;
      Node left, right;
      }
    }

• N-ary-tree nodes are represented similarly.

  private class Node {
    E value;
    Node children[N];
    }

Trees And Recursion

• Trees are a non-trivial recursive data structure.
• A binary tree is either
  • empty,
  • or a node (the root) and two trees called left and right (the children).
    • Each child is also known as a subtree.
• The recursive definition of n-ary trees is similar.

Binary Tree Operations

• As part of an ADT, binary trees should support the usual operations.
  • In particular add(), remove() and member().
• The expected performance of these operations should be O(log n).

Binary-Tree Search

bool member(T e, node root)
  if root = nil, return false
  if root.data = e, return true
  if member(e, root.left), return true
  return member(e, root.right)

Binary-Tree Add

• The old tree can become either child.

  node add(T e, node root)
    return new node(e, nil, root)
  

Removing Nodes

• How do you remove the node?
  • No children? No problem.
  • What do we do with the children?

Removing Leaves

• Null out the parent's pointer to n.

  n.parent.left = null;
  

  • Keeping in mind that n could be the root.

Removing Almost Leaves

• Copy a child's value to the parent.
• Null out the parent's pointer to the copied child.

Removing Any Node

• Find a leaf node and hoist its value up to the deleted node.
  • Null out the parent's pointer to the hoisted leaf node.

Binary-Tree Remove

node remove(node root)
  if root.left ≠ nil
    root.data = root.left.data
    root.left = delete(root.left)

  or root.right ≠ nil
    root.data = root.right.data
    root.right = delete(root.right)

  or
    root = nil

  return root

Operation Performance

• Search has O(n) behavior.
• Add has O(1) behavior.
• Remove has O(n) behavior.
• This is not what we paid for.
• There’s not enough information in the tree to move through it intelligently.
• How to add more information?

Tree Traversals

• A tree traversal is an organized tour through a tree’s nodes.
  • Each node is processed once, but possibly traversed many times.
• Example: binary tree search.

  

Traversal Actions

• Each step in a tree traversal performs one of three steps:
  1. Process node data (N).
  2. Traverse the left child (L).
  3. Traverse the right child (R).
• There are six different sequences of three actions.
  • NLR, NRL, LNR, LRN, RLN, and RNL.

Traversal Types

• Three common traversal types are
  1. Inorder traversal (LNR).
  2. Pre-order traversal (NLR).
  3. Post-order traversal (LRN).
• The order refers to when the root node is processed.
• The children are traversed in left-right order.
  • Don’t forget the other variations.

Traversal Example

• The binary tree search can be implemented with inorder, pre-order, or post-order traversals.

  

  • Although using a pre-order traversal makes the most sense.

Implementing Traversals

• Traversals are easily implemented using the recursive definition of trees.

  pre-order-traversal(node root)
    if root ≠ nil
      process(root)
      pre-order-traversal(root.left)
      pre-order-traversal(root.right)
  
  in-order-traversal(node root)
    if root ≠ nil
      in-order-traversal(root.left)
      process(root)
      in-order-traversal(root.right)
  
  prost-order-traversal(node root)
    if root ≠ nil
      post-order-traversal(root.left)
      post-order-traversal(root.right)
      process(root)

Summary

• Trees generalize linked lists to provide uniform, efficient access to all elements.
  • With a little work.
• But why aren’t trees faster than lists?
  • Lists have the same performance at lower implementation costs.
• The three common tree traversals are inorder, pre-order, and post-order.

References

• Trees, Chapter 18, in Data Structures & Problem Solving Using Java, fourth ed, by Mark Weiss from Addison Wesley, 2010.
• Trees, Chapter 9, in Java Software Structures, third ed, by Lewis Chase from Addison Wesley, 2010.
• Trees, Chapter 7, in Data Structures & Algorithms in Java, fifth ed, by Michael Goodrich and Roberto Tamassia from Wiley, 2010.

Credits

• shadows and tall trees by gin_able under a Creative Commons AT NC license.

---

This page last modified on 25 March 2010.