Dado un árbol de búsqueda binaria, la tarea es encontrar el K-ésimo elemento más grande en el árbol de búsqueda binaria.
Ejemplo:
Input : k = 3 Root of following BST 10 / \ 4 20 / / \ 2 15 40 Output : 15
La idea es utilizar Reverse Morris Traversal , que se basa en Threaded Binary Trees . Los árboles binarios enhebrados utilizan los punteros NULL para almacenar la información del sucesor y el predecesor, lo que nos ayuda a utilizar la memoria desperdiciada por esos punteros NULL.
Lo especial del recorrido de Morris es que podemos realizar un recorrido en orden sin usar la pila o la recursión, lo que nos ahorra memoria consumida por la pila o la pila de llamadas de recursión.
Reverse Morris traversal es justo lo contrario de Morris traversal, que se usa principalmente para hacer Reverse Inorder traversal con memoria extra constante O (1) consumida, ya que no usa ninguna Pila o Recursión.
Para encontrar el K-ésimo elemento más grandeen un árbol de búsqueda binario, la lógica más simple es hacer un recorrido en orden inverso y mientras se realiza un recorrido en orden inverso simplemente mantener un recuento del número de Nodes visitados. Cuando el conteo se vuelve igual a k, detenemos el recorrido e imprimimos los datos. Utiliza el hecho de que el recorrido en orden inverso nos dará una lista ordenada en orden descendente.
Algoritmo
1) Initialize Current as root. 2) Initialize a count variable to 0. 3) While current is not NULL : 3.1) If current has no right child a) Increment count and check if count is equal to K. 1) If count is equal to K, simply return current Node as it is the Kth largest Node. b) Otherwise, Move to the left child of current. 3.2) Else, here we have 2 cases: a) Find the inorder successor of current Node. Inorder successor is the left most Node in the right subtree or right child itself. b) If the left child of the inorder successor is NULL: 1) Set current as the left child of its inorder successor. 2) Move current Node to its right. c) Else, if the threaded link between the current Node and it's inorder successor already exists : 1) Set left pointer of the inorder successor as NULL. 2) Increment count and check if count is equal to K. a) If count is equal to K, simply return current Node as it is the Kth largest Node. 3) Otherwise, Move current to it's left child.
C++
// CPP code for finding K-th largest Node using O(1) // extra memory and reverse Morris traversal. #include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node *left, *right; }; // helper function to create a new Node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->right = temp->left = NULL; return temp; } Node* KthLargestUsingMorrisTraversal(Node* root, int k) { Node* curr = root; Node* Klargest = NULL; // count variable to keep count of visited Nodes int count = 0; while (curr != NULL) { // if right child is NULL if (curr->right == NULL) { // first increment count and check if count = k if (++count == k) Klargest = curr; // otherwise move to the left child curr = curr->left; } else { // find inorder successor of current Node Node* succ = curr->right; while (succ->left != NULL && succ->left != curr) succ = succ->left; if (succ->left == NULL) { // set left child of successor to the // current Node succ->left = curr; // move current to its right curr = curr->right; } // restoring the tree back to original binary // search tree removing threaded links else { succ->left = NULL; if (++count == k) Klargest = curr; // move current to its left child curr = curr->left; } } } return Klargest; } int main() { // Your C++ Code /* Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10 */ Node* root = newNode(4); root->left = newNode(2); root->right = newNode(7); root->left->left = newNode(1); root->left->right = newNode(3); root->right->left = newNode(6); root->right->right = newNode(10); cout << "Finding K-th largest Node in BST : " << KthLargestUsingMorrisTraversal(root, 2)->data; return 0; }
Java
// Java Program for finding K-th largest Node using O(1) // extra memory and reverse Morris traversal. class GfG { static class Node { int data; Node left, right; } // helper function to create a new Node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.right = null; temp.left = null; return temp; } static Node KthLargestUsingMorrisTraversal(Node root, int k) { Node curr = root; Node Klargest = null; // count variable to keep count of visited Nodes int count = 0; while (curr != null) { // if right child is NULL if (curr.right == null) { // first increment count and check if count = k if (++count == k) Klargest = curr; // otherwise move to the left child curr = curr.left; } else { // find inorder successor of current Node Node succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null) { // set left child of successor to the // current Node succ.left = curr; // move current to its right curr = curr.right; } // restoring the tree back to original binary // search tree removing threaded links else { succ.left = null; if (++count == k) Klargest = curr; // move current to its left child curr = curr.left; } } } return Klargest; } // Driver code public static void main(String[] args) { // Your Java Code /* Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10 */ Node root = newNode(4); root.left = newNode(2); root.right = newNode(7); root.left.left = newNode(1); root.left.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(10); System.out.println("Finding K-th largest Node in BST : " + KthLargestUsingMorrisTraversal(root, 2).data); } }
Python3
# Python3 code for finding K-th largest # Node using O(1) extra memory and # reverse Morris traversal. # helper function to create a new Node class newNode: def __init__(self, data): self.data = data self.right = self.left = None def KthLargestUsingMorrisTraversal(root, k): curr = root Klargest = None # count variable to keep count # of visited Nodes count = 0 while (curr != None): # if right child is None if (curr.right == None): # first increment count and # check if count = k count += 1 if (count == k): Klargest = curr # otherwise move to the left child curr = curr.left else: # find inorder successor of # current Node succ = curr.right while (succ.left != None and succ.left != curr): succ = succ.left if (succ.left == None): # set left child of successor # to the current Node succ.left = curr # move current to its right curr = curr.right # restoring the tree back to # original binary search tree # removing threaded links else: succ.left = None count += 1 if (count == k): Klargest = curr # move current to its left child curr = curr.left return Klargest # Driver Code if __name__ == '__main__': # Constructed binary tree is # 4 # / \ # 2 7 # / \ / \ # 1 3 6 10 root = newNode(4) root.left = newNode(2) root.right = newNode(7) root.left.left = newNode(1) root.left.right = newNode(3) root.right.left = newNode(6) root.right.right = newNode(10) print("Finding K-th largest Node in BST : ", KthLargestUsingMorrisTraversal(root, 2).data) # This code is contributed by PranchalK
C#
// C# Program for finding K-th largest Node using O(1) // extra memory and reverse Morris traversal. using System; using System.Collections.Generic; class GfG { public class Node { public int data; public Node left, right; } // helper function to create a new Node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.right = null; temp.left = null; return temp; } static Node KthLargestUsingMorrisTraversal(Node root, int k) { Node curr = root; Node Klargest = null; // count variable to keep count of visited Nodes int count = 0; while (curr != null) { // if right child is NULL if (curr.right == null) { // first increment count and check if count = k if (++count == k) Klargest = curr; // otherwise move to the left child curr = curr.left; } else { // find inorder successor of current Node Node succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null) { // set left child of successor to the // current Node succ.left = curr; // move current to its right curr = curr.right; } // restoring the tree back to original binary // search tree removing threaded links else { succ.left = null; if (++count == k) Klargest = curr; // move current to its left child curr = curr.left; } } } return Klargest; } // Driver code public static void Main(String[] args) { // Your C# Code /* Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10 */ Node root = newNode(4); root.left = newNode(2); root.right = newNode(7); root.left.left = newNode(1); root.left.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(10); Console.Write("Finding K-th largest Node in BST : " + KthLargestUsingMorrisTraversal(root, 2).data); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // JavaScript Program for finding // K-th largest Node using O(1) // extra memory and reverse // Morris traversal. class Node { constructor(){ this.data = 0; this.left = null; this.right = null; } } // helper function to create a new Node function newNode(data) { var temp = new Node(); temp.data = data; temp.right = null; temp.left = null; return temp; } function KthLargestUsingMorrisTraversal(root , k) { var curr = root; var Klargest = null; // count variable to keep count of visited Nodes var count = 0; while (curr != null) { // if right child is NULL if (curr.right == null) { // first increment count and // check if count = k if (++count == k) Klargest = curr; // otherwise move to the left child curr = curr.left; } else { // find inorder successor of // current Node var succ = curr.right; while (succ.left != null && succ.left != curr) succ = succ.left; if (succ.left == null) { // set left child of successor to the // current Node succ.left = curr; // move current to its right curr = curr.right; } // restoring the tree back to original binary // search tree removing threaded links else { succ.left = null; if (++count == k) Klargest = curr; // move current to its left child curr = curr.left; } } } return Klargest; } // Driver code // Your JavaScript Code /* Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10 */ root = newNode(4); root.left = newNode(2); root.right = newNode(7); root.left.left = newNode(1); root.left.right = newNode(3); root.right.left = newNode(6); root.right.right = newNode(10); document.write("Finding K-th largest Node in BST : " + KthLargestUsingMorrisTraversal(root, 2).data); // This code contributed by aashish1995 </script>
Finding K-th largest Node in BST : 7
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por AnishSinghWalia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA