Dada una array de enteros, la tarea es encontrar la secuencia en la que estos enteros deben agregarse a un árbol AVL de modo que no se requieran rotaciones para equilibrar el árbol.
Ejemplos:
Input : array = {1, 2, 3}
Output : 2 1 3
Input : array = {2, 4, 1, 3, 5, 6, 7}
Output : 4 2 6 1 3 5 7
Acercarse :
- Ordenar la array dada de enteros.
- Cree el árbol AVL a partir de la array ordenada siguiendo el enfoque que se describe aquí .
- Ahora, encuentre el recorrido de orden de nivel del árbol que es la secuencia requerida.
- Agregar números en la secuencia encontrada en el paso anterior siempre mantendrá la propiedad de equilibrio de altura de todos los Nodes en el árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
/* A Binary Tree node */
struct TNode {
int data;
struct TNode* left;
struct TNode* right;
};
struct TNode* newNode(int data);
/* Function to construct AVL tree
from a sorted array */
struct TNode* sortedArrayToBST(vector<int> arr, int start, int end)
{
/* Base Case */
if (start > end)
return NULL;
/* Get the middle element
and make it root */
int mid = (start + end) / 2;
struct TNode* root = newNode(arr[mid]);
/* Recursively construct the
left subtree and make it
left child of root */
root->left = sortedArrayToBST(arr, start, mid - 1);
/* Recursively construct the
right subtree and make it
right child of root */
root->right = sortedArrayToBST(arr, mid + 1, end);
return root;
}
/* Helper function that allocates
a new node with the given data
and NULL to the left and
the right pointers. */
struct TNode* newNode(int data)
{
struct TNode* node = new TNode();
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// This function is used for testing purpose
void printLevelOrder(TNode *root)
{
if (root == NULL) return;
queue<TNode *> q;
q.push(root);
while (q.empty() == false)
{
TNode *node = q.front();
cout << node->data << " ";
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
}
/* Driver program to
test above functions */
int main()
{
// Assuming the array is sorted
vector<int> arr = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.size();
/* Convert List to AVL tree */
struct TNode* root = sortedArrayToBST(arr, 0, n - 1);
printLevelOrder(root);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class solution
{
/* A Binary Tree node */
static class TNode {
int data;
TNode left;
TNode right;
}
/* Function to con AVL tree
from a sorted array */
static TNode sortedArrayToBST(int arr[], int start, int end)
{
/* Base Case */
if (start > end)
return null;
/* Get the middle element
and make it root */
int mid = (start + end) / 2;
TNode root = newNode(arr[mid]);
/* Recursively construct the
left subtree and make it
left child of root */
root.left = sortedArrayToBST(arr, start, mid - 1);
/* Recursively construct the
right subtree and make it
right child of root */
root.right = sortedArrayToBST(arr, mid + 1, end);
return root;
}
/* Helper function that allocates
a new node with the given data
and null to the left and
the right pointers. */
static TNode newNode(int data)
{
TNode node = new TNode();
node.data = data;
node.left = null;
node.right = null;
return node;
}
// This function is used for testing purpose
static void printLevelOrder(TNode root)
{
if (root == null) return;
Queue<TNode > q= new LinkedList<TNode>();
q.add(root);
while (q.size()>0)
{
TNode node = q.element();
System.out.print( node.data + " ");
q.remove();
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
}
/* Driver program to
test above functions */
public static void main(String args[])
{
// Assuming the array is sorted
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.length;
/* Convert List to AVL tree */
TNode root = sortedArrayToBST(arr, 0, n - 1);
printLevelOrder(root);
}
}
//contributed by Arnab Kundu
Python3
# Python3 code to print order of # insertion into AVL tree to # ensure no rotations # Tree Node class Node: def __init__(self, d): self.data = d self.left = None self.right = None # Function to convert sorted array # to a balanced AVL Tree/BST # Input : sorted array of integers # Output: root node of balanced AVL Tree/BST def sortedArrayToBST(arr): if not arr: return None # Find middle and get its floor value mid = int((len(arr)) / 2) root = Node(arr[mid]) # Recursively construct the left # and right subtree root.left = sortedArrayToBST(arr[:mid]) root.right = sortedArrayToBST(arr[mid + 1:]) # Return the root of the # constructed tree return root # A utility function to print the # Level Order Traversal of AVL Tree # using a Queue def printLevelOrder(root): if not root: return q = [] q.append(root) # Keep printing the top element and # adding to queue while it is not empty while q != []: node = q.pop(0) print(node.data, end=" ") # If left node exists, enqueue it if node.left: q.append(node.left) # If right node exists, enqueue it if node.right: q.append(node.right) # Driver Code arr = [1, 2, 3, 4, 5, 6, 7] root = sortedArrayToBST(arr) printLevelOrder(root) # This code is contributed # by Adikar Bharath
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
/* A Binary Tree node */
public class TNode
{
public int data;
public TNode left;
public TNode right;
}
/* Function to con AVL tree
from a sorted array */
static TNode sortedArrayToBST(int []arr,
int start, int end)
{
/* Base Case */
if (start > end)
return null;
/* Get the middle element
and make it root */
int mid = (start + end) / 2;
TNode root = newNode(arr[mid]);
/* Recursively construct the
left subtree and make it
left child of root */
root.left = sortedArrayToBST(arr, start, mid - 1);
/* Recursively construct the
right subtree and make it
right child of root */
root.right = sortedArrayToBST(arr, mid + 1, end);
return root;
}
/* Helper function that allocates
a new node with the given data
and null to the left and
the right pointers. */
static TNode newNode(int data)
{
TNode node = new TNode();
node.data = data;
node.left = null;
node.right = null;
return node;
}
// This function is used for testing purpose
static void printLevelOrder(TNode root)
{
if (root == null) return;
Queue<TNode > q = new Queue<TNode>();
q.Enqueue(root);
while (q.Count > 0)
{
TNode node = q.Peek();
Console.Write( node.data + " ");
q.Dequeue();
if (node.left != null)
q.Enqueue(node.left);
if (node.right != null)
q.Enqueue(node.right);
}
}
/* Driver code */
public static void Main()
{
// Assuming the array is sorted
int []arr = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.Length;
/* Convert List to AVL tree */
TNode root = sortedArrayToBST(arr, 0, n - 1);
printLevelOrder(root);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
/* A Binary Tree node */
class TNode
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
/* Function to con AVL tree
from a sorted array */
function sortedArrayToBST(arr, start, end)
{
/* Base Case */
if (start > end)
return null;
/* Get the middle element
and make it root */
var mid = parseInt((start + end) / 2);
var root = newNode(arr[mid]);
/* Recursively construct the
left subtree and make it
left child of root */
root.left = sortedArrayToBST(arr, start, mid - 1);
/* Recursively construct the
right subtree and make it
right child of root */
root.right = sortedArrayToBST(arr, mid + 1, end);
return root;
}
/* Helper function that allocates
a new node with the given data
and null to the left and
the right pointers. */
function newNode(data)
{
var node = new TNode();
node.data = data;
node.left = null;
node.right = null;
return node;
}
// This function is used for testing purpose
function printLevelOrder(root)
{
if (root == null) return;
var q = [];
q.push(root);
while (q.length > 0)
{
var node = q[0];
document.write( node.data + " ");
q.shift();
if (node.left != null)
q.push(node.left);
if (node.right != null)
q.push(node.right);
}
}
/* Driver code */
// Assuming the array is sorted
var arr = [1, 2, 3, 4, 5, 6, 7];
var n = arr.length;
/* Convert List to AVL tree */
var root = sortedArrayToBST(arr, 0, n - 1);
printLevelOrder(root);
// This code is contributed by itsok.
</script>
Producción:
4 2 6 1 3 5 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)