# Linear Structures and Trees

• Efficiency of an algorithm
• Linear datastructures
• Trees

• Traversals
• Binary tree

## Efficiency of an algorithm

The efficiency of an algorithm can be specified with the big-oh notation:

• O(n) linear increase in processing time

• O(1) constant processing time

• O(2powerN) exponential increase in processing time

• O(logN)

## Linear datastructures

Linear datastructures are abstract data types allowing to add new data or remove existing data at every possible position in the structure. Linear data structures are defined by having exactly one predecessor and one successor. Examples of these are

• IndexList

• PositionList

• Sequence IndexList is a generalized array with an index to assess elements, PositionList a generalized linked list and a Sequence the combination of both.

### IndexList

An IndexList support following operations

E get(r) returns element from list with index r
E set(r,e) exchanges element at index r with e
E remove(r) returns element at index r and removes it from list
int size() returns amount of elements of list
boolean isEmpty() returns true if list is empty
ArrayList is an implementation of this ADT. It is implemented using an array. Disadvantage is that array size needs to be know at forehand. In case max size is reached, the whole array is copied to a new array which has the same size + 30%. This operation is very time consuming.

### PositionList

In a PositionList ADT, an element is mainly characterized by its predecessor and successor. It supports following operations:

PositionList interface
Position first() returns first value of PositionList
Position last() returns last value of PositionList
boolean isFirst(p) true if Position p is first
boolean isLast(p) true if Position p is last
Position before(p) returns position of PositionList preceding p
Position after(p) returns position of PositionList succeeding p
int size Amount of positions
boolean isEmpty true if PositionList is empty
Important note is that the position on a PositionList is similar to a node in a linked list. Specifically it is possible and common used to use the Node class to implement the position list. Important difference however is that the Position interface should only give access to the element it is associated with. As the setNext-implementation of Node also allows to change the order of the list (e.g. deletes all following nodes of at position x by adding a node y instead at position x) one should be careful using this implementation and only change other elements using the PositionList data type and not the instance of Position.

### Sequence

A sequence is combination of both ADT just mentioned. It gives access to elements of an list by Position or index. So, it extends both interfaces and also to convert position into rank and vice versa.

Position<E> atRank(r) Returns Position of element
int rankOf(p) Returns index number of element at Position p

### Iterators

A typical process on InexList, PositionList and Sequence is the ordered looping across all elements. An iterator is an ADT for particularly this purpose. All elements of a list are added to the iterator which is then used to loop over. It supports the two operations hasNext() and next(). The Java Iterator interface also knows a method for removing an element of the underlying collection. Alternatively one can also use the interface Enumeration. Classes implementing the interface `Iterable`, have implemented a method iterator() which returns a iterator object. Over such an object can be iterated using a foreach-statement.

## Trees

Trees are non-linear data structures. They are hierarchical ordered and have some methods with which the tree can be traversed. Terminology:

• Parent: node or junction

• Children: child node

• external node or leaf: node without children

• Root: top node

• ordered tree: linear order between children of each node. It does not mean that there is an order between all nodes of the tree

• Binary tree: tree with max 2 children per node

• depth: amount of parent of a node exclusive node itself

• height: maximum levels of children of node As a ADT the tree stores elements in positions. Other than PositionLists there is no next or previous but child and parent. A tree supports following operations

Tree interface
Position root returns the root
Position parent(v) returns parent of v
Iterator children returns iterator of children of v
boolean isInternal(v) true if v has children
boolean isExternal(v) true if v is leaf
boolean isRoot(v) true if v is root

### Traversals

There are several ways of traversing a tree: `Preorder` How it works: Parent is visited before children Application: Print content of document tree `Postorder` How it works: Childrens are visited first Application: calculate disk usage of a folder `Inorder` (only binary trees) How it works: Childrens of the left branch are visited first, then center then right branch Application: Print binary tree

### Binary tree

Special tree with max 2 children per node. It supports the operations leftChild(v), rightChild(v), and siblings(). A natural way of implementing a binary tree is to use nodes.

``````public class BTNode<E>{
private BTNode<E> parent;
private BTNode<E> left;
private BTNode<E> right;
private E element;
// getters and setters for all attributes
}
``````

The interface for the binary search tree looks like this:

``````public boolean contains(E e);