pertemuan ke 5, Binary Search Tree, 2101678775, Rafael Kevin Liman


Binary Search Tree

Binary Search Tree Operations
•        Binary Search Tree has the following basic operations:
–     find(x)             : find key x in the BST
–     insert(x)          : insert new key x into BST
–     remove(x)       : remove key x from BST

Operations: Search
Because all data in 2-3 tree are stored in sorted order, searching in 2-3 tree is easy. We can extend the search algorithm for binary search tree to obtain the search algorithm in 2-3 tree.
find(ptr, x)
            If ptr is NULL then not found
            If x = A then found
            If x < A then find(ptr->left, x)
            If ptr is 3-node
                        If x = B then found
                        If A < x and x < B then find(ptr->middle, x)
                        If B < x then find(ptr->right,x)

Operations: Insertion
Insert operation is to insert one or more data elements into an array. Based on the requirement, new element can be added at the beginning, end or any given index of array.
Here, we see a practical implementation of insertion operation, where we add data at the end of the array.
Algorithm:
Step 1: IF TREE = NULL, then 
                                    Allocate memory for TREE
                         SET TREE->DATA = VAL
                        SET TREE->LEFT = TREE ->RIGHT = NULL
            ELSE
                        IF VAL < TREE->DATA
                                                Insert(TREE->LEFT, VAL)
                        ELSE
                                                Insert(TREE->RIGHT, VAL)
                         [END OF IF]
            [END OF IF]
Step 2: End

or


Example

#include <stdio.h>
void main()
{
   int LA[] = {2,4,6,8,9};
   int item = 11, k = 3, n = 5;
   int i = 0, j = n;

   printf("The original array elements are:\n");

   for(i = 0; i<n; i++)
   {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   n = n + 1;

   while( j >= k)
   {
      LA[j+1] = LA[j];
      j = j - 1;
   }

   LA[k] = item;

   printf("The array elements after insertion:\n");

   for(i = 0; i<n; i++)
   {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}


Operations: Deletion
Example
Consider LA is a linear array with N elements and K is a positive integer such that K<=N.
#include <stdio.h>
void main()
{
   int LA[] = {2,4,6,8,9};
   int k = 3, n = 5;
   int i, j;

   printf("The original array elements are:n");

   for(i = 0; i<n; i++)
   {
      printf("LA[%d] = %d n", i, LA[i]);
   }

   j = k;

   while( j < n)
   {
      LA[j-1] = LA[j];
      j = j + 1;
   }

   n = n -1;

   printf("The array elements after deletion:n");

   for(i = 0; i<n; i++)
   {
      printf("LA[%d] = %d n", i, LA[i]);
   }
}

Komentar

Posting Komentar

Postingan populer dari blog ini

Pertemuan ke 2, Linked List Implementation I, 2101678775, Rafael Kevin Liman.

Linked List Implementation I Sub Topics Linked List: -         Single Linked List -         Polynomial Representation -         Circular Single Linked List -         Doubly Linked List Single Linked List: Insert To insert a new value, first we should dynamically allocate a new node and assign the value to it and then connect it with the existing linked list. Single Linked List: Delete To delete a value, first we should find the location of   n ode which store the value we want to delete, remove it, a nd connect the remaining linked list. Polynomial Representation •         Polynomial is given as 6x 3 + 9x 2 + 1 •         Every individual term in a polynomial consists of two parts, a coefficient and a power •     ...
Baca selengkapnya

Pertemuan 1 - 5, Rangkuman, Rafael Kevin Liman, 2101678775.

Nama: Rafael Kevin Liman NIM  : 201678775 Kelas Lab : LA04  -LEC Pertemuan ke 1 Introduction to Linked List Sub Topics Pointer, Array and Introduction to Data Structure ·         Array Review ·         Pointer Review ·         Types of Data Structures Abstract Data Type Array •         A collection of similar data elements •         These data elements have the same data type (homogenous) •         The elements of the array are stored in consecutive memory locations and are referenced by an index Array index starts from zero Array Declaration & Accessing Array •         One Dimensional Array Declaration: •         int arr[5]; ...
Baca selengkapnya

Pertemuan ke 4, 2-3 Tree and B Tree, 2101678775, Rafael Kevin Liman

2-3 Tree and B Tree Sub Topics 2-3 Tree and B Tree -         2-3 Tree Concept -         Properties -         2-3 Tree Operation: Search, Insertion and Deletion -         B - Tree Concept -         Properties -         B Tree Operation: Search, Insertion and Delet ion 2-3 Tree Concept •         2-3 Tree is a tree data structure where every node with children has either two children and one data or three children and two data. •         2-3 Tree is NOT a binary tree.   2-3 Tree Properties ·         Every internal node is a 2-node or a 3-node. ·         All leaves are at the same level. ·  ...
Baca selengkapnya