Splay tree is not perferctly balanced. Worst case time can be O(n) for one single operation. But average running time is O(n lg n)

# Data Structures and Algorithms

## Thursday, June 14, 2012

### Splay Trees

Splay tree is a balanced binary search tree.

Splay tree is not perferctly balanced. Worst case time can be O(n) for one single operation. But average running time is O(n lg n)

Splay tree is not perferctly balanced. Worst case time can be O(n) for one single operation. But average running time is O(n lg n)

### Graphs

A graph G is a set of vertices and a set of edges that connects the vertices together.

It is written as

###

[incomplete]

It is written as

G = (V, E)

### Undirected graphs

### Directed graphs

###

Weighted graph

### Graph Traversal

[incomplete]

### Disjoint Sets

Disjoint set is a mathematical term which represents sets among which no two set has any item common. So intersection od any two sets results to empty set.

Merges two sets into one set.

Given an item it returns the set identifier in which the item belongs.

[incomplete]

### Operations

#### Union

Merges two sets into one set.

#### Find

Given an item it returns the set identifier in which the item belongs.

### List based disjoint set

### Tree based disjoint set

#### Path compression

#### Union by size

### Implementing quick union using Array

[incomplete]

### Tree

A tree is a set of nodes and edges that connects the nodes. Between there could be exactly one path.

Leaf node

Siblings

Ancestors

Descendents

Length of path

Depth of node

Height of node

Height of tree

Subtree

###

[incomplete] Complete binary tree can not have a right child without a left child.

#### Rooted Tree

When a node is distingushed as root the thre is a rooted tree. In such a tree every node has a parent except the root node. From any node to the path of root parent is the first node in that path.#### Definations

Leaf node

Siblings

Ancestors

Descendents

Length of path

Depth of node

Height of node

Height of tree

Subtree

### Binary tree

### Tree traversal

#### Preorder traversal

#### Postorder traversal

#### Inorder traversal for binary tree

#### Level order traversal

### Expression tree

#### Prefix expression

#### Postfix expression

#### Infix expression

[incomplete] Complete binary tree can not have a right child without a left child.

## Wednesday, June 13, 2012

### Index

### Data Structures

ArrayLinked List

Stack

Queue

Double ended queue - Deque

Hash Tables

Tree

Binary Search Tree

Trie

Priority Queue / Binary Heap

Disjoint Sets

Splay Trees

B-Tree

Graphs

### Algorithms

#### Greedy algorithms

#### Divide and Conquer

#### String operations

Knuth-Morris-Pratt algorithm for string search#### Search

Linear searchBinary search

#### Sort

Insertion SortSelection Sort

Mergesort

Heapsort

Quicksort and Quick Select

Bucket sort

Counting sort

Radix sort

Sort stability

#### Graph algorithms

Minimum spanning tree -Kruskals algorithm

Sortest path-

Dijkstra's algorithm

Bellman Ford algorithm

Topological sorting

Gift wrapping algorithm (convex hull)

#### Computer Graphics

Bresenham's line drawing algorithmFlood fill algorithm

Ray traching algorithm

#### Encoding

Huffman coding#### Cryptography

RSA algorithm for public key encryption#### Game Tree Search

### Priority Queue and Binary Heap

### Priority Queue

Data structure with nodes and keys and data are associated with each node. Total order is defined for the keys.

Its is simple to identify or remove smallest key. But no other key can be identified or removes as easily.

Insertion is possible at any time.

Priority Queue can be represented using Binary Heap.

### Binary Heap

A complete binary tree- A tree in which every level is filled except bottom level which is filled in the left to right order.

No child of any node may have key less than its parents key.

Level order traversal gives a sorted list of keys.

#### Binary heap using Array

A binary heap can be maintained using an array. For any node X with an index i its children are at i*2 and i*2+1. Like for a node with index 3, its children nodes are at 6 nad 7.

### Binary heap time complexity

Average case | Worst case | |

Search | O(n) | O(n) |

Insert | O(lg n) | O(lg n) |

Delete | O(lg n) | O(lg n) |

### Operations

#### Get min

Just return the node's key at root.

#### Insert

Place the new key at the boottom of the tree- ie the after the last entry- set this as current node.

Now the entry needs to bubble up untill the heaporder property is satisfied-

Repeat untill no swap possible

