Question

Exercise 3: Multi-way Trees

A way to reduce the height of tree and ensure balance is to allow multiple children of nodes. In your class you learned 2-3 trees which allows up to 2 keys in a node, and the number of children is equal to the number of keys + 1. B-trees extend this concept to any arbitrary number of keys (usually number of keys is even and number of children (equal to number of keys+1) is odd).

Assume we want to design a 5-way B-Tree. This will mean that there can be maximum 4 keys in a node, and if the number of keys becomes 5, we can split it into two (the same way we split 2-3 tree when number of keys becomes 3).

Design a 5-way B-tree. Starting with an empty tree, insert the following keys in order.
2, 3, 5, 7, 10, 50, 22, 44, 45, 55, 66, 68, 70, 17, 6, 21, 67

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Exercise 1: Pre-sorting

Consider the problem of finding the distance between the two closest numbers in an array of n numbers. (The distance between two numbers x and y is computed as |x − y|.)

a. Design a presorting-based algorithm and implement it in your preferred language.

b. Solve the above problem using brute-force approach. Implement in your preferred language.

c. Compare the efficiency of the above two algorithms.

Answer 1

1)  For B tree we just have to insert keys and when children become N we split it into two halves.

End result:

Procees:

2)  

a) Just sort the array using in log(n) time with mergesort or inbuild function.

#include<bits/stdc++.h>
#include<numeric>
using namespace std;
void merge(int *v,int s,int e)
{
    int a[100];
    int mid=(s+e)/2;
    int j=s,k=s,i=mid+1;
    while(j<=mid && i<=e)
    {
        if(v[i]<v[j])
        {
            //ans.push_back(v[i]);
            a[k++]=v[i++];
            //i++;
        }
        else
        {
            a[k++]=v[j++];
            //j++;
        }
    }
    while(i<=e)
    {
        a[k++]=v[i++];
        //i++;
    }
    while(j<=mid)
    {
        a[k++]=v[j++];
        //j++;
    }
    for(int i=s;i<=e;i++)
    {
        v[i]=a[i];
    }
}
void mergesort(int v[],int s,int e)
{
    if(s>=e)return;
    int mid=(s+e)/2;
    mergesort(v,s,mid);
    mergesort(v,mid+1,e);
    merge(v,s,e);
}
int main()
{
        int n;
        cin>>n;
        int v[n];
        for(int i=0;i<n;i++)
        {
                cin>>v[i];        // taking array as input
        }
        mergesort(v,0,n-1); // sorting array
        int mn=INT_MAX; //declaring a variable mn which will be our answer INT_MAX max possible value.
        for(int i=1;i<n;i++)
        {
                mn=min(v[i]-v[i-1],mn); // comparing new value with minimum value till this point.
        }
        cout<<mn<<endl; // answer
        return 0;
}

n log(n) + n = n log(n)

this takes n log(n) time.

b)

In this, we iterate over an array in a nested loop to find the distance

#include<bits/stdc++.h>
#include<numeric>
using namespace std;
int main()
{
        int n;
        cin>>n;
        int v[n];
        for(int i=0;i<n;i++)
        {
                cin>>v[i];        
        }
        int mn=INT_MAX;
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<n;j++)
                {
                        mn=min(mn,abs(v[i]-v[j]));
                }
        }
        cout<<mn<<endl;
        return 0;
}

This is  .

C) algorithm in A takes time and algorithm in B take time.

Please Upvote.

if you face any problem comment below.