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>
35
Complejidad temporal: O(Log(N))
Espacio auxiliar: O(Log(N))