K-ésimo elemento más pequeño en un árbol de búsqueda binario perfecto

Dado un BST perfecto con N Nodes y un número entero K, la tarea es encontrar el K -ésimo elemento más pequeño presente en el árbol.

Ejemplo:

Input:
K = 3, N = 15
               50 
            /     \ 
          30        70 
         /  \      /  \ 
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85   
Output: 25

Explanation: 
The 3rd smallest element
in the given BST is 25


Input: 
K = 9, N = 15
              50 
           /       \ 
          30        70 
         /  \      /  \ 
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85    
Output: 55

Explanation: 
The 9th smallest element
in the given BST is 55

Enfoque ingenuo: realice el recorrido en orden en un BST perfecto, como el recorrido de morris o la solución recursiva, que visita cada Node y devuelve la clave de visita k-ésima. Se necesita una complejidad de tiempo O(N) para completar la tarea. 

Enfoque eficiente: 
dado que el BST dado es perfecto y ya se conoce el número de Nodes de todo el árbol, la complejidad computacional para resolver el problema se puede reducir a log(N) . Siga los pasos que se indican a continuación para resolver el problema:

  • en un árbol BST perfecto(N), |N| siempre será impar en un árbol binario perfecto, la ubicación de la mediana en cualquier BST perfecto es piso(|N|/2) + 1.
  • Calcule el número de Nodes en cada subárbol dividiendo el total de Nodes como piso (| N| / 2).
  • El subárbol izquierdo del BST perfecto siempre contendrá el K-ésimo elemento más pequeño si :
    • K < ubicación (mediana (N)) = M esto se debe a que el M elemento más pequeño siempre será más grande que el K elemento más pequeño y cada elemento en el subárbol derecho será más grande que el M elemento más pequeño
  • El sub-árbol derecho de Perfect BST siempre contendrá un R -ésimo elemento más pequeño si :
    • K > ubicación (mediana (N)) = M, en este caso, K – ubicación (mediana (N)) = R es el elemento más pequeño de R en el subárbol derecho. Esto se debe a que el R elemento más pequeño del subárbol derecho es mayor que el M elemento más pequeño y cada elemento del subárbol izquierdo es más pequeño que el M elemento más pequeño, pero el R elemento más pequeño es mayor que todos ellos. Uno puede pensar en R como el nuevo número cuando se pueden ignorar al menos M posibilidades más pequeñas. El elemento más pequeño de R es el elemento más pequeño de K cuando se repite en el subárbol derecho (pero tenga en cuenta que R !=¡K!).
  • Si K es ubicación (mediana (T)), entonces ese Node contiene el K-ésimo elemento más pequeño en BST perfecto.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find K-th
// smallest element in a
// perfect BST
#include <bits/stdc++.h>
using namespace std;
 
// A BST node
struct Node
{
    int key;
    Node *left, *right;
};
 
