Posts tagged "abstract data structure"

Trees - Part I

tre

render(鈥/image.*鈥, caption: 鈥楤right green tree - Waikat鈥, src: 鈥//upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Bright_green_tree_-Waikato.jpg/512px-Bright_green_tree-Waikato.jpg)](http://commons.wikimedia.org/wiki/File%3ABright_green_tree-_Waikato.jpg)

We used trees to build the heap data structure before, but we didn鈥檛 bother with the theory behind trees, which are abstract and concrete data structures themselves. There鈥檚 a huge range of material to cover so I鈥檒l split this in several posts.

In this first post we鈥檒l cover the basic theory and implement a binary search tree (BST), which provides O(h) time search, insert and delete operations (h is the tree height). First, the basics:

Trees are graphs with a few extra properties and interpretations/conventions. * Trees have height (longest branch length) and depth (distance to root). * The uppermost level consists of at most one node (the tree root). * All nodes may have children. * There are no edges other than parent-child edges.

Trees are classified according to some of those properties above and some others we鈥檒l mention later. Most commonly, there is a constraint to the maximum number of children per node -e.g. the binary tree limits children to 2 per node.

Heap & Priority Queues

Priority queues (PQs) are abstract data types that work just like regular stacks, but the popping order depends on each element鈥檚 priority instead of the sequence they were pushed onto the queue (FIFO or LIFO).

The na茂ve way of implementing a PQ consists of using an unsorted list or array and searching for the highest-priority element at each pop, which takes O(n) time. There are several more efficient implementations, of which the most usual is the heap.

Heaps are complete (i.e. all levels except possibly the last are filled) binary trees that work as PQs by maintaining the following property: children nodes always have a smaller priority than their parent, i.e. for any node A with children B and C, priority(B) < priority(A) && priority(C) < priority(A). Note that there is no assumed relation between siblings or cousins.

max-heap and corresponding array.

Each element of a heap has two pieces of information: a key and a value, hence we call them key-value (KV) pair. The key identifies the specific element, and the value determines the element鈥檚 priority within the heap. Heaps can be min-heaps (low value = high priority) or max-heaps (high value = high priority).

Stack

Using our implementation of a doubly linked (DL) list, we can very simply build the most basic LIFO (last in, first out) data structure: the stack.

stac

Stacks have two basic operations: push and pop. Push pushes data onto the stack (i.e., end of the DL list) and pop pops data off the list鈥檚 tail, which is only possible because we can set the new tail as tail->prev, since we鈥檙e using a DL list, with previous pointers. Another useful function is peek, which returns a pointer to the stack鈥檚 top.