Friday, 24 November 2017

Binary Search Trees and AVL Trees in Data Structure

1. Binary search trees are an excellent data structure to implement associative arrays, maps, sets, and similar interfaces.
2. The main difficulty, as discussed in last lecture, is that they are efficient only when they are balanced.
3. Straightforward sequences of insertions can lead to highly unbalanced trees with poor asymptotic complexity and unacceptable practical efficiency.
4. The solution is to dynamically rebalance the search tree during insert or search operations.
5. We have to be careful not to destroy the ordering invariant of the tree while we rebalance.
6. Because of the importance of binary search trees, researchers have developed many different algorithms for keeping trees in balance, such as AVL trees, red/black trees, splay trees, or randomized binary search trees.
7. In this lecture we discuss AVL trees, which is a simple and efficient data structure to maintain balance.
8. It is named after its inventors, G.M. Adelson-Velskii and E.M. Landis, who described it in 1962.

Ordering Invariant.
1. At any node with key k in a binary search tree, all keys of the elements in the left subtree are strictly less than k, while all keys of the elements in the right subtree are strictly greater than k.
2. To describe AVL trees we need the concept of tree height, which we define as the maximal length of a path from the root to a leaf. So the empty tree has height 0, the tree with one node has height 1, a balanced tree with three nodes has height 2.
3. If we add one more node to this last tree is will have height 3. Alternatively, we can define it recursively by saying that the empty tree has height 0, and the height of any node is one greater than the maximal height of its two children.
3. AVL trees maintain a height invariant (At any node in the tree, the heights of the left and right sub-trees differs by at most.)

Mukesh Rajput
Sorting Algorithms:

Meaning of Sorting in data structure:
1. Sorting is the process of arranging items in a certain sequence or in different sets .
2. The main purpose of sorting information is to optimize it's usefulness for a specific tasks.
3. Sorting is one of the most extensively researched subject because of the need to speed up the operations on thousands or millions of records during a search operation.

Different types of Sorting algorithms:

Internal Sorting :
1. An internal sort is any data sorting process that takes place entirely within the main memory of a computer. 
2. This is possible whenever the data to be sorted is small enough to all be held in the main memory. 
3. For sorting larger data-sets, it may be necessary to hold only a chunk of data in memory at a time, since it won’t all fit. 
4. The rest of the data is normally held on some larger, but slower medium, like a hard-disk. 
5. Any reading or writing of data to and from this slower media can slow the sorting process considerably.

External Sorting: 
1. Many important sorting applications involve processing very large files, much too large to fit into the primary memory of any computer.
2. Methods appropriate for such applications are called external methods, since they involve a large amount of processing external to the central processing unit. 
3. There are two major factors which make external algorithms quite different: 
First, the cost of accessing an item is orders of magnitude greater than any bookkeeping or calculating costs.
Second, over and above with this higher cost, there are severe restrictions on access, depending on the external storage medium used: for example, items on a magnetic tape can be accessed only in a sequential manner.

Mukesh Rajput
Linked List: A Linear Data Structure

Linked List is a linear data structure in which every element is linked with each other in a sequential manner. Below are some properties of Linked list are given:
1. Linked List is a dynamic data structure.
2. Linked List is a linear collection of data items.
3. In Linear List direction of each element is associated with it.
4. In Linear List logical link exits between items and pointers acts as the logical link.
5. Linked List consists of nodes that has two fields. Data field : info of the element. Next field: next pointer containing the address of next node.

Different types of Linked List:
1. Singly or chain: Single link b/w items.
2. Doubly: There are two links, forward and backward link.
3. Circular: The last node is again linked to the first node. These can be singly circular & doubly circular list.

Different advantages of Linked List:
1. Linked list use dynamic memory allocation thus allocating memory when program is initialised. List can grow and shrink as needed. Arrays follow static memory allocation. Hence there is wastage of space when less elements are declared. There is possibility of overflow too bcoz of fixed amount of storage.
2. Nodes are stored incontiguously thus insertion and deletion operations are easily implemented.
3. Linear data structures like stack and queues are easily implemented using linked list.

Different dis-advantages of Linked List:
1. Wastage of memory as pointers requirextra storage.
2. Nodes are in-contiguously stored thereby increasing time required to access individual elements. To access nth item arrays need a single operation while linked list need to pass through (n-1) items.
3. Nodes must be read in order from beginning as they have inherent sequential access.
4. Reverse traversing is difficult especially in singly linked list. Memory is wasted for allocating space for back pointers in doubly linked list.

Mukesh Rajput
Deletion from a Binary Search Tree

1. Deletion of a leaf node is easy.  For example, if a leaf node is left child, we set the left child field of its parent to NULL and free the node.  

2. The deletion of a non-leaf node that has only a single child is also easy.  We erase the node and then place the single child in the place of the erased node.  

3. When we delete a non-leaf node with two children, we replace the node with either the largest element in its left sub-tree or the smallest elements in its right sub-tree.  Then we proceed by deleting this replacing element from the sub-tree from which it was taken.

Mukesh Rajput
Binary Search Tree : A Non-Linear Data Structure

Definition: A binary search tree is a binary tree.  It may be empty. If it is not empty, it satisfies the following properties:
1. Every element has a key, and no two elements have the same key, that is, the keys are unique.
2. The keys in a nonempty left sub-tree must be smaller than the key in the root of the sub-tree.
3. The keys in a nonempty right sub-tree must be larger than the key in the root of the sub-tree.
4. The left and right sub-trees are also binary search trees.

Function for Inserting new element into Binary Search Tree:
To insert a new element, key, we must first verify that the key is different from those of existing elements.  To do this we search the tree.  If the search is unsuccessful, then we insert the element at the point the search terminated.

Important Note: ** The function modified_search that is slightly modified version of function search.  This function searches the binary search tree *node for the key number(num).  If the tree is empty or if number(num) is present, it returns NULL.  Otherwise, it returns a pointer to the last node of the tree that was encountered during the search.  The new element is to be inserted as a child of this node.

void   insert_node ( tree_ptr   *node, int   num )
tree_ptr   ptr, temp = modified_search ( *node, num );  // **
if ( temp  ||  !( *node ) )
ptr = new node;
if ( ptr = = NULL)
cout << “The memory is full \n”;
exit ( 1 );
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
if ( *node )
if ( num < temp->data )
temp->left_child = ptr;
temp->right_child = ptr;
*node = ptr;

Mukesh Rajput