Data Structures & Algorithms Lecture Notes

25 November 2008 • Trees

Outline

Motivation
Tree properties.
The tree 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.

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.
This form of tree ADT are more commonly called a dictionary.

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

simple data for a tree

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

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

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?

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.

This page last modified on 25 November 2008.