wake-up-neo.com

Finden Sie das k-kleinste Element in einem binären Suchbaum auf optimale Weise

Ich muss das kleinste k-te Element im binären Suchbaum finden, ohne statische/globale Variablen zu verwenden. Wie kann man das effizient erreichen? Die Lösung, die ich im Kopf habe, ist die Operation in O (n). Aber tief im Innern habe ich das Gefühl, dass ich die BST-Eigenschaft hier nicht benutze. Ist meine angenommene Lösung richtig oder gibt es eine bessere Lösung?

105
bragboy

Hier nur ein Überblick über die Idee:

In einer BST enthält der linke Teilbaum des Knotens T nur Elemente, die kleiner als der in T gespeicherte Wert sind. Wenn k kleiner als die Anzahl der Elemente im linken Teilbaum ist, muss das kleinste k-Element zum linken Teilbaum gehören. Wenn k größer ist, befindet sich das kleinste Element k im rechten Teilbaum.

Wir können die BST so erweitern, dass jeder Knoten die Anzahl der Elemente in seinem linken Teilbaum speichert (vorausgesetzt, der linke Teilbaum eines bestimmten Knotens enthält diesen Knoten). Mit dieser Information ist es einfach, den Baum zu durchqueren, indem Sie wiederholt nach der Anzahl der Elemente im linken Teilbaum fragen, um zu entscheiden, ob Sie in den linken oder rechten Teilbaum wechseln möchten.

Nehmen wir an, wir sind am Knoten T:

  1. Wenn k == num_elements (linker Teilbaum von T) , dann ist die Antwort, nach der wir suchen, der Wert im Knoten T.
  2. Wenn k> num_elements (linker Teilbaum von T) , dann können wir natürlich den linken Teilbaum ignorieren, da diese Elemente auch kleiner als die kleinste kth sein werden. Daher reduzieren wir das Problem auf das k - num_elements(left subtree of T) kleinste Element des rechten Teilbaums. 
  3. Wenn k <num_elements (linker Teilbaum von T) ist, befindet sich die kleinste Variable kth irgendwo im linken Teilbaum. Daher reduzieren wir das Problem, indem das kleinste k-Element im linken Teilbaum gefunden wird.

Komplexitätsanalyse:

Dies dauert O(depth of node) Zeit, was O(log n) im schlimmsten Fall bei einer ausgeglichenen BST oder O(log n) im Durchschnitt für eine zufällige BST ist.

Ein BST benötigt O(n)-Speicher und es dauert ein weiteres O(n), um die Informationen zur Anzahl der Elemente zu speichern. Alle BST-Vorgänge benötigen O(depth of node)-Zeit, und O(depth of node) benötigt zusätzliche Zeit, um die "Elementanzahl" -Information für das Einfügen, Löschen oder Drehen von Knoten beizubehalten. Das Speichern von Informationen über die Anzahl der Elemente im linken Teilbaum bewahrt daher die räumliche und zeitliche Komplexität einer BST.

164
IVlad

Eine einfachere Lösung wäre, einen Inorder-Durchlauf durchzuführen und das aktuell zu druckende Element zu verfolgen (ohne es zu drucken). Wenn wir k erreicht haben, drucken Sie das Element aus und überspringen den Rest der Baumdurchquerung.

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); 
}
65
prasadvk
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;
    }

dies ist meine Implementierung in C # basierend auf dem obigen Algorithmus. Ich dachte, ich würde es posten, damit die Leute es besser verstehen können

danke IVlad

13
Para

Eine einfachere Lösung wäre, einen Inorder-Durchlauf durchzuführen und das Element, das aktuell mit einem Zähler k gedruckt werden soll, zu verfolgen. Wenn wir k erreicht haben, drucken Sie das Element. Die Laufzeit ist O (n). Denken Sie daran, dass der Rückgabetyp der Funktion nicht ungültig sein kann. Er muss nach jedem rekursiven Aufruf den aktualisierten Wert von k zurückgeben. Eine bessere Lösung wäre eine erweiterte BST mit einem sortierten Positionswert an jedem Knoten.

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;
}
11
Sumit Balani

// Eine Java-Version ohne Rekursion hinzufügen

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();
        }
    }
}
10
Jiaji Li

Sie können iteratives Inorder-Traversal verwenden: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal Mit einer einfachen Prüfung auf kth-Element, nachdem Sie einen Knoten aus dem Stack gezogen haben.

7
Binh Nguyen

Rekursiv In-Order Gehen Sie mit einem Zähler

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

Die Idee ähnelt der @ prasadvk-Lösung, weist jedoch einige Mängel auf (siehe Anmerkungen unten). Deshalb poste ich dies als separate Antwort.

// 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 );
}

Anmerkungen (und Unterschiede zur @ prasadvk-Lösung):

  1. if( counter == k ) test ist an drei Stellen erforderlich: (a) nach linkem Teilbaum, (b) nach Wurzel und (c) nach rechtem Teilbaum. Hierbei handelt es sich um sicherstellen, dass das k-te Element für alle Positionen erkannt wird, d. H. Unabhängig von dem Unterbaum, in dem es sich befindet.

  2. if( result == -1 ) test ist erforderlich, um sicherzustellen, dass nur das Ergebniselement wird gedruckt, andernfalls werden alle Elemente gedruckt, die vom kleinsten k-ten Wert bis zum Stamm reichen.

4
Arun

Wenn Sie nur einen einfachen binären Suchbaum verwenden, können Sie nur vom kleinsten aus beginnen und nach oben gehen, um den richtigen Knoten zu finden.

