Dado un árbol de búsqueda binaria (BST) que consta de N Nodes y dos Nodes A y B , la tarea es encontrar la mediana de todos los Nodes en el BST dado cuyos valores se encuentran en el rango [A, B] .
Ejemplos:
Entrada: A = 3, B = 11
Salida: 6
Explicación:
Los Nodes que se encuentran sobre el rango [3, 11] son {3, 4, 6, 8, 11}. La mediana de los Nodes dados es 6.Entrada: A = 6, B = 15
Salida: 9.5
Enfoque: el problema dado se puede resolver realizando cualquier recorrido de árbol en el árbol dado y almacenando todos los Nodes que se encuentran en el rango [A, B] , y encuentra la mediana de todos los elementos almacenados. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos V que almacene todos los valores del árbol que se encuentra sobre el rango [A, B] .
- Realice el recorrido Inorder del árbol dado y si el valor de algún Node se encuentra sobre el rango [A, B] , inserte ese valor en el vector V .
- Después de completar los pasos anteriores, imprima el valor de la mediana de todos los elementos almacenados en el vector V como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Tree Node structure
struct Node {
struct Node *left, *right;
int key;
};
// Function to create a new BST node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a new node with
// given key in BST
Node* insertNode(Node* node, int key)
{
// If the tree is empty,
// return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
node->left = insertNode(
node->left, key);
else if (key > node->key)
node->right = insertNode(
node->right, key);
// Return the node pointer
return node;
}
// Function to find all the nodes that
// lies over the range [node1, node2]
void getIntermediateNodes(
Node* root, vector<int>& interNodes,
int node1, int node2)
{
// If the tree is empty, return
if (root == NULL)
return;
// Traverse for the left subtree
getIntermediateNodes(root->left,
interNodes,
node1, node2);
// If a second node is found,
// then update the flag as false
if (root->key <= node2
and root->key >= node1) {
interNodes.push_back(root->key);
}
// Traverse the right subtree
getIntermediateNodes(root->right,
interNodes,
node1, node2);
}
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
float findMedian(Node* root, int node1,
int node2)
{
// Stores all the nodes in
// the range [node1, node2]
vector<int> interNodes;
getIntermediateNodes(root, interNodes,
node1, node2);
// Store the size of the array
int nSize = interNodes.size();
// Print the median of array
// based on the size of array
return (nSize % 2 == 1)
? (float)interNodes[nSize / 2]
: (float)(interNodes[(nSize - 1) / 2]
+ interNodes[nSize / 2])
/ 2;
}
// Driver Code
int main()
{
// Given BST
struct Node* root = NULL;
root = insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 1);
insertNode(root, 6);
insertNode(root, 4);
insertNode(root, 11);
insertNode(root, 15);
cout << findMedian(root, 3, 11);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Tree Node structure
static class Node
{
Node left, right;
int key;
};
static Vector<Integer> interNodes = new Vector<Integer>();
// Function to create a new BST node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// Function to insert a new node with
// given key in BST
static Node insertNode(Node node, int key)
{
// If the tree is empty,
// return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insertNode(
node.left, key);
else if (key > node.key)
node.right = insertNode(
node.right, key);
// Return the node pointer
return node;
}
// Function to find all the nodes that
// lies over the range [node1, node2]
static void getIntermediateNodes(Node root,
int node1,
int node2)
{
// If the tree is empty, return
if (root == null)
return;
// Traverse for the left subtree
getIntermediateNodes(root.left,
node1, node2);
// If a second node is found,
// then update the flag as false
if (root.key <= node2 &&
root.key >= node1)
{
interNodes.add(root.key);
}
// Traverse the right subtree
getIntermediateNodes(root.right,
node1, node2);
}
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
static float findMedian(Node root, int node1,
int node2)
{
// Stores all the nodes in
// the range [node1, node2]
getIntermediateNodes(root,
node1, node2);
// Store the size of the array
int nSize = interNodes.size();
// Print the median of array
// based on the size of array
return (nSize % 2 == 1) ?
(float)interNodes.get(nSize / 2) :
(float)(interNodes.get((nSize - 1) / 2) +
interNodes.get(nSize / 2)) / 2;
}
// Driver Code
public static void main(String[] args)
{
// Given BST
Node root = null;
root = insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 1);
insertNode(root, 6);
insertNode(root, 4);
insertNode(root, 11);
insertNode(root, 15);
System.out.print(findMedian(root, 3, 11));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Tree Node structure class Node: def __init__(self, key): self.key = key self.left = None self.right = None interNodes = [] # Function to create a new BST node def newNode(key): temp = Node(key) return temp # Function to insert a new node with # given key in BST def insertNode(node, key): # If the tree is empty, # return a new node if (node == None): return newNode(key) # Otherwise, recur down the tree if (key < node.key): node.left = insertNode(node.left, key) elif (key > node.key): node.right = insertNode(node.right, key) # Return the node pointer return node # Function to find all the nodes that # lies over the range [node1, node2] def getIntermediateNodes(root, node1, node2): # If the tree is empty, return if (root == None): return # Traverse for the left subtree getIntermediateNodes(root.left, node1, node2) # If a second node is found, # then update the flag as false if (root.key <= node2 and root.key >= node1): interNodes.append(root.key) # Traverse the right subtree getIntermediateNodes(root.right, node1, node2) # Function to find the median of all # the values in the given BST that # lies over the range [node1, node2] def findMedian(root, node1, node2): # Stores all the nodes in # the range [node1, node2] getIntermediateNodes(root, node1, node2) # Store the size of the array nSize = len(interNodes) # Print the median of array # based on the size of array if nSize % 2 == 1: return interNodes[int(nSize / 2)] else: return (interNodes[int((nSize - 1) / 2)] + interNodes[nSize / 2]) / 2 # Given BST root = None root = insertNode(root, 8) insertNode(root, 3) insertNode(root, 1) insertNode(root, 6) insertNode(root, 4) insertNode(root, 11) insertNode(root, 15) print(findMedian(root, 3, 11)) # This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Tree Node structure
class Node
{
public Node left, right;
public int key;
};
static List<int> interNodes = new List<int>();
// Function to create a new BST node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// Function to insert a new node with
// given key in BST
static Node insertNode(Node node, int key)
{
// If the tree is empty,
// return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insertNode(
node.left, key);
else if (key > node.key)
node.right = insertNode(
node.right, key);
// Return the node pointer
return node;
}
// Function to find all the nodes that
// lies over the range [node1, node2]
static void getIntermediateNodes(Node root,
int node1,
int node2)
{
// If the tree is empty, return
if (root == null)
return;
// Traverse for the left subtree
getIntermediateNodes(root.left,
node1, node2);
// If a second node is found,
// then update the flag as false
if (root.key <= node2 &&
root.key >= node1)
{
interNodes.Add(root.key);
}
// Traverse the right subtree
getIntermediateNodes(root.right,
node1, node2);
}
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
static float findMedian(Node root, int node1,
int node2)
{
// Stores all the nodes in
// the range [node1, node2]
getIntermediateNodes(root,
node1, node2);
// Store the size of the array
int nSize = interNodes.Count;
// Print the median of array
// based on the size of array
return (nSize % 2 == 1) ?
(float)interNodes[nSize / 2] :
(float)(interNodes[(nSize - 1) / 2] +
interNodes[nSize / 2]) / 2;
}
// Driver Code
public static void Main(String[] args)
{
// Given BST
Node root = null;
root = insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 1);
insertNode(root, 6);
insertNode(root, 4);
insertNode(root, 11);
insertNode(root, 15);
Console.Write(findMedian(root, 3, 11));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Tree Node structure
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
let interNodes = [];
// Function to create a new BST node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to insert a new node with
// given key in BST
function insertNode(node, key)
{
// If the tree is empty,
// return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insertNode(
node.left, key);
else if (key > node.key)
node.right = insertNode(
node.right, key);
// Return the node pointer
return node;
}
// Function to find all the nodes that
// lies over the range [node1, node2]
function getIntermediateNodes(root, node1, node2)
{
// If the tree is empty, return
if (root == null)
return;
// Traverse for the left subtree
getIntermediateNodes(root.left,
node1, node2);
// If a second node is found,
// then update the flag as false
if (root.key <= node2 &&
root.key >= node1)
{
interNodes.push(root.key);
}
// Traverse the right subtree
getIntermediateNodes(root.right,
node1, node2);
}
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
function findMedian(root, node1, node2)
{
// Stores all the nodes in
// the range [node1, node2]
getIntermediateNodes(root, node1, node2);
// Store the size of the array
let nSize = interNodes.length;
// Print the median of array
// based on the size of array
return (nSize % 2 == 1) ?
interNodes[parseInt(nSize / 2, 10)] :
(interNodes[parseInt((nSize - 1) / 2, 10)] +
interNodes[nSize / 2]) / 2;
}
// Given BST
let root = null;
root = insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 1);
insertNode(root, 6);
insertNode(root, 4);
insertNode(root, 11);
insertNode(root, 15);
document.write(findMedian(root, 3, 11));
// This code is contributed by suresh07.
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por yogesh irale y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA