- Efficiency of an algorithm
- Linear datastructures
-
- Traversals
-
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
-
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 add(r,e) adds new element e to list at index r 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 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 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 treePostorder
How it works: Childrens are visited first Application: calculate disk usage of a folderInorder
(only binary trees) How it works: Childrens of the left branch are visited first, then center then right branch Application: Print binary treeBinary 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); public void add(E e); public ArrayList<E> getElementsInOrder(); public boolean isEmpty(); public int getSize();
Because we want to order elements we also need to implement the ‘compareTo(E e)’ method of the interface Comparable