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