Dado un árbol de búsqueda binaria (BST) y un número entero positivo k, busque el k-ésimo elemento más pequeño en el árbol de búsqueda binaria.
Por ejemplo, en el siguiente BST, si k = 3, la salida debería ser 10, y si k = 5, la salida debería ser 14.
Hemos discutido dos métodos en esta publicación y un método en esta publicación. Todos los métodos anteriores requieren espacio adicional. ¿Cómo encontrar el k’th elemento más grande sin espacio extra?
La idea es utilizar Morris Traversal . En este recorrido, primero creamos enlaces al sucesor Inorder e imprimimos los datos usando estos enlaces, y finalmente revertimos los cambios para restaurar el árbol original. Vea esto para más detalles.
A continuación se muestra la implementación de la idea.
C++
// C++ program to find k'th largest element in BST
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct Node
{
int key;
Node *left, *right;
};
// A function to find
int KSmallestUsingMorris(Node *root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = INT_MIN; // store the Kth smallest
Node *curr = root; // to store the current node
while (curr != NULL)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr->left == NULL)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr->key;
// go to current's right child
curr = curr->right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
// building links
if (pre->right==NULL)
{
//link made to Inorder Successor
pre->right = curr;
curr = curr->left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre->right = NULL;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr->key;
curr = curr->right;
}
}
}
return ksmall; //return the found value
}
// 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, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
for (int k=1; k<=7; k++)
cout << KSmallestUsingMorris(root, k) << " ";
return 0;
}
Java
// Java program to find k'th largest element in BST
import java.util.*;
class GfG {
// A BST node
static class Node
{
int key;
Node left, right;
}
// A function to find
static int KSmallestUsingMorris(Node root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = Integer.MIN_VALUE; // store the Kth smallest
Node curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right== null)
{
//link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
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, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
public static void main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
for (int k=1; k<=7; k++)
System.out.print(KSmallestUsingMorris(root, k) + " ");
}
}
Python3
# Python 3 program to find k'th # largest element in BST # A BST node class Node: # Constructor to create a new node def __init__(self, data): self.key = data self.left = None self.right = None # A function to find def KSmallestUsingMorris(root, k): # Count to iterate over elements # till we get the kth smallest number count = 0 ksmall = -9999999999 # store the Kth smallest curr = root # to store the current node while curr != None: # Like Morris traversal if current does # not have left child rather than # printing as we did in inorder, we # will just increment the count as the # number will be in an increasing order if curr.left == None: count += 1 # if count is equal to K then we # found the kth smallest, so store # it in ksmall if count == k: ksmall = curr.key # go to current's right child curr = curr.right else: # we create links to Inorder Successor # and count using these links pre = curr.left while (pre.right != None and pre.right != curr): pre = pre.right # building links if pre.right == None: # link made to Inorder Successor pre.right = curr curr = curr.left # While breaking the links in so made # temporary threaded tree we will check # for the K smallest condition else: # Revert the changes made in if part # (break link from the Inorder Successor) pre.right = None count += 1 # If count is equal to K then we # found the kth smallest and so # store it in ksmall if count == k: ksmall = curr.key curr = curr.right return ksmall # return the found value # A utility function to insert a new # node with given key in BST def insert(node, key): # If the tree is empty, # return a new node if node == None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) # return the (unchanged) node pointer return node # Driver Code if __name__ == '__main__': # Let us create following BST # 50 # / \ # 30 70 # / \ / \ # 20 40 60 80 root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) for k in range(1,8): print(KSmallestUsingMorris(root, k), end = " ") # This code is contributed by PranchalK
C#
// C# program to find k'th largest element in BST
using System;
class GfG
{
// A BST node
public class Node
{
public int key;
public Node left, right;
}
// A function to find
static int KSmallestUsingMorris(Node root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = int.MinValue; // store the Kth smallest
Node curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right == null)
{
// link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count == k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
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, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
public static void Main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
for (int k = 1; k <= 7; k++)
Console.Write(KSmallestUsingMorris(root, k) + " ");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript program to find k'th largest element in BST
// A BST node
class Node {
constructor() {
this.key = 0;
this.left = null;
this.right = null;
}
}
// A function to find
function KSmallestUsingMorris(root , k)
{
// Count to iterate over elements till we
// get the kth smallest number
var count = 0;
var ksmall = Number.MIN_VALUE; // store the Kth smallest
var curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
var pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right== null)
{
//link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.left = null;
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, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
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);
for (k=1; k<=7; k++)
document.write(KSmallestUsingMorris(root, k) + " ");
// This code contributed by Rajput-Ji
</script>
Producción
20 30 40 50 60 70 80
Complejidad de tiempo : O(n) donde n es el tamaño de BST
Espacio auxiliar: O(1)
Este artículo es una contribución de Abhishek Somani. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA