UNIT – V

Unit-V/Lecture-01

Binary search trees

Trees:

 A tree is a Non-Linear Data Structure which consists of set of nodes called vertices and set of edges which links vertices.

·         A tree is a data structure that is made of nodes and pointers, much like a linked list. The difference between them lies in how they are organized:

­   In a linked list each node is connected to one “successor” node (via next pointer), that is, it is linear.

­   In a tree, the nodes can have several next pointers and thus are not linear.

·         The top node in the tree is called the root and all other nodes branch off from this one.

·         Every node in the tree can have some number of children. Each child node can in turn be the parent node to its children and so on.

Basic Terminology:

• Root Node: The starting node of a tree is called  Root node of that tree
• Terminal Nodes: The node which has no children is said to be terminal node or leaf
• Nodes.
• Non-Terminal Node: The nodes which have children is said to be Non-Terminal Nodes
• Degree: The degree of a node is number of sub trees of that node
• Depth: The length of largest path from root to terminals is said to be depth or height of the tree
• Siblings: The children of same parent are said to be siblings
• Ancestors: The ancestors  of a node are all the nodes along the path from the root to the node

Property           Value Number of nodes :  9 Height            :  4 Root Node         :  A Leaves            :  D, H,I,F, C Interior nodes    :  B.E, F,G    Number of levels  :  5 Ancestors of  H   :  I Descendants of  B :  D,E, F Siblings of  E    :  D, F

A

C

D

G

E

F

I

H

Binary Tree:

Binary trees are special class of trees in which max degree for each node is 2

Recursive definition:

A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

Any tree can be transformed into binary tree. By left child-right sibling representation.

A

B

DDDDC

H

C E

FFF

G

E

·         A common example of a tree structure is the binary tree.

Examples:

root

root

·         The following are NOT binary trees:

Property of Binary Tree:

·         If n1 is the root of a binary tree and n2 is the root of its left or right tree, then n1 is the parent of n2 and n2 is the left or right child of n1.

·         A node that has no children is called a leaf.

·         The nodes are siblings if they are left and right children of the same parent.

·         The level of a node in a binary tree:

­   The root of the tree has level 0

­   The level of any other node in the tree is one more than the level of its parent.

root

Level 0

Level 1

Level 2

Level 3

Binary search trees:

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

Insertion and Deletion

In a binary search tree to determine the conditions that can cause an unbalanced tree. To insert an 18 in the tree in Figure 5.1, we first search for that number. This causes us to arrive at node 16 with nowhere to go. Since 18 > 16, we simply add node 18 to the right child of node 16

                      Figure-5.1 : Binary Tree After Adding Node 18

Deletions are similar, but require that the binary search tree property be maintained.

For example, if node 20 in figure 5.1 is removed, it must be replaced by node 37. This results in the tree shown in Figure 5.2. The rationale for this choice is as follows. The successor for node 20 must be chosen such that all nodes to the right are larger. Therefore we need to select the smallest valued node to the right of node 20. To make the selection, chain once to the right (node 38), and then chain to the left until the last node is found (node 37). This is the successor for node 20.

                                                Figure 5.2: Binary Tree After Deleting Node 20

Searching a binary search tree:

Starting at the root node, the search algorithm compares the search key with the data stored in the current node.

(a)  If the search key is equal to the data of the current node, the value has been found, and the search is terminated.

(b)  If the search key is greater than the data of the current node, the search proceeds with the right child as the new current node.

(c)  If the search key is less than the data of the current node, the search proceeds with the left child as the new current node.

(d)  If the current node is null, the search is terminated as unsuccessful.

Unit-V/Lecture-02

Height balanced tree

Balanced Tree:

A balanced tree is a rooted tree where each subtree of the root has equal number of nodes.

Types of balanced tree:

1. Height balance tree or AVL Tree
2. Splay tree
3. Red –Black tree
4. B-trees

Height  Balance Tree:

                                An empty tree is height balanced tree if T is a non-empty binary tree with TL and TR as its left and right subtrees.

The T is height balanced iff

1. T_L and T_R are height balanced.
2. h_L – h_R <=1 where h_L and h_R  are heights of T_L and T_R

Balance Factor:

                                The balance factor of a node in a binary tree is defined to h_L – h_R <=1 where h_L and h_R  are heights of T_L and T_R.

Representation of AVL Tree:

1. It follows the property of BST. AVL tree is BST with balance factor -1,0,1.
2. After insertion of any node in an AVL tree if the balance factor of any node becomes other than -1,0,1 then it is that AVL property is violated. Then we have to restore the destroyed balance condition.
3. After an insertion of a new node if balance condition gets destroyed, then the nodes on that path(to root) needs to be readjusted(means affected subtree is to be rebalanced).
4. Rebalancing should be such that entire tree should satisfy AVL property.

