Рубрики

Создайте два BST из данного массива так, чтобы максимальная высота среди них была минимальной

Бинарное дерево поиска, Массивы, Структуры данных

Для заданного массива из n целых чисел задача состоит в том, чтобы создать два дерева двоичного поиска из заданного массива (в любом порядке) таким образом, чтобы максимальная высота среди двух деревьев была минимально возможной, и вывести максимальную высоту.

Примеры:

Input: arr[] = {1, 2, 3, 4, 6}
Output: 1

Input: arr[] = { 74, 25, 23, 1, 65, 2, 8, 99 }
Output: 2

Подход: цель состоит в том, чтобы минимизировать высоту дерева бинарного поиска максимальной высоты, и для этого нам нужно равномерно разделить элементы массива между обоими деревьями. И поскольку порядок не имеет значения, мы можем легко выбрать любой элемент для первого или второго двоичного дерева. Теперь, чтобы минимизировать высоту двух деревьев, деревья должны быть почти завершены и иметь как можно более равную высоту. И максимальная (минимизированная) высота будет log (n / 2) или log (n / 2 + 1).

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для расчета журнала ()

int cal_log(int n)

{

    int ans = 0;

  

    while (n) {

        n /= 2;

        ans++;

    }

  

    return ans;

}

  
// Функция для возврата максимума
// высота дерева

int maximumHeight(int n, int arr[])

{

    int level = cal_log(n / 2 + n % 2);

    return (level - 1);

}

  
// Управляемый код

int main()

{

    int arr[] = { 1, 2, 3, 4, 6 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << maximumHeight(n, arr);

  

    return 0;

}

Джава

// Java реализация подхода

import java.io.*;

  

class GFG

{

  
// Функция для расчета журнала ()

static int cal_log(int n)

{

    int ans = 0;

  

    while (n > 0) 

    {

        n /= 2;

        ans++;

    }

  

    return ans;

}

  
// Функция для возврата максимума
// высота дерева

static int maximumHeight(int n, int arr[])

{

    int level = cal_log(n / 2 + n % 2);

    return (level - 1);

}

  
// Код драйвера

public static void main (String[] args) 

{

    int arr[] = { 1, 2, 3, 4, 6 };

    int n =arr.length;

    System.out.print( maximumHeight(n, arr));

}
}

  
// Этот код предоставлен anuj_67 ..

C #

// C # реализация подхода

using System;

  

class GFG

{

  
// Функция для расчета журнала ()

static int cal_log(int n)

{

    int ans = 0;

  

    while (n > 0) 

    {

        n /= 2;

        ans++;

    }

  

    return ans;

}

  
// Функция для возврата максимума
// высота дерева

static int maximumHeight(int n, int []arr)

{

    int level = cal_log(n / 2 + n % 2);

    return (level - 1);

}

  
// Код драйвера

public static void Main () 

{

    int []arr = { 1, 2, 3, 4, 6 };

    int n =arr.Length;

    Console.WriteLine( maximumHeight(n, arr));

}
}

  
// Этот код предоставлен anuj_67 ..

python3

# Python реализация подхода

  
# Функция для расчета журнала ()

def cal_log(n): 

    ans = 0; 

  

    while (n):

        n //= 2; 

        ans+=1; 

  

  

    return ans; 

  

  
# Функция для возврата максимума
# высота дерева

def maximumHeight(n, arr): 

    level = cal_log(n // 2 + n % 2); 

    return (level - 1); 

  

  
# Код драйвера

arr = [ 1, 2, 3, 4, 6 ]; 

n = len(arr); 

print(maximumHeight(n, arr)); 

  
# Этот код предоставлен Принчи Сингхом

Выход:

1

Рекомендуемые посты:

Создайте два BST из данного массива так, чтобы максимальная высота среди них была минимальной

0.00 (0%) 0 votes