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 Deletion

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.

·        All data is kept in sorted order.

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.

Example

Let LA is a Linear Array (unordered) 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 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

Deletion refers to removing an existing element from the array and re-organizing all elements of an array.

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]);

   }

}