Example-1

Now insert 13-

Balance condition is violated.

When we insert the element in the tree then for rebalancing there are four types of rotations.

1. Insertion of new node into left subtree of left child(LL).
2. Insertion of new node into right subtree of left child(LR).
3. Insertion of new node into left subtree of right child(RL).
4. Insertion of new node into right subtree of right child(RR).

Unit-V/Lecture-03

B-Tree & 2-3 Trees

B-Tree-

B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations (search, insert, delete, max, min, etc) require O(h) disk accesses where h is height of the tree. Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Generally, a B-Tree node size is kept equal to the disk block size. Since h is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to balanced Binary Search Trees like AVL Tree, Red Black Tree,etc.

Properties of B-Tree
1) All leaves are at same level.
2) A B-Tree is defined by the term minimum degree‘t’. The value of t depends upon disk block size.
3) Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
4) All nodes (including root) may contain at most 2t – 1 keys.
5) Number of children of a node is equal to the number of keys in it plus 1.
6) All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in range from k1 and k2.
7) B-Tree grows and shrinks from root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.
8) Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(Logn).

Following is an example of B-Tree of minimum degree 3. Note that in practical B-Trees, the value of minimum degree is much more than 3.

Search
Search is similar to search in Binary Search Tree. Let the key to be searched be k. We start from root and recursively traverse down. For every visited non-leaf node, if the node has key, we simply return the node. Otherwise we recur down to the appropriate child (The child which is just before the first greater key) of the node. If we reach a leaf node and don’t find k in the leaf node, we return NULL.

Traverse
Traversal is also similar to Inorder traversal of Binary Tree. We start from the leftmost child, recursively print the leftmost child, then repeat the same process for remaining children and keys. In the end, recursively print the rightmost child.

Example-1 Construct B-Tree tree of minimum degree 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-Tree.

Solution-

Initially root is NULL. Let us first insert 10.

Let us now insert 20, 30, 40 and 50. They all will be inserted in root because maximum number of keys a node can accommodate is 2*t – 1 which is 5.

Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted into the appropriate child.

.

Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without any split.

Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.

2-3   Trees- A B-tree of order 3 is known as a 2-3 tree. A 2-3 tree is a type of data structure, where every node with children(internal node) has either two children and one data element(two nodes) or three children and two data elements(3-nodes).

Nodes on the outside of the tree (leaf node) have no children and 2-data elements.

Properties:-

1. Every non-leaf node has 2 or 3 children.

2. All leaves are at the same level.

3. All data is kept in sorted order.

4. Every non leaf node will contain 1 or 2 fields.

Example- 34,68,1,2,88,56,56,94

If we insert 34 into an empty tree, we get a tree with a leaf root.

Now insert 68.

A leaf can have only one data value, so we split and make a new root:

Now insert 1.

There's room in the parent for another child, so this is an easy case:

Next insert 2.

There's no room in the parent for another child, so we have to split and create a new root:

Next insert 88.

There's room in the parent for another child, so we have an easy case:

Next insert 56.

There's no room in the parent for another child, so we have to split the parent:

Next insert 56.

There's no room in the parent for another child, so we have to split the parent. Fortunately, there's room in the grandparent for the new parent:

Next insert 94.

There's room in the parent for another child, so -

Unit-V/Lecture-04

Basic search and traversal techniques for trees

Tree Traversal vs Search Techniques -

Traversal of a binary tree involves examining every node in the tree.

Search involves visiting nodes in a graph in a systematic manner, and may or may not result into a visit to all nodes. Different nodes of a graph may be visited , possibly more than once, during traversal or search. If search results into a visit to all the vertices, it is called traversal

Tree Traversal Technique-

There are three standard ways of traversing a binary tree T with root R.

Three recursive traversal techniques are widely used:

1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal

Preorder

–      Process the root R.

–      Traverse the left subtree of R in preorder.

–      Traverse the right subtree of R in preorder.

Inorder

–      Traverse the left subtree of R in inorder.

–      Process the root R.

–      Traverse the right subtree of R in inorder.

Postorder

–      Traverse the left subtree of R in postorder.

–      Traverse the right subtree of R in postorder.

–      Process the root R.

Tree Searching Techniques-

A tree search starts at the root and explores nodes from there, looking for a goal node (a node that satisfies certain conditions, depending on the problem).

1.       Depth-first searching

n  A depth-first search (DFS) explores a path all the way to a leaf before backtracking and exploring another path

n  For example, after searching A, then B, then D, the search backtracks and tries another path from B

n  Node are explored in the order A B D E H L M N I O P C F G J K Q

n  N will be found before J

2.       Breadth-first searching

n  A breadth-first search (BFS) explores nodes nearest the root before exploring nodes further away

n  For example, after searching A, then B, then C, the search proceeds with D, E, F, G