Wenn Sie dies sehr häufig tun, können Sie jedem Knoten ein Attribut hinzufügen, das angibt, wie viele Knoten sich in seinem linken Teilbaum befinden. Auf diese Weise können Sie den Baum direkt zum richtigen Knoten absteigen.

4
Jerry Coffin

Für nicht einen ausgeglichenen Suchbaum braucht man O (n) .

Für den ausgeglichenen Suchbaum braucht man O (k + log n) im schlimmsten Fall aber nur O (k) in Amortized Sinn.

Zusätzliche Ganzzahl für jeden Knoten haben und verwalten: Die Größe des Unterbaums gibt O (log n) Zeitkomplexität. Ein solcher ausgeglichener Suchbaum wird üblicherweise RankTree genannt.

Im Allgemeinen gibt es Lösungen (basierend nicht auf Baum).

Grüße.

3
Slava

Obwohl dies definitiv nicht die optimale Lösung für das Problem ist, ist es eine andere potenzielle Lösung, von der ich dachte, dass einige Leute interessant sein könnten:

/**
 * 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 );
}
1

Nun, hier sind meine 2 Cent ...

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;
 }
1
Manish Shukla

unterschrift:

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

anrufen als:

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

definition:

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;
}
1
Aim

Das funktioniert gut: status: ist das Array, das enthält, ob ein Element gefunden wird. k: ist das zu findende k-te Element. count: verfolgt die Anzahl der Knoten, die während der Baumdurchquerung durchlaufen wurden.

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;
}
1
pranjal

Ich denke, das ist besser als die akzeptierte Antwort, da der ursprüngliche Baumknoten nicht geändert werden muss, um die Anzahl seiner untergeordneten Knoten zu speichern.

Wir müssen nur die Durchlaufreihenfolge in der Reihenfolge verwenden, um den kleinsten Knoten von links nach rechts zu zählen und die Suche zu beenden, sobald die Anzahl gleich K ist.

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);
}
0
jinshui

Der Linux-Kernel verfügt über eine hervorragende erweiterte rot-schwarze Baumdatenstruktur, die rangebasierte Operationen in O (log n) in linux/lib/rbtree.c unterstützt.

Einen sehr groben Java-Port finden Sie auch unter http://code.google.com/p/refolding/source/browse/trunk/core/src/main/Java/it/unibo/refolding/alg/RbTree. Java , zusammen mit RbRoot.Java und RbNode.Java. Das n-te Element kann durch Aufrufen von RbNode.nth (RbNode-Knoten, int n) erhalten werden, wobei die Wurzel des Baums übergeben wird.

0
Daniel

Nun, wir können einfach die in order-Reihenfolge verwenden und das besuchte Element auf einen Stack legen. _. Pop k-mal, um die Antwort zu erhalten.

wir können auch nach k Elementen aufhören

0
kartheek babu

Verwenden der Hilfsergebnisklasse zum Verfolgen, ob der Knoten gefunden wurde und der aktuelle Wert k ist.

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;
    }
}
}
0
Alex Fedulov

das würde auch funktionieren. Rufen Sie einfach die Funktion mit maxNode im Baum auf

def k_largest (self, node, k): wenn k <0: return Keine
wenn k == 0: Rückkehrknoten sonst: k - = 1 return self.k_largest (self.predecessor (Knoten), k)

0
user2229805

IVlad-Lösung mit einem order statistics tree ist die effizienteste. Wenn Sie jedoch keinen order statistics tree verwenden können und mit einer regulären alten BST verbunden sind, ist der beste Ansatz ein In-Order-Traversal (wie von prasadvk ausgeführt). Seine Lösung ist jedoch unzureichend, wenn Sie das k-kleinste Element zurückgeben und den Wert nicht einfach ausdrucken möchten. Da seine Lösung rekursiv ist, besteht die Gefahr eines Stapelüberlaufs. Daher habe ich eine Java-Lösung geschrieben, die den k-kleinsten Knoten zurückgibt und einen Stapel für das In-Order-Traversal verwendet. Die Laufzeit ist O(n), während die Raumkomplexität O(h) ist, wobei h die maximale Höhe des Baums ist.

// 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;
}
0
Haider

Hier ist eine prägnante Version in C # that gibt das k-te kleinste Element zurück, erfordert jedoch die Übergabe von k als ref-Argument (es ist dieselbe Vorgehensweise wie bei @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 ist O (log n), um den kleinsten Knoten zu finden, und dann O(k), um zum k-ten Knoten zu gelangen, also ist es O (k + log n).

0
Erhhung

Hier ist der Java-Code,

max (Knotenwurzel, int k) - um k-te größte zu finden

min (Knotenwurzel, int k) - um kth kleinste zu finden

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);
}
0
code_2_peep
 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    } 

Dieser rekursive Java-Algorithmus stoppt die Rekursion, sobald das kleinste k-te Element gefunden wird. 

0

Der beste Ansatz ist bereits da. Aber ich möchte einen einfachen Code dafür hinzufügen

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 );
}}
0

Ich konnte keinen besseren Algorithmus finden. Also entschied ich mich, einen zu schreiben:) Korrigieren Sie mich, wenn dies falsch ist.

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));
}

}

0
laxman

Lösung für kompletten BST-Fall: -

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;
}
0
gvijay

http://www.geeksforgeeks.org/archives/10379

dies ist die genaue Antwort auf diese Frage: -

1.Verwenden des Inorder-Durchlaufs zum Zeitpunkt O(n) 2. Verwenden des erweiterten Baums in k + logn-Zeit

0
Shivendra

Das habe ich gedacht und es funktioniert. Es läuft in 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
0
Learner