Dada una serie de valores. La tarea es implementar un árbol de búsqueda binaria utilizando los valores de la array donde cada Node almacena la cantidad máxima de Nodes en la ruta, comenzando desde el propio Node y terminando en cualquier hoja del árbol.
Nota : el número máximo de Nodes en la ruta de cualquier Node a cualquier Node hoja en un BST es la altura del subárbol enraizado en ese Node.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida:
datos = 1 altura = 6
datos = 2 altura = 5
datos = 3 altura = 4
datos = 4 altura = 3
datos = 5 altura = 2
datos = 6 altura = 1
datos = 7 altura = 0Entrada: arr[] = {4, 12, 10, 5, 11, 8, 7, 6, 9}
Salida:
datos = 4 altura = 6
datos = 5 altura = 3
datos = 6 altura = 0
datos = 7 altura = 1
datos = 8 altura = 2
datos = 9 altura = 0
datos = 10 altura = 4
datos = 11 altura = 0
datos = 12 altura = 5
La idea es agregar Nodes al estilo BST. La altura del padre dice que P se actualizará solo cuando el nuevo Node se agregue al subárbol, lo que contribuye a la altura de P Y (lógico) la altura del subárbol también aumentó después de agregar el nuevo Node.
Digamos que un árbol existente es (los datos del Node están en rojo y la altura actual del Node en verde):
Ahora vamos a agregar un nuevo Node que contiene el valor 6, la ruta tomada por el Node para agregarse se ha resaltado en azul:
Con la adición del nuevo Node, la altura de su padre inmediato aumentará (solo si la altura del padre inmediato del Node que contiene 6 se ve afectada por esta adición, lo que en este caso es cierto). Una vez que se incrementa la altura del padre, se verificará si el subárbol donde está presente el padre es el principal contribuyente a la altura del Node que tiene ese subárbol como hijo; en caso afirmativo, se aumentará la altura de ese Node, en acorta el incremento de altura si se propaga hacia arriba.
Ahora vamos a agregar otro Node que contenga el valor 9 y la ruta que tomará para agregarse a su posición final está en azul:
Dado que la altura del padre inmediato del Node que contiene el valor 9 no se ve afectada por esta adición, la altura de su padre no se verá afectada y el incremento de altura no se propagará hacia arriba.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
// Structure containing basic template od a node
struct node {
// Stores the data and current height of the node
int data;
int height;
struct node* right;
struct node* left;
};
int indicator = 0;
void left_insert(struct node*, struct node*);
void right_insert(struct node*, struct node*);
// Inorder traversal of the tree
void traverse(struct node* head)
{
if (head != NULL) {
traverse(head->left);
cout << " data = " << head->data;
cout<< " height = " << head->height << endl;
traverse(head->right);
}
}
// Insertion to the left sub-tree
void left_insert(struct node* head, struct node* temp)
{
// Child node of Current head
struct node* child = NULL;
if (head->data > temp->data) {
if (head->left == NULL) {
indicator = 1;
child = head->left = temp;
}
else {
left_insert(head->left, temp);
child = head->left;
}
}
else {
right_insert(head, temp);
}
if ((indicator == 1) && (child != NULL)) {
if (head->height > child->height) {
// Ending propagation to height of above nodes
indicator = 0;
}
else {
head->height += 1;
}
}
}
// Insertion to the right sub-tree
void right_insert(struct node* head, struct node* temp)
{
// Child node of Current head
struct node* child = NULL;
if (head->data < temp->data) {
if (head->right == NULL) {
indicator = 1;
child = head->right = temp;
}
else {
right_insert(head->right, temp);
child = head->right;
}
}
else {
left_insert(head, temp);
}
if ((indicator == 1) && (child != NULL)) {
if (head->height > child->height) {
// Ending propagation to height of above nodes
indicator = 0;
}
else {
head->height += 1;
}
}
}
// Function to create node and push
// it to its appropriate position
void add_nodes(struct node** head, int value)
{
struct node *temp_head = *head, *temp;
if (*head == NULL) {
// When first node is added
*head = new node();
(*head)->data = value;
(*head)->height = 0;
(*head)->right = (*head)->left = NULL;
}
else {
temp = new node();
temp->data = value;
temp->height = 0;
temp->right = temp->left = NULL;
left_insert(temp_head, temp);
temp_head = *head;
indicator = 0;
}
}
// Driver Code
int main()
{
struct node *head = NULL, *temp_head = NULL;
add_nodes(&head, 4);
add_nodes(&head, 12);
add_nodes(&head, 10);
add_nodes(&head, 5);
add_nodes(&head, 11);
add_nodes(&head, 8);
add_nodes(&head, 7);
add_nodes(&head, 6);
add_nodes(&head, 9);
temp_head = head;
// Traversing the tree to display
// the updated height values
traverse(temp_head);
return 0;
}
// This code is contributed by rrrtnx.
C
// C implementation of above approach
#include <stdio.h>
#include <stdlib.h>
// Structure containing basic template od a node
struct node {
// Stores the data and current height of the node
int data;
int height;
struct node* right;
struct node* left;
};
int indicator = 0;
void left_insert(struct node*, struct node*);
void right_insert(struct node*, struct node*);
// Inorder traversal of the tree
void traverse(struct node* head)
{
if (head != NULL) {
traverse(head->left);
printf(" data = %d", head->data);
printf(" height = %d\n", head->height);
traverse(head->right);
}
}
// Insertion to the left sub-tree
void left_insert(struct node* head, struct node* temp)
{
// Child node of Current head
struct node* child = NULL;
if (head->data > temp->data) {
if (head->left == NULL) {
indicator = 1;
child = head->left = temp;
}
else {
left_insert(head->left, temp);
child = head->left;
}
}
else {
right_insert(head, temp);
}
if ((indicator == 1) && (child != NULL)) {
if (head->height > child->height) {
// Ending propagation to height of above nodes
indicator = 0;
}
else {
head->height += 1;
}
}
}
// Insertion to the right sub-tree
void right_insert(struct node* head, struct node* temp)
{
// Child node of Current head
struct node* child = NULL;
if (head->data < temp->data) {
if (head->right == NULL) {
indicator = 1;
child = head->right = temp;
}
else {
right_insert(head->right, temp);
child = head->right;
}
}
else {
left_insert(head, temp);
}
if ((indicator == 1) && (child != NULL)) {
if (head->height > child->height) {
// Ending propagation to height of above nodes
indicator = 0;
}
else {
head->height += 1;
}
}
}
// Function to create node and push
// it to its appropriate position
void add_nodes(struct node** head, int value)
{
struct node *temp_head = *head, *temp;
if (*head == NULL) {
// When first node is added
*head = malloc(sizeof(**head));
(*head)->data = value;
(*head)->height = 0;
(*head)->right = (*head)->left = NULL;
}
else {
temp = malloc(sizeof(*temp));
temp->data = value;
temp->height = 0;
temp->right = temp->left = NULL;
left_insert(temp_head, temp);
temp_head = *head;
indicator = 0;
}
}
// Driver Code
int main()
{
struct node *head = NULL, *temp_head = NULL;
add_nodes(&head, 4);
add_nodes(&head, 12);
add_nodes(&head, 10);
add_nodes(&head, 5);
add_nodes(&head, 11);
add_nodes(&head, 8);
add_nodes(&head, 7);
add_nodes(&head, 6);
add_nodes(&head, 9);
temp_head = head;
// Traversing the tree to display
// the updated height values
traverse(temp_head);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Structure containing basic template od a node
static class node
{
// Stores the data and current height of the node
int data;
int height;
node right;
node left;
}
static int indicator = 0;
// Inorder traversal of the tree
static void traverse(node head)
{
if (head != null)
{
traverse(head.left);
System.out.printf(" data = %d", head.data);
System.out.printf(" height = %d\n", head.height);
traverse(head.right);
}
}
// Insertion to the left sub-tree
static void left_insert(node head, node temp)
{
// Child node of Current head
node child = null;
if (head.data > temp.data)
{
if (head.left == null)
{
indicator = 1;
child = head.left = temp;
}
else
{
left_insert(head.left, temp);
child = head.left;
}
}
else
{
right_insert(head, temp);
}
if ((indicator == 1) && (child != null))
{
if (head.height > child.height)
{
// Ending propagation to height of above nodes
indicator = 0;
}
else
{
head.height += 1;
}
}
}
// Insertion to the right sub-tree
static void right_insert(node head, node temp)
{
// Child node of Current head
node child = null;
if (head.data < temp.data)
{
if (head.right == null)
{
indicator = 1;
child = head.right = temp;
}
else
{
right_insert(head.right, temp);
child = head.right;
}
}
else
{
left_insert(head, temp);
}
if ((indicator == 1) && (child != null))
{
if (head.height > child.height)
{
// Ending propagation to height of above nodes
indicator = 0;
}
else
{
head.height += 1;
}
}
}
// Function to create node and push
// it to its appropriate position
static node add_nodes(node head, int value)
{
node temp_head = head, temp;
if (head == null)
{
// When first node is added
head = new node();
(head).data = value;
(head).height = 0;
(head).right = (head).left = null;
}
else
{
temp = new node();
temp.data = value;
temp.height = 0;
temp.right = temp.left = null;
left_insert(temp_head, temp);
temp_head = head;
indicator = 0;
}
return head;
}
// Driver Code
public static void main(String args[])
{
node head = null, temp_head = null;
head = add_nodes(head, 4);
head = add_nodes(head, 12);
head = add_nodes(head, 10);
head = add_nodes(head, 5);
head = add_nodes(head, 11);
head = add_nodes(head, 8);
head = add_nodes(head, 7);
head = add_nodes(head, 6);
head = add_nodes(head, 9);
temp_head = head;
// Traversing the tree to display
// the updated height values
traverse(temp_head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python implementation of above approach
# Structure containing basic template od a node
class node:
def __init__(self) -> None:
# Stores the data and current height of the node
self.data = 0
self.height = 0
self.right = None
self.left = None
# Inorder traversal of the tree
def traverse(head: node) -> None:
if (head != None):
traverse(head.left)
print(" data = {}".format(head.data), end="")
print(" height = {}".format(head.height))
traverse(head.right)
# Insertion to the left sub-tree
def left_insert(head: node, temp: node) -> None:
global indicator
# Child node of Current head
child = None
if (head.data > temp.data):
if (head.left == None):
indicator = 1
child = head.left = temp
else:
left_insert(head.left, temp)
child = head.left
else:
right_insert(head, temp)
if ((indicator == 1) and (child != None)):
if (head.height > child.height):
# Ending propagation to height of above nodes
indicator = 0
else:
head.height += 1
# Insertion to the right sub-tree
def right_insert(head: node, temp: node) -> None:
global indicator
# Child node of Current head
child = None
if (head.data < temp.data):
if (head.right == None):
indicator = 1
child = head.right = temp
else:
right_insert(head.right, temp)
child = head.right
else:
left_insert(head, temp)
if ((indicator == 1) and (child != None)):
if (head.height > child.height):
# Ending propagation to height of above nodes
indicator = 0
else:
head.height += 1
# Function to create node and push
# it to its appropriate position
def add_nodes(head: node, value: int) -> node:
global indicator
temp_head = head
temp = None
if (head == None):
# When first node is added
head = node()
(head).data = value
(head).height = 0
(head).right = (head).left = None
else:
temp = node()
temp.data = value
temp.height = 0
temp.right = temp.left = None
left_insert(temp_head, temp)
temp_head = head
indicator = 0
return head
# Driver Code
if __name__ == "__main__":
indicator = 0
head = None
temp_head = None
head = add_nodes(head, 4)
head = add_nodes(head, 12)
head = add_nodes(head, 10)
head = add_nodes(head, 5)
head = add_nodes(head, 11)
head = add_nodes(head, 8)
head = add_nodes(head, 7)
head = add_nodes(head, 6)
head = add_nodes(head, 9)
temp_head = head
# Traversing the tree to display
# the updated height values
traverse(temp_head)
# This code is contributed by sanjeev2552
C#
// C# implementation of above approach
using System;
public class GFG {
// Structure containing basic template od a node
public class node {
// Stores the data and current height of the node
public int data;
public int height;
public node right;
public node left;
}
static int indicator = 0;
// Inorder traversal of the tree
static void traverse(node head) {
if (head != null) {
traverse(head.left);
Console.Write(" data = {0}", head.data);
Console.Write(" height = {0}\n", head.height);
traverse(head.right);
}
}
// Insertion to the left sub-tree
static void left_insert(node head, node temp) {
// Child node of Current head
node child = null;
if (head.data > temp.data) {
if (head.left == null) {
indicator = 1;
child = head.left = temp;
} else {
left_insert(head.left, temp);
child = head.left;
}
} else {
right_insert(head, temp);
}
if ((indicator == 1) && (child != null)) {
if (head.height > child.height) {
// Ending propagation to height of above nodes
indicator = 0;
} else {
head.height += 1;
}
}
}
// Insertion to the right sub-tree
static void right_insert(node head, node temp) {
// Child node of Current head
node child = null;
if (head.data < temp.data) {
if (head.right == null) {
indicator = 1;
child = head.right = temp;
} else {
right_insert(head.right, temp);
child = head.right;
}
} else {
left_insert(head, temp);
}
if ((indicator == 1) && (child != null)) {
if (head.height > child.height) {
// Ending propagation to height of above nodes
indicator = 0;
} else {
head.height += 1;
}
}
}
// Function to create node and push
// it to its appropriate position
static node add_nodes(node head, int value) {
node temp_head = head, temp;
if (head == null) {
// When first node is added
head = new node();
(head).data = value;
(head).height = 0;
(head).right = (head).left = null;
} else {
temp = new node();
temp.data = value;
temp.height = 0;
temp.right = temp.left = null;
left_insert(temp_head, temp);
temp_head = head;
indicator = 0;
}
return head;
}
// Driver Code
public static void Main(String []args) {
node head = null, temp_head = null;
head = add_nodes(head, 4);
head = add_nodes(head, 12);
head = add_nodes(head, 10);
head = add_nodes(head, 5);
head = add_nodes(head, 11);
head = add_nodes(head, 8);
head = add_nodes(head, 7);
head = add_nodes(head, 6);
head = add_nodes(head, 9);
temp_head = head;
// Traversing the tree to display
// the updated height values
traverse(temp_head);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of above approach
// Structure containing basic template od a node
class node
{
constructor()
{
this.left;
this.right;
this.data;
this.height;
}
}
let indicator = 0;
// Inorder traversal of the tree
function traverse(head)
{
if (head != null)
{
traverse(head.left);
document.write(" data = " + head.data);
document.write(" height = "+
head.height + "</br>");
traverse(head.right);
}
}
// Insertion to the left sub-tree
function left_insert(head, temp)
{
// Child node of Current head
let child = null;
if (head.data > temp.data)
{
if (head.left == null)
{
indicator = 1;
child = head.left = temp;
}
else
{
left_insert(head.left, temp);
child = head.left;
}
}
else
{
right_insert(head, temp);
}
if ((indicator == 1) && (child != null))
{
if (head.height > child.height)
{
// Ending propagation to height
// of above nodes
indicator = 0;
}
else
{
head.height += 1;
}
}
}
// Insertion to the right sub-tree
function right_insert(head, temp)
{
// Child node of Current head
let child = null;
if (head.data < temp.data)
{
if (head.right == null)
{
indicator = 1;
child = head.right = temp;
}
else
{
right_insert(head.right, temp);
child = head.right;
}
}
else
{
left_insert(head, temp);
}
if ((indicator == 1) && (child != null))
{
if (head.height > child.height)
{
// Ending propagation to height
// of above nodes
indicator = 0;
}
else
{
head.height += 1;
}
}
}
// Function to create node and push
// it to its appropriate position
function add_nodes(head, value)
{
let temp_head = head, temp;
if (head == null)
{
// When first node is added
head = new node();
(head).data = value;
(head).height = 0;
(head).right = (head).left = null;
}
else
{
temp = new node();
temp.data = value;
temp.height = 0;
temp.right = temp.left = null;
left_insert(temp_head, temp);
temp_head = head;
indicator = 0;
}
return head;
}
// Driver code
let head = null, temp_head = null;
head = add_nodes(head, 4);
head = add_nodes(head, 12);
head = add_nodes(head, 10);
head = add_nodes(head, 5);
head = add_nodes(head, 11);
head = add_nodes(head, 8);
head = add_nodes(head, 7);
head = add_nodes(head, 6);
head = add_nodes(head, 9);
temp_head = head;
// Traversing the tree to display
// the updated height values
traverse(temp_head);
// This code is contributed by divyeshrabadiya07
</script>
Producción:
data = 4 height = 6 data = 5 height = 3 data = 6 height = 0 data = 7 height = 1 data = 8 height = 2 data = 9 height = 0 data = 10 height = 4 data = 11 height = 0 data = 12 height = 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por GauravSingh1203 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA