usos qué programa ordenamiento khan iterativa grafos búsqueda busqueda binaria academy algorithm data-structures binary-tree binary-search

algorithm - qué - Encuentra el k-ésimo elemento más pequeño en un árbol de búsqueda binaria de manera óptima



usos de la busqueda binaria (30)

Necesito encontrar el k-ésimo elemento más pequeño en el árbol de búsqueda binario sin usar ninguna variable estática / global. ¿Cómo lograrlo de manera eficiente? La solución que tengo en mente es hacer la operación en O (n), el peor de los casos, ya que estoy planeando hacer un recorrido inorden de todo el árbol. Pero en el fondo siento que no estoy usando la propiedad BST aquí. ¿Es correcta mi solución supuesta o hay una mejor disponible?

Paseo recursivo en orden con un contador

Time Complexity: O( N ), N is the number of nodes Space Complexity: O( 1 ), excluding the function call stack

La idea es similar a la solución @prasadvk, pero tiene algunas deficiencias (véanse las notas a continuación), así que estoy publicando esto como una respuesta separada.

// Private Helper Macro #define testAndReturn( k, counter, result ) / do { if( (counter == k) && (result == -1) ) { / result = pn->key_; / return; / } } while( 0 ) // Private Helper Function static void findKthSmallest( BstNode const * pn, int const k, int & counter, int & result ) { if( ! pn ) return; findKthSmallest( pn->left_, k, counter, result ); testAndReturn( k, counter, result ); counter += 1; testAndReturn( k, counter, result ); findKthSmallest( pn->right_, k, counter, result ); testAndReturn( k, counter, result ); } // Public API function void findKthSmallest( Bst const * pt, int const k ) { int counter = 0; int result = -1; // -1 := not found findKthSmallest( pt->root_, k, counter, result ); printf("%d-th element: element = %d/n", k, result ); }

Notas (y diferencias de la solución de @ prasadvk):

  1. if( counter == k ) se requiere la prueba if( counter == k ) en tres lugares: (a) después del subárbol izquierdo, (b) después de la raíz y (c) después del subárbol derecho. Esto es para asegurar que k-elemento se detecta para todas las ubicaciones , es decir, independientemente del subárbol que se encuentra.

  2. if( result == -1 ) prueba requerida para asegurar que solo se imprima el elemento resultante , de lo contrario se imprimen todos los elementos comenzando desde el kth más pequeño hasta el raíz.

// agrega una versión java sin recursión

public static <T> void find(TreeNode<T> node, int num){ Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>(); TreeNode<T> current = node; int tmp = num; while(stack.size() > 0 || current!=null){ if(current!= null){ stack.add(current); current = current.getLeft(); }else{ current = stack.pop(); tmp--; if(tmp == 0){ System.out.println(current.getValue()); return; } current = current.getRight(); } } }

Aquí está el código de Java,

max (raíz del nodo, int k) - para encontrar el kth más grande

min (Node root, int k) - para encontrar kth Smallest

static int count(Node root){ if(root == null) return 0; else return count(root.left) + count(root.right) +1; } static int max(Node root, int k) { if(root == null) return -1; int right= count(root.right); if(k == right+1) return root.data; else if(right < k) return max(root.left, k-right-1); else return max(root.right, k); } static int min(Node root, int k) { if (root==null) return -1; int left= count(root.left); if(k == left+1) return root.data; else if (left < k) return min(root.right, k-left-1); else return min(root.left, k); }

Aquí hay solo un resumen de la idea:

En una BST, el subárbol izquierdo del nodo T contiene solo elementos menores que el valor almacenado en T Si k es más pequeño que el número de elementos en el subárbol izquierdo, el k ésimo elemento más pequeño debe pertenecer al subárbol izquierdo. De lo contrario, si k es más grande, entonces el k ésimo elemento más pequeño está en el subárbol derecho.

Podemos aumentar el BST para que cada nodo en él almacene la cantidad de elementos en su subárbol izquierdo (suponiendo que el subárbol izquierdo de un nodo dado incluye ese nodo). Con esta información, es simple atravesar el árbol al pedir repetidamente la cantidad de elementos en el subárbol izquierdo, para decidir si hacer recurse en el subárbol izquierdo o derecho.

Ahora, supongamos que estamos en el nodo T:

  1. Si k == elementos num (subárbol izquierdo de T) , entonces la respuesta que estamos buscando es el valor en el nodo T
  2. Si k> num_elements (subárbol izquierdo de T) , entonces obviamente podemos ignorar el subárbol izquierdo, porque esos elementos también serán más pequeños que el k ésimo. Entonces, reducimos el problema para encontrar el elemento k - num_elements(left subtree of T) elemento más pequeño del subárbol derecho.
  3. Si k <num_elements (subárbol izquierdo de T) , entonces el k ésimo más pequeño está en alguna parte en el subárbol izquierdo, por lo que reducimos el problema para encontrar el k ésimo elemento más pequeño en el subárbol izquierdo.