n  Node are explored in the order A B C D E F G H I J K L M N O P Q

n  J will be found before N

Depth- vs. breadth-first searching-

n  When a breadth-first search succeeds, it finds a minimum-depth (nearest the root) goal node

n  When a depth-first search succeeds, the found goal node is not necessarily minimum depth

n  For a large tree, breadth-first search memory requirements may be excessive

n  For a large tree, a depth-first search may take an excessively long time to find even a very nearby goal node

Unit-V/Lecture-05

Basic search and traversal techniques for graphs

Definition-

A graph G=(V, E) consists of a set of vertices V, and a set of edges E, such that each edge in E is a connection between a pair of vertices in V.

The number of vertices is written as |V|, and the number of edges is written as |E|.

Search and traversal techniques for graphs:

Fundamental problem concerning the graph is the path problem. In its simplest form, it requires us to determine whether or not there exist a path in a given graph G = (V, E) such that the path starts at vertex v and ends at vertex u.

More general form would be to determine for a given starting vertex all vertices u such that there is a path from v to u.

Breadth First Search (BFS)

In BFS we start at vertex v and make it as having been reached (visited). The vertex v will at this time should be unexplored. A vertex will be said to have been explored by an algorithm

when the algorithm has visited all the vertices adjacent from it. All the unvisited vertices adjacent from v are visited next.

Breadth–first search tries to stay as close as possible to the starting point. It first visits the

vertices adjacent to the starting vertex, and only then it goes farther away.It uses a queue to store nodes.

Given any source vertex s, BFS visits the other vertices at increasing distances away from s. In doing so, BFS discovers paths from s to other vertices

BFS Algorithm

Example-

Solution-

Depth-first search-

DFS is another popular graph search strategy. Idea is similar to pre-order traversal (visit children first).

DFS can provide certain information about the graph that BFS cannot. It can tell whether we have encountered a cycle or not. DFS will continue to visit neighbors in a recursive pattern. Whenever we visit v from u, we recursively visit all unvisited neighbors of v. Then we backtrack (return) to u.

DFS Algorithm

Unit-V/Lecture-06

NP-completeness

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to "nondeterministic polynomial time.

A Polynomial Time Algorithm is an algorithm with a Time Complexity that progress slow according to a huge input size.

A Non-Polynomial Time Algorithm is an algorithm with a Time Complexity that progress fast, Polynomial Time Complexity examples: 

O(c), O(logN), O(N).

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the  Hamiltonian path problem and the vertex cover problem.

Since deterministic Turing machines are special nondeterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.  

NP-Completeness-

There are two groups in which a problem can be classified.

Ø   The first group consists of the problems that can be solved in polynomial time.

For example: searching of an element from the list O( log n) , sorting of elements O( log n).

Ø   The second group consists of problems that can be solved in non-detreministic polynomial time.

For example: Knapsack problem O(2^n/2) and traveling salesperson problem O( n²2ⁿ).

Any problem for which answer is either yes or no is called decision problem.

The algorithm for decision problem is called Decision Algorithm.

Any problem that involves the identification of optimal cost (minimum or maximum) is called optimization problem.

The algorithm for optimization problem is called optimization algorithm.

Definition of P-

Problems that can be solved in polynomial time. (“P stands for polynomial ”).

Example: searching of an element from the list , sorting of elements , All pair shortest path.

Definition of NP-

It stands for “non-deterministic polynomial time”. NP does not stand for “non-polynomial”.

Example: Traveling salesperson problem ,Graph coloring problem , Knapsack, Hamiltonian circuit problem.

The NP class problems can be further categorized into NP-complete and NP-hard problems.

A problem D is called NP – complete if-

(1)   It belongs to class NP

(2)   Every problem in NP can also be solved in polynomial time.

Ø  If an NP-hard problem can be solved in polynomial time then all NP-complete problems can also be solved in polynomial time.

Ø  All NP-complete problems are NP-hard problems but all NP-hard problems can not be NP-complete.

Ø  The NP class problems are the decision problems that can be solved by non-deterministic polynomial algorithm.

Example of P class problem-

Kruskal’s Algorithm:- In kruskal’s algorithm the minimum weight is obtained. In this algorithm also the circuit should not be formed. Each time the edge of minimum weight has to be selected, from the graph. It is not necessary in this algorithm to have edges of minimum weights to be adjacent.

Example of NP class problem-

Travelling Salesman problem:- This problem can be stated as “ Given a set of cities and cost to be travel between each pair of cities, determine whether there is a path that visits every city once and returns to the first city. Such that the cost travelled is less”.

Note:- This problem is NP problem as there may exist some path with shortest distance between the cities. If you get the solution by applying certain algorithm then Travelling Salesman Problem is NP Complete problem. If we get no solution at all by applying an algorithm then the travelling Salesman problem belongs to NP hard class.