// A utility function to
// create a new BST node
Node* newNode(int item)
{
    Node* temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to insert a
// new node with given key in BST
Node* insert(Node* node, int key)
{
    // If the tree is empty
    if (node == NULL)
        return newNode(key);
 
    // Recur down the left
    // subtree for smaller values
    if (key < node->key)
        node->left = insert(node->left, key);
 
    // Recur down the right
    // subtree for smaller values
    else if (key > node->key)
        node->right = insert(node->right, key);
 
    // Return the (unchanged) node pointer
    return node;
}
 
// FUnction to find Kth Smallest
// element in a perfect BST
bool KSmallestPerfectBST(Node* root, int k,
                         int treeSize,
                         int& kth_smallest)
{
    if (root == NULL)
        return false;
 
    // Find the median
    // (division operation is floored)
    int median_loc = (treeSize / 2) + 1;
 
    // If the element is at
    // the median
    if (k == median_loc)
    {
        kth_smallest = root->key;
        return true;
    }
 
    // calculate the number of nodes in the
    // right and left sub-trees
    // (division operation is floored)
    int newTreeSize = treeSize / 2;
 
    // If median is located higher
    if (k < median_loc)
    {
        return KSmallestPerfectBST(
            root->left, k,
            newTreeSize, kth_smallest);
    }
 
    // If median is located lower
    int newK = k - median_loc;
    return KSmallestPerfectBST(root->right, newK,
                               newTreeSize,
                               kth_smallest);
}
 
// Driver Code
int main()
{
    /* Let us create following BST
               50
           /       \
          30        70
         /  \      /  \
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85
       */
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    insert(root, 14);
    insert(root, 25);
    insert(root, 35);
    insert(root, 45);
    insert(root, 55);
    insert(root, 65);
    insert(root, 75);
    insert(root, 85);
 
    int n = 15, k = 5;
    int ans = -1;
   
    // Function call
    if (KSmallestPerfectBST(root, k, n, ans)) {
 
        cout << ans << " ";
    }
 
    return 0;
}

Java

// Java program to find K-th
// smallest element in a
// perfect BST
import java.util.*;
 
class GFG{
 
// A BST node
 static class Node
{
    int key;
    Node left, right;
};
 
static int kth_smallest;
 
// A utility function to
// create a new BST node
public static Node newNode(int item)
{
    Node temp = new Node();
    temp.key = item;
    temp.left = temp.right = null;
    return temp;
}
 
// A utility function to insert a
// new node with given key in BST
static Node insert(Node node, int key)
{
     
    // If the tree is empty
    if (node == null)
        return newNode(key);
 
    // Recur down the left
    // subtree for smaller values
    if (key < node.key)
        node.left = insert(node.left, key);
 
    // Recur down the right
    // subtree for smaller values
    else if (key > node.key)
        node.right = insert(node.right, key);
 
    // Return the (unchanged) node pointer
    return node;
}
 
// FUnction to find Kth Smallest
// element in a perfect BST
static boolean KSmallestPerfectBST(Node root, int k,
                                   int treeSize)
{
    if (root == null)
        return false;
 
    // Find the median
    // (division operation is floored)
    int median_loc = (treeSize / 2) + 1;
 
    // If the element is at
    // the median
    if (k == median_loc)
    {
        kth_smallest = root.key;
        return true;
    }
 
    // calculate the number of nodes in the
    // right and left sub-trees
    // (division operation is floored)
    int newTreeSize = treeSize / 2;
 
    // If median is located higher
    if (k < median_loc)
    {
        return KSmallestPerfectBST(
            root.left, k,
            newTreeSize);
    }
 
    // If median is located lower
    int newK = k - median_loc;
    return KSmallestPerfectBST(root.right, newK,
                               newTreeSize);
}
 
// Driver Code
public static void main(String[] args)
{
    /* Let us create following BST
               50
           /       \
          30        70
         /  \      /  \
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85
       */
    Node root = null;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    insert(root, 14);
    insert(root, 25);
    insert(root, 35);
    insert(root, 45);
    insert(root, 55);
    insert(root, 65);
    insert(root, 75);
    insert(root, 85);
 
    int n = 15, k = 5;
   
    // Function call
    if (KSmallestPerfectBST(root, k, n))
    {
        System.out.print(kth_smallest + " ");
    }
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to find K-th
# smallest element in a perfect BST
kth_smallest = 0
 
# A BST node
class newNode:
     
    def __init__(self, item):
         
        self.key = item
        self.left = None
        self.right = None
 
# A utility function to insert a
# new node with given key in BST
def insert(node, key):
     
    # If the tree is empty
    if (node == None):
        return newNode(key)
 
    # Recur down the left
    # subtree for smaller values
    if (key < node.key):
        node.left = insert(node.left, key)
 
    # Recur down the right
    # subtree for smaller values
    elif(key > node.key):
        node.right = insert(node.right, key)
 
    # Return the (unchanged) node pointer
    return node
 
# FUnction to find Kth Smallest
# element in a perfect BST
def KSmallestPerfectBST(root, k, treeSize):
     
    global kth_smallest
     
    if (root == None):
        return False
 
    # Find the median
    # (division operation is floored)
    median_loc = (treeSize // 2) + 1
 
    # If the element is at
    # the median
    if (k == median_loc):
        kth_smallest = root.key
        return True
 
    # Calculate the number of nodes in
    # the right and left sub-trees
    # (division operation is floored)
    newTreeSize = treeSize // 2
 
    # If median is located higher
    if (k < median_loc):
        return KSmallestPerfectBST(root.left,
                                   k, newTreeSize)
 
    # If median is located lower
    newK = k - median_loc
    return KSmallestPerfectBST(root.right, newK,
                               newTreeSize)
 
# Driver Code
if __name__ == '__main__':
     
    ''' Let us create following BST
              50
           /       \
          30        70
         /  \      /  \
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85
    '''
    root = None
    root = insert(root, 50)
    insert(root, 30)
    insert(root, 20)
    insert(root, 40)
    insert(root, 70)
    insert(root, 60)
    insert(root, 80)
    insert(root, 14)
    insert(root, 25)
    insert(root, 35)
    insert(root, 45)
    insert(root, 55)
    insert(root, 65)
    insert(root, 75)
    insert(root, 85)
 
    n = 15
    k = 5
   
    # Function call
    if (KSmallestPerfectBST(root, k, n)):
        print(kth_smallest, end = " ")
 
# This code is contributed by ipg2016107

C#

// C# program to find K-th
// smallest element in a
// perfect BST
using System;
class GFG{
 
// A BST node
 public class Node
 {
   public int key;
   public Node left,
               right;
 };
 
static int kth_smallest;
 
// A utility function to
// create a new BST node
public static Node newNode(int item)
{
  Node temp = new Node();
  temp.key = item;
  temp.left = temp.right = null;
  return temp;
}
 
// A utility function to
// insert a new node with
// given key in BST
static Node insert(Node node,
                   int key)
{   
  // If the tree is empty
  if (node == null)
    return newNode(key);
 
  // Recur down the left
  // subtree for smaller values
  if (key < node.key)
    node.left = insert(node.left,
                       key);
 
  // Recur down the right
  // subtree for smaller values
  else if (key > node.key)
    node.right = insert(node.right,
                        key);
 
  // Return the (unchanged)
  // node pointer
  return node;
}
 
// Function to find Kth Smallest
// element in a perfect BST
static bool KSmallestPerfectBST(Node root, int k,
                                int treeSize)
{
  if (root == null)
    return false;
 
  // Find the median
  // (division operation is floored)
  int median_loc = (treeSize / 2) + 1;
 
  // If the element is at
  // the median
  if (k == median_loc)
  {
    kth_smallest = root.key;
    return true;
  }
 
  // calculate the number of nodes 
  // in the right and left sub-trees
  // (division operation is floored)
  int newTreeSize = treeSize / 2;
 
  // If median is located higher
  if (k < median_loc)
  {
    return KSmallestPerfectBST(root.left, k,
                               newTreeSize);
  }
 
  // If median is located lower
  int newK = k - median_loc;
  return KSmallestPerfectBST(root.right, newK,
                             newTreeSize);
}
 
// Driver Code
public static void Main(String[] args)
{
  /* Let us create following BST
               50
           /       \
          30        70
         /  \      /  \
       20   40    60    80
       /\   /\    /\    / \
     14 25 35 45 55 65 75  85
       */
  Node root = null;
  root = insert(root, 50);
  insert(root, 30);
  insert(root, 20);
  insert(root, 40);
  insert(root, 70);
  insert(root, 60);
  insert(root, 80);
  insert(root, 14);
  insert(root, 25);
  insert(root, 35);
  insert(root, 45);
  insert(root, 55);
  insert(root, 65);
  insert(root, 75);
  insert(root, 85);
 
  int n = 15, k = 5;
 
  // Function call
  if (KSmallestPerfectBST(root,
                          k, n))
  {
    Console.Write(kth_smallest + " ");
  }
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to find K-th
// smallest element in a
// perfect BST
 
// A BST node
 class Node
 {
     constructor()
     {
         this.key = 0;
         this.left = null;
         this.right = null;
     }
 };
 
var kth_smallest;
 
// A utility function to
// create a new BST node
function newNode(item)
{
  var temp = new Node();
  temp.key = item;
  temp.left = temp.right = null;
  return temp;
}
 
// A utility function to
// insert a new node with
// given key in BST
function insert( node, key)
{   
  // If the tree is empty
  if (node == null)
    return newNode(key);
 
  // Recur down the left
  // subtree for smaller values
  if (key < node.key)
    node.left = insert(node.left,
                       key);
 
  // Recur down the right
  // subtree for smaller values
  else if (key > node.key)
    node.right = insert(node.right,
                        key);
 
  // Return the (unchanged)
  // node pointer
  return node;
}
 
// Function to find Kth Smallest
// element in a perfect BST
function KSmallestPerfectBST(root, k, treeSize)
{
  if (root == null)
    return false;
 
  // Find the median
  // (division operation is floored)
  var median_loc = parseInt(treeSize / 2) + 1;
 
  // If the element is at
  // the median
  if (k == median_loc)
  {
    kth_smallest = root.key;
    return true;
  }
 
  // calculate the number of nodes 
  // in the right and left sub-trees
  // (division operation is floored)
  var newTreeSize = parseInt(treeSize / 2);
 
  // If median is located higher
  if (k < median_loc)
  {
    return KSmallestPerfectBST(root.left, k,
                               newTreeSize);
  }
 
  // If median is located lower
  var newK = k - median_loc;
  return KSmallestPerfectBST(root.right, newK,
                             newTreeSize);
}
 
// Driver Code
/* Let us create following BST
             50
         /       \
        30        70
       /  \      /  \
     20   40    60    80
     /\   /\    /\    / \
   14 25 35 45 55 65 75  85
     */
var root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
insert(root, 14);
insert(root, 25);
insert(root, 35);
insert(root, 45);
insert(root, 55);
insert(root, 65);
insert(root, 75);
insert(root, 85);
var n = 15, k = 5;
// Function call
if (KSmallestPerfectBST(root,
                        k, n))
{
  document.write(kth_smallest + " ");
}
 
// This code is contributed by rrrtnx.
</script>
Producción

35 

Complejidad temporal: O(Log(N)) 
Espacio auxiliar: O(Log(N))

Publicación traducida automáticamente

Artículo escrito por ephi2g y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *