Dada la altura de un árbol AVL ‘h’, la tarea es encontrar el número mínimo de Nodes que puede tener el árbol.
Ejemplos:
Input : H = 0 Output : N = 1 Only '1' node is possible if the height of the tree is '0' which is the root node. Input : H = 3 Output : N = 7
Enfoque recursivo: en un árbol AVL, debemos mantener la propiedad de equilibrio de altura, es decir, la diferencia en la altura de los subárboles izquierdo y derecho no puede ser distinta de -1, 0 o 1 para cada Node.
Intentaremos crear una relación de recurrencia para encontrar el número mínimo de Nodes para una altura dada, n(h).
- Para altura = 0, solo podemos tener un solo Node en un árbol AVL, es decir, n(0) = 1
- Para altura = 1, podemos tener un mínimo de dos Nodes en un árbol AVL, es decir, n(1) = 2
- Ahora, para cualquier altura ‘h’, la raíz tendrá dos subárboles (izquierdo y derecho). De los cuales uno ha de ser de altura h-1 y otro de h-2. [Node raíz excluido]
- Entonces, n(h) = 1 + n(h-1) + n(h-2) es la relación de recurrencia requerida para h>=2 [se agrega 1 para el Node raíz]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// minimum number of nodes
int AVLnodes(int height)
{
// Base Conditions
if (height == 0)
return 1;
else if (height == 1)
return 2;
// Recursive function call
// for the recurrence relation
return (1 + AVLnodes(height - 1) + AVLnodes(height - 2));
}
// Driver Code
int main()
{
int H = 3;
cout << AVLnodes(H) << endl;
}
Java
// Java implementation of the approach
class GFG{
// Function to find
// minimum number of nodes
static int AVLnodes(int height)
{
// Base Conditions
if (height == 0)
return 1;
else if (height == 1)
return 2;
// Recursive function call
// for the recurrence relation
return (1 + AVLnodes(height - 1) + AVLnodes(height - 2));
}
// Driver Code
public static void main(String args[])
{
int H = 3;
System.out.println(AVLnodes(H));
}
}
Python3
# Python3 implementation of the approach # Function to find minimum # number of nodes def AVLnodes(height): # Base Conditions if (height == 0): return 1 elif (height == 1): return 2 # Recursive function call # for the recurrence relation return (1 + AVLnodes(height - 1) + AVLnodes(height - 2)) # Driver Code if __name__ == '__main__': H = 3 print(AVLnodes(H)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find
// minimum number of nodes
static int AVLnodes(int height)
{
// Base Conditions
if (height == 0)
return 1;
else if (height == 1)
return 2;
// Recursive function call
// for the recurrence relation
return (1 + AVLnodes(height - 1) +
AVLnodes(height - 2));
}
// Driver Code
public static void Main()
{
int H = 3;
Console.Write(AVLnodes(H));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to find minimum
// number of nodes
function AVLnodes($height)
{
// Base Conditions
if ($height == 0)
return 1;
else if ($height == 1)
return 2;
// Recursive function call
// for the recurrence relation
return (1 + AVLnodes($height - 1) +
AVLnodes($height - 2));
}
// Driver Code
$H = 3;
echo(AVLnodes($H));
// This code is contributed
// by Code_Mech.
Javascript
<script>
// Javascript implementation of the approach
// Function to find
// minimum number of nodes
function AVLnodes(height)
{
// Base Conditions
if (height == 0)
return 1;
else if (height == 1)
return 2;
// Recursive function call
// for the recurrence relation
return (1 + AVLnodes(height - 1) +
AVLnodes(height - 2));
}
// Driver code
let H = 3;
document.write(AVLnodes(H));
// This code is contributed by decode2207
</script>
Producción:
7
Enfoque recursivo de cola:
- La función recursiva para encontrar n(h) (número mínimo de Nodes posibles en un árbol AVL con altura ‘h’) es n(h) = 1 + n(h-1) + n(h-2) ; h>=2; n(0)=1 ; n(1)=2;
- Para crear una Función Recursiva de Cola, mantendremos 1 + n(h-1) + n(h-2) como argumentos de función de modo que en lugar de calcularlo, devolvamos directamente su valor a la función principal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to return
//minimum number of nodes
int AVLtree(int H, int a = 1, int b = 2)
{
// Base Conditions
if (H == 0)
return 1;
if (H == 1)
return b;
// Tail Recursive Call
return AVLtree(H - 1, b, a + b + 1);
}
// Driver Code
int main()
{
int H = 5;
int answer = AVLtree(H);
// Output the result
cout << "n(" << H << ") = "
<< answer << endl;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return
//minimum number of nodes
static int AVLtree(int H, int a, int b)
{
// Base Conditions
if (H == 0)
return 1;
if (H == 1)
return b;
// Tail Recursive Call
return AVLtree(H - 1, b, a + b + 1);
}
// Driver Code
public static void main(String[] args)
{
int H = 5;
int answer = AVLtree(H, 1, 2);
// Output the result
System.out.println("n(" + H + ") = " + answer);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach
# Function to return
# minimum number of nodes
def AVLtree(H, a, b):
# Base Conditions
if(H == 0):
return 1;
if(H == 1):
return b;
# Tail Recursive Call
return AVLtree(H - 1, b, a + b + 1);
# Driver Code
if __name__ == '__main__':
H = 5;
answer = AVLtree(H, 1, 2);
# Output the result
print("n(", H , ") = "\
, answer);
# This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return
//minimum number of nodes
static int AVLtree(int H, int a, int b)
{
// Base Conditions
if (H == 0)
return 1;
if (H == 1)
return b;
// Tail Recursive Call
return AVLtree(H - 1, b, a + b + 1);
}
// Driver Code
public static void Main(String[] args)
{
int H = 5;
int answer = AVLtree(H, 1, 2);
// Output the result
Console.WriteLine("n(" + H + ") = " + answer);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the approach
// Function to return
//minimum number of nodes
function AVLtree(H, a, b)
{
// Base Conditions
if (H == 0)
return 1;
if (H == 1)
return b;
// Tail Recursive Call
return AVLtree(H - 1, b, a + b + 1);
}
let H = 5;
let answer = AVLtree(H, 1, 2);
// Output the result
document.write("n(" + H + ") = " + answer);
// This code is contributed by mukesh07.
</script>
Producción:
n(5) = 20