If current node's key is less than its parents' key swap current node with parent.

#### Remove min

Remove the root entry and replace root with last item in the tree (array). Then while possible bubble down the entry by comparing and swaping with child that has smaller key than current nodes key untill no swap is possible.

### Bottom up heap construction

Insert all the items in the tree any order. That is we can keep the array of numbers as it is.Take the last internal node and bubble down to tree like removeMin() operation in the heap.

### Binary Search Tree

Binary search tree is a ordered dictionary in which keys for each node in the tree has total order. It is also called ordered or sorted binary tree.

We can find, insert, remove entries relatively fast. Quickly find node with minumum or maximum keys or keas near another key.

We can find words with close spelling without knowing exact spelling or can find something like smallest number that is greater than 100.

BST is used as data structures for sets, multisets, associated arrays etc.

For any node X, the tree the left subtree of X contains nodes with keys less than X's key and right subtree contains nodes with greater than X's key nad both subtree must be binary search trees themselves.

Any node may have data attached to it.

We can get all the keys in sorted order by doing inorder traversal of the tree.

Start from the root as current node

Untill the key is found or no more node to visit

If the current node's key is equal to K return the current node

If current node's key is smaller than K select right node as current node

If current node's key is greater than K select left node as current node

Return NULL

While searching for a key K we encounter both of these keys if K is not in the tree. We need to keep track of the keys. When we go right node we have key smaller than K. When we go left we have key greater than K. Last of these two is the smallest key >=K and largest key <=K.

Starting form root continously select left child as long as possible. Last node will be the node with smallest key of the tree.

####

Starting form root continously select right child as long as possible. Last node will be the node with largest key of the tree.

Let K be the key we want to insert.

Search the tree for key K untill it is found or we hit NULL node

If NULL replace the NULL node with K.

If K is found insert new node as left or right node with key K

Let K be the key of the node we want to delete.

Search for the node X with Key K.

(a)If not found return.

(b)If found and node has no child detach the key from its parent.

(c)If found and node has one child replace the node with its child node.

(d)If found and node has two children-

Find the node Y with smallest key in the RIGHT subtree of the node to delete

Y do not have any left subtree so it can be removed easily using (a) or (b)

Replace X with Y

We can find, insert, remove entries relatively fast. Quickly find node with minumum or maximum keys or keas near another key.

We can find words with close spelling without knowing exact spelling or can find something like smallest number that is greater than 100.

BST is used as data structures for sets, multisets, associated arrays etc.

### Binary search tree time complexity

Average | Worst case | |

Search | O(lg n) | O(n) |

Insert | O(lg n) | O(n) |

Delete | O(lg n) | O(n) |

### Binary Search Tree Invariant

For any node X, the tree the left subtree of X contains nodes with keys less than X's key and right subtree contains nodes with greater than X's key nad both subtree must be binary search trees themselves.

Any node may have data attached to it.

We can get all the keys in sorted order by doing inorder traversal of the tree.

### Operations

#### Find a node with key K

Start from the root as current node

Untill the key is found or no more node to visit

If the current node's key is equal to K return the current node

If current node's key is smaller than K select right node as current node

If current node's key is greater than K select left node as current node

Return NULL

#### Find smallest key >=K and largest key <=K

While searching for a key K we encounter both of these keys if K is not in the tree. We need to keep track of the keys. When we go right node we have key smaller than K. When we go left we have key greater than K. Last of these two is the smallest key >=K and largest key <=K.

#### Find a node with smallest key

Starting form root continously select left child as long as possible. Last node will be the node with smallest key of the tree.

####

Find a node with largest key

Starting form root continously select right child as long as possible. Last node will be the node with largest key of the tree.

#### Insert a node

Let K be the key we want to insert.

Search the tree for key K untill it is found or we hit NULL node

If NULL replace the NULL node with K.

If K is found insert new node as left or right node with key K

#### Delete a node

Let K be the key of the node we want to delete.

Search for the node X with Key K.

(a)If not found return.

(b)If found and node has no child detach the key from its parent.

(c)If found and node has one child replace the node with its child node.

(d)If found and node has two children-

Find the node Y with smallest key in the RIGHT subtree of the node to delete

Y do not have any left subtree so it can be removed easily using (a) or (b)

Replace X with Y

Subscribe to:
Posts (Atom)