Take-Away Notes for Module COMP2048.

(Positional) Lists, Iterators, (Binary) Trees

Proofread
Reviewed
Add Figures
Complete Sample Proofs

Note: Induction Proofs required! (Basis of Induction -> Inductive Step)

List & Positional List

Several abstract data types that represent a linear sequence of elements, but with more general support for adding or removing elements at arbitrary positions.

Static Array List

Description

Fixed-capacity Array where elements can be inserted and removed arbitrarily.

Elements have to be shifted to allocate memory space for the operated element, e.g. (a) shifting up for an insertion at index i; (b) shifting down for a removal at index i;

Array-based implementation of an array list that is storing n elements. — Array-based implementation of an array list that is storing `n` elements.

Note: The space used by the data structure is .

Evaluation

Method	Running Time
`size()`
`isEmpty()`
`get(i)`
`set(i, e)`
`add(i, e)`
`remove(i)`

Note: The space used by the data structure is .

Dynamic Array List

Description

When a call to add new element risks overflowing the current array A, perform the following steps(illustration only): 1. Crate new array B of larger capacity; 2. Store elements of A in B; 3. Reassign reference A to the new array B;

A illustration of "growing" a dynamic array

Strategy Comparison: Amortized Analysis

Shorthand notation:

The insertion of an element to be the last element in an array list as push() operation.

Proposition:

To compare the incremental strategy and the doubling strategy by analyzing the total time needed to perform a series of push() operation;

Assume to start with an empty list represented by a growable array of size 1;

Call amortized time of a push operation the average time taken by a push operation over the operation series, i.e. ;

Incremental Strategy Analysis

Given , thus, the amortized time of a push operation is .

Doubling Strategy Analysis

Given , thus, the amortized time of a push operation is .

Positional List

Description

To provide a general abstraction of a sequence of elements with the ability to identify the location of an element without using index.

Usually implemented with a doubly-linked list.

Note: A position acts as marker / token within the broader positional list, similar to the "me" reference below.

Position: - unaffected by changes elsewhere / of element referred; - becomes invalid iff an explicit is issued to delete it; - a position instance is a simple object, supporting only the method getElement() which returns the element stored at the position.

Iterator

An iterator is a software design pattern that abstracts the process of scanning through a sequence of elements, one at a time.

Note: iterator supports the "for-each loop" syntax:

1
2
3

for (E variable: collection) {
    loopBody;
}

is equivalent to:

Iterator<E> iter = collection.iterator();
while (iter.hasNext()) {
    E variable = iter.next();
    loopBody;
}

TBC: refer to the iterable interface for more details.

Tree & Binary Tree

Tree

Definition

A tree is an abstract data type that stores elements hierarchically: With the exception of the top element(root), each element in a tree has a parent element and zero or more child elements(for binary trees, at most 2 children).

A tree consists of nodes with a parent-child relation.

Formal Definition:

Recursive Definition

A tree is either empty
or Consists of a node , called the root of , and a (possibly empty) set of trees whose roots are the children of .

Tree Terminology

[Root]: node without parent
[Internal Node]: node with at least one child
[External Node]: node without children
[Ancestors of Node ]: , parent, grandparent, etc.
[Descendant of Node ]: , child, grandchild, etc,
[Siblings of Node ]: nodes of same parent
[Subtree]
[Depth]: Let be a position within tree ; The depth of is the number of ancestors of p other than p itself.
[Height]: Maximum of the depths of its positions.

Funfact: Trees has bee applied to file tree / arithmetic expression tree / decision trees.

Traversal Algorithms

Pre-Order Traversal

A node is visited before its descendants.

Algorithm preOrder(v)
  visit(v)
  for each child w of v
    preOrder(w)

In-Order Traversal: Binary Tree Traversal Algorithms

A node is visited after its left subtree and before its right subtree in a Binary Tree.

Algorithm inOrder(v)
  if left(v) != null
    inOrder(left(v))
  visit(v)
  if right(v) != null
    inOrder(right(v))

Post-Order Traversal

A node is visited after its descendants.

Algorithm postOrder(v)
  for each child w of v
    preOrder(w)
  visit(v)

Binary Tree

Definition

A binary tree is an ordered tree with the following properties: 1. Every node has at most two children 2. Each child node is labelled as being either a left child or a right child 3. A left child precedes a right child in the order of children of a node. (Left First)

Recursive Definition

A binary tree is either... - empty - or Consists of a node , called the root of , and two binary trees(possibly empty) and whose roots are the left child and right child of r respectively.

Proper Binary Tree

A binary tree is proper if every internal node has exactly 2 children.

Let denote the number of nodes, denote the height of a proper binary tree .

i.e,

Implementation: Concrete Data Structure -> Abstract Data Structure

Linked General Tree Structure

In General Trees, A node is represented by an object storing: - Element - (Reference to) Parent Node - Sequence of (Reference to) Parent Node

Linked Binary Tree Structure

In Binary Trees, A node is represented by an object storing: - Element - (Reference to) Parent Node - (Reference to) Left Child Node & Right Child Node

Array-Based Tree Structure: TBC for further confirmation about rank