Advanced Programming I Lecture Notes

2 March 2006 • Trees

Outline

Motivation
List properties.
The list ADT.
ADT 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.
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.

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.

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

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

binary tree insertion

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

binary tree add

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

Removing Nodes

binary tree delete

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

searching bst

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...

Array-Based Trees

The array-based implementation of trees is not easily dynamic.
It is, however, the bases for a number of useful data structures and algorithms.
- It's also a cheap way to implement binary trees in some cases.
- In particular, when the number of elements is bounded.

Binary Tree Indexing

binary tree indexing

If a binary-tree node is stored at index i, its
- left child is stored at index 2i + 1 and
- its right child is stored at index 2(i + 1) and
The root of the binary tree is stored at index 0.

Heaps

A heap is a binary tree T with the property that
the value stored at any node n in T is not less (or greater) than the values stored at n's children.
- This is the heap property.

Heap Characteristics

Heaps and binary search trees are incomparable.
The heap property can be maintained with O(log n) work per element.
Maintaining the heap property is easier than is maintaining the binary search tree property.
- A single pass up or down the heap is enough.

Priority Queues

A regular queue stores elements in FIFO order.
Assign each queue element a priority that can be ordered.
A priority queue stores elements in increasing (min queue) or decreasing (max queue) order.
- No more FIFO ordering.
- Sometimes no more end-restricted access either (canceling queued entries).

Heaps as Priority Queues

An array-based heap provides an efficient implementation of a priority queue.
New entries are enqueued at the last element and bubbled up to maintain the heap property.
The head is dequeued by replacing it with the last element and bubbling it down to its proper location.
Heaps provide O(log n) behavior.
- Vs. O(n) for a non-heap implementation.

Example Enqueue

example priority queue enqueue