Computer Algorithms II Lecture Notes

20 November 2007 • Trees

Outline

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

Linked Lists

• 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?

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.

• A distinguished node is known as the root.

  

Node Relations

• Nodes exist in parent-child relations.

• A leaf node has no children.

  • The root is the only node with no parent.

• Children of the same parent are siblings.

• Each node in an n-ary tree can have at most n children.

Tree Properties

• Desirable tree 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.

Tree Data Structure

• A tree is another implementation of a dictionary.

• The usual operations.

• add() and remove() manipulation operations.

  • But add and remove where?

• The 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 Implementation

• The tree-node data structure is inaccessible outside the tree.

Dynamic Implementation

• A tree node is represented by a node structure.

  template <typename T>
  struct node
    T data
    node * left, * right
  

  • This is a binary-tree node.

• N-ary-tree nodes are represented similarly.

  template <typename T, unsigned S>
  struct node
    T data
    node * children[S]
  

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

• Binary tree data structures 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 memeber(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

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

Removing Nodes

• How do you remove the node?

  • No children? No problem.

  • What do we do with the children?

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? Sorting!

Binary Trees and Order

• Go back to the original list and assume it's in order.

  

• Now make a tree out of it.

  

Binary Search Trees

• A binary tree T obeys the binary search property if, for every node n in T,

  • every node in n's left subtree contains a value less than n.e and

  • every node in n's right subtree contains a value at at least n.e.

• A binary tree obeying the binary search property is a binary search tree.

Binary Search Tree Member

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

Binary Search Tree Add

• It's easiest to add new data as a leaf.

  node * add(T e, node * root)
    if root = nil
      root = new node(data, nil, nil)
    or e < root.data
      root.left = add(e, root.left)
    or
      root.right = add(e, root.right)
    return root
  

Removing Nodes

• Using data from a child may not work.

  

• The BST property requires the largest on the left or the smallest on the right.

Binary Search Tree Remove

node * remove(node * r)

  if r.left ≠ nil
    r.left = remove_max(r.left, r.data)

  or r.right ≠ nil
    r.right = remove_min(r.right, r.data)

  or
    delete r
    r = nil

  return r

Performance

• Has worst-case performance improved for operations on binary search trees?

• Sadly, no: they are still O(n).

  • The binary search property is only part of the machinery needed to insure O(log n) behavior.

  • More to come...

Summary

• Trees generalize linked lists to provide uniform, efficient access to all elements.

  • With a little work.

• Binary search trees generalize sorted linked lists.

• But why aren't trees faster than lists?

  • Lists have the same performance at lower implementation costs.

References

• shadows and tall trees by gin_able, used under the AT-NC CC license.