Análisis de Complejidad

Esto toma el tiempo O(depth of node) , que es O(log n) en el peor de los casos en una BST balanceada, u O(log n) en promedio para una BST aleatoria.

Una BST requiere O(n) almacenamiento, y se necesita otra O(n) para almacenar la información sobre la cantidad de elementos. Todas las operaciones BST toman el tiempo O(depth of node) y toma O(depth of node) tiempo extra para mantener la información del "número de elementos" para la inserción, eliminación o rotación de nodos. Por lo tanto, almacenar información sobre el número de elementos en el subárbol izquierdo mantiene la complejidad de espacio y tiempo de una BST.

Aquí hay una versión concisa en C # que devuelve el k-ésimo elemento más pequeño, pero requiere pasar k en como argumento de ref (es el mismo enfoque que @prasadvk):

Node FindSmall(Node root, ref int k) { if (root == null || k < 1) return null; Node node = FindSmall(root.LeftChild, ref k); if (node != null) return node; if (--k == 0) return node ?? root; return FindSmall(root.RightChild, ref k); }

Es O (log n) para encontrar el nodo más pequeño, y luego O (k) para atravesar k-ésimo nodo, por lo que es O (k + log n).

Bueno, aquí está mi 2 centavos ...

int numBSTnodes(const Node* pNode){ if(pNode == NULL) return 0; return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1); } //This function will find Kth smallest element Node* findKthSmallestBSTelement(Node* root, int k){ Node* pTrav = root; while(k > 0){ int numNodes = numBSTnodes(pTrav->left); if(numNodes >= k){ pTrav = pTrav->left; } else{ //subtract left tree nodes and root count from ''k'' k -= (numBSTnodes(pTrav->left) + 1); if(k == 0) return pTrav; pTrav = pTrav->right; } return NULL; }

Bueno, podemos simplemente usar el recorrido en orden y empujar el elemento visitado a una pila. pop k número de veces, para obtener la respuesta.

también podemos parar después de k elementos

Creo que esto es mejor que la respuesta aceptada porque no necesita modificar el nodo del árbol original para almacenar el número de nodos secundarios.

Solo necesitamos usar el recorrido en orden para contar el nodo más pequeño de izquierda a derecha, detener la búsqueda una vez que el conteo sea igual a K.

private static int count = 0; public static void printKthSmallestNode(Node node, int k){ if(node == null){ return; } if( node.getLeftNode() != null ){ printKthSmallestNode(node.getLeftNode(), k); } count ++ ; if(count <= k ) System.out.println(node.getValue() + ", count=" + count + ", k=" + k); if(count < k && node.getRightNode() != null) printKthSmallestNode(node.getRightNode(), k); }

Dado solo un árbol de búsqueda binaria simple, todo lo que puede hacer es comenzar desde el más pequeño y recorrer hacia arriba para encontrar el nodo correcto.

Si vas a hacer esto muy a menudo, puedes agregar un atributo a cada nodo que signifique cuántos nodos hay en su subárbol izquierdo. Usando eso, puede descender el árbol directamente al nodo correcto.

El mejor enfoque ya está disponible. Pero me gustaría agregar un código simple para ese

int kthsmallest(treenode *q,int k){ int n = size(q->left) + 1; if(n==k){ return q->val; } if(n > k){ return kthsmallest(q->left,k); } if(n < k){ return kthsmallest(q->right,k - n); }

}

int size(treenode *q){ if(q==NULL){ return 0; } else{ return ( size(q->left) + size(q->right) + 1 ); }}

Escribí una función ordenada para calcular el k-ésimo elemento más pequeño. Utilizo un recorrido en orden y me detengo cuando alcanza el k-ésimo elemento más pequeño.

void btree::kthSmallest(node* temp, int& k){ if( temp!= NULL) { kthSmallest(temp->left,k); if(k >0) { if(k==1) { cout<<temp->value<<endl; return; } k--; } kthSmallest(temp->right,k); }}

Esto es lo que pensé y funciona. Se ejecutará en o (log n)

public static int FindkThSmallestElemet(Node root, int k) { int count = 0; Node current = root; while (current != null) { count++; current = current.left; } current = root; while (current != null) { if (count == k) return current.data; else { current = current.left; count--; } } return -1; } // end of function FindkThSmallestElemet

Esto funciona bien: estado: es la matriz que contiene si se encuentra un elemento. k: es el k-ésimo elemento que se encuentra. recuento: realiza un seguimiento del número de nodos atravesados ​​durante el recorrido del árbol.

int kth(struct tree* node, int* status, int k, int count) { if (!node) return count; count = kth(node->lft, status, k, count); if( status[1] ) return status[0]; if (count == k) { status[0] = node->val; status[1] = 1; return status[0]; } count = kth(node->rgt, status, k, count+1); if( status[1] ) return status[0]; return count; }

La solución IVlad utilizando un order statistics tree es la más eficiente. Pero si no puede usar un order statistics tree y está atascado con una BST antigua normal, entonces el mejor enfoque es hacer un cruce de órdenes (como lo señala prasadvk). Pero su solución es inadecuada si desea devolver el elemento más pequeño y no simplemente imprimir el valor. Además, dado que su solución es recursiva, existe el peligro de que se desborde la pila. Por lo tanto, escribí una solución java que devuelve el k-ésimo nodo más pequeño y usa una pila para hacer el cruce en orden. El tiempo de ejecución es O (n) mientras que la complejidad del espacio es O (h) donde h es la altura máxima del árbol.

// The 0th element is defined to be the smallest element in the tree. public Node find_kth_element(Node root , int k) { if (root == null || k < 0) return null; Deque<Node> stack = new ArrayDeque<Node>(); stack.push(root); while (!stack.isEmpty()) { Node curr = stack.peek(); if (curr.left != null) { stack.push(curr.left); continue; } if (k == 0) return curr; stack.pop(); --k; if (curr.right != null) { stack.push(curr.right); } } return null; }

No pude encontrar un algoritmo mejor ... así que decidí escribir uno :) Corrígeme si esto está mal.

class KthLargestBST{ protected static int findKthSmallest(BSTNode root,int k){//user calls this function int [] result=findKthSmallest(root,k,0);//I call another function inside return result[1]; } private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position. if(root==null){ int[] i=new int[2]; i[0]=-1; i[1]=-1; return i; }else{ int rval[]=new int[2]; int temp[]=new int[2]; rval=findKthSmallest(root.leftChild,k,count); if(rval[0]!=-1){ count=rval[0]; } count++; if(count==k){ rval[1]=root.data; } temp=findKthSmallest(root.rightChild,k,(count)); if(temp[0]!=-1){ count=temp[0]; } if(temp[1]!=-1){ rval[1]=temp[1]; } rval[0]=count; return rval; } } public static void main(String args[]){ BinarySearchTree bst=new BinarySearchTree(); bst.insert(6); bst.insert(8); bst.insert(7); bst.insert(4); bst.insert(3); bst.insert(4); bst.insert(1); bst.insert(12); bst.insert(18); bst.insert(15); bst.insert(16); bst.inOrderTraversal(); System.out.println(); System.out.println(findKthSmallest(bst.root,11)); }

}

Para árbol de búsqueda no equilibrado, toma O (n) .

Para el árbol de búsqueda equilibrado , toma O (k + log n) en el peor de los casos, pero solo O (k) en el sentido Amortizado .

Tener y administrar el entero extra para cada nodo: el tamaño del subárbol le da a O (log n) complejidad de tiempo. Tal árbol de búsqueda equilibrado generalmente se llama RankTree.

En general, hay soluciones (basadas no en el árbol).

Saludos.

Si bien esta no es definitivamente la solución óptima para el problema, es otra posible solución que pensé que algunas personas podrían encontrar interesante:

/** * Treat the bst as a sorted list in descending order and find the element * in position k. * * Time complexity BigO ( n^2 ) * * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4 * * @param t The root of the binary search tree. * @param k The position of the element to find. * @return The value of the element at position k. */ public static int kElement2( Node t, int k ) { int treeSize = sizeOfTree( t ); return kElement2( t, k, treeSize, 0 ).intValue(); } /** * Find the value at position k in the bst by doing an in-order traversal * of the tree and mapping the ascending order index to the descending order * index. * * * @param t Root of the bst to search in. * @param k Index of the element being searched for. * @param treeSize Size of the entire bst. * @param count The number of node already visited. * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if * not found in this sub-tree. */ private static Double kElement2( Node t, int k, int treeSize, int count ) { // Double.POSITIVE_INFINITY is a marker value indicating that the kth // element wasn''t found in this sub-tree. if ( t == null ) return Double.POSITIVE_INFINITY; Double kea = kElement2( t.getLeftSon(), k, treeSize, count ); if ( kea != Double.POSITIVE_INFINITY ) return kea; // The index of the current node. count += 1 + sizeOfTree( t.getLeftSon() ); // Given any index from the ascending in order traversal of the bst, // treeSize + 1 - index gives the // corresponding index in the descending order list. if ( ( treeSize + 1 - count ) == k ) return (double)t.getNumber(); return kElement2( t.getRightSon(), k, treeSize, count ); }

Solución para el caso BST completo: -

Node kSmallest(Node root, int k) { int i = root.size(); // 2^height - 1, single node is height = 1; Node result = root; while (i - 1 > k) { i = (i-1)/2; // size of left subtree if (k < i) { result = result.left; } else { result = result.right; k -= i; } } return i-1==k ? result: null; }

Una solución más simple sería hacer un recorrido inorden y realizar un seguimiento del elemento que se imprimirá en ese momento (sin imprimirlo). Cuando alcanzamos k, imprime el elemento y salta el resto del recorrido del árbol.

void findK(Node* p, int* k) { if(!p || k < 0) return; findK(p->left, k); --k; if(k == 0) { print p->data; return; } findK(p->right, k); }

Una solución más simple sería hacer un recorrido inorden y realizar un seguimiento del elemento que se imprimirá en ese momento con un contador k. Cuando alcanzamos k, imprime el elemento. El tiempo de ejecución es O (n). Recuerde que el tipo de devolución de función no puede ser nulo, debe devolver su valor actualizado de k después de cada llamada recursiva. Una mejor solución para esto sería una BST aumentada con un valor de posición ordenada en cada nodo.

public static int kthSmallest (Node pivot, int k){ if(pivot == null ) return k; k = kthSmallest(pivot.left, k); k--; if(k == 0){ System.out.println(pivot.value); } k = kthSmallest(pivot.right, k); return k; }

Usar la clase auxiliar de resultados para rastrear si se encuentra un nodo y k actual.

public class KthSmallestElementWithAux { public int kthsmallest(TreeNode a, int k) { TreeNode ans = kthsmallestRec(a, k).node; if (ans != null) { return ans.val; } else { return -1; } } private Result kthsmallestRec(TreeNode a, int k) { //Leaf node, do nothing and return if (a == null) { return new Result(k, null); } //Search left first Result leftSearch = kthsmallestRec(a.left, k); //We are done, no need to check right. if (leftSearch.node != null) { return leftSearch; } //Consider number of nodes found to the left k = leftSearch.k; //Check if current root is the solution before going right k--; if (k == 0) { return new Result(k - 1, a); } //Check right Result rightBalanced = kthsmallestRec(a.right, k); //Consider all nodes found to the right k = rightBalanced.k; if (rightBalanced.node != null) { return rightBalanced; } //No node found, recursion will continue at the higher level return new Result(k, null); } private class Result { private final int k; private final TreeNode node; Result(int max, TreeNode node) { this.k = max; this.node = node; } } }

esto funcionaría también simplemente llame a la función con maxNode en el árbol

def k_largest (self, node, k): si k <0: return None
si k == 0: return node else: k - = 1 return self.k_largest (self.predecessor (node), k)

firma:

Node * find(Node* tree, int *n, int k);

llamar como:

*n = 0; kthNode = find(root, n, k);

definición:

Node * find ( Node * tree, int *n, int k) { Node *temp = NULL; if (tree->left && *n<k) temp = find(tree->left, n, k); *n++; if(*n==k) temp = root; if (tree->right && *n<k) temp = find(tree->right, n, k); return temp; }

int RecPrintKSmallest(Node_ptr head,int k){ if(head!=NULL){ k=RecPrintKSmallest(head->left,k); if(k>0){ printf("%c ",head->Node_key.key); k--; } k=RecPrintKSmallest(head->right,k); } return k; }

public TreeNode findKthElement(TreeNode root, int k){ if((k==numberElement(root.left)+1)){ return root; } else if(k>numberElement(root.left)+1){ findKthElement(root.right,k-numberElement(root.left)-1); } else{ findKthElement(root.left, k); } } public int numberElement(TreeNode node){ if(node==null){ return 0; } else{ return numberElement(node.left) + numberElement(node.right) + 1; } }

public int ReturnKthSmallestElement1(int k) { Node node = Root; int count = k; int sizeOfLeftSubtree = 0; while(node != null) { sizeOfLeftSubtree = node.SizeOfLeftSubtree(); if (sizeOfLeftSubtree + 1 == count) return node.Value; else if (sizeOfLeftSubtree < count) { node = node.Right; count -= sizeOfLeftSubtree+1; } else { node = node.Left; } } return -1; }

esta es mi implementación en C # basada en el algoritmo anterior, solo pensé en publicarla para que la gente pueda entender mejor, me funciona

gracias IVlad

public static Node kth(Node n, int k){ Stack<Node> s=new Stack<Node>(); int countPopped=0; while(!s.isEmpty()||n!=null){ if(n!=null){ s.push(n); n=n.left; }else{ node=s.pop(); countPopped++; if(countPopped==k){ return node; } node=node.right; } }

}