Temukan elemen terkecil ke-k dalam pohon pencarian biner dengan cara Optimum

Saya perlu menemukan elemen terkecil ke-k di pohon pencarian biner tanpa menggunakan variabel statis / global. Bagaimana cara mencapainya secara efisien? Solusi yang ada dalam pikiran saya adalah melakukan operasi di O (n), kasus terburuk karena saya berencana untuk melakukan penelusuran inorder seluruh pohon. Tetapi jauh di lubuk hati saya merasa bahwa saya tidak menggunakan properti BST di sini. Apakah solusi asumsi saya benar atau ada solusi yang lebih baik yang tersedia?

Inilah garis besar idenya:

Dalam BST, subpohon kiri dari node Thanya berisi elemen yang lebih kecil dari nilai yang disimpan T. Jika klebih kecil dari jumlah elemen di subtree kiri, kelemen terkecil harus dimiliki subtree kiri. Sebaliknya, jika klebih besar, maka filek elemen terkecil ada di subtree kanan.

Kita dapat menambah BST agar setiap node di dalamnya menyimpan jumlah elemen di subtree kirinya (asumsikan bahwa subtree kiri dari node tertentu menyertakan node tersebut). Dengan informasi ini, mudah untuk melintasi pohon dengan berulang kali menanyakan jumlah elemen di subtree kiri, untuk memutuskan apakah akan melakukan perulangan ke subtree kiri atau kanan.

Sekarang, misalkan kita berada di simpul T:

1. Jika k == num_elements (subpohon kiri T) , maka jawaban yang kita cari adalah nilai pada node T.
2. Jika k> num_elements (subtree kiri dari T) , maka jelas kita bisa mengabaikan subtree kiri, karena elemen tersebut juga akan lebih kecil dari yang kterkecil. Jadi, kami mengurangi masalah untuk menemukan k - num_elements(left subtree of T)elemen terkecil dari subpohon kanan.
3. Jika k <num_elements (subpohon kiri dari T) , maka yang kterkecil ada di suatu tempat di subpohon kiri, jadi kita mengurangi masalahnya untuk mencari kelemen terkecil di subpohon kiri.

Analisis kompleksitas:

Ini membutuhkan O(depth of node)waktu, yang O(log n)dalam kasus terburuk pada BST seimbang, atau O(log n)rata-rata untuk BST acak.

BST membutuhkan O(n)penyimpanan, dan BST membutuhkan penyimpanan lain O(n)untuk menyimpan informasi tentang jumlah elemen. Semua operasi BST membutuhkan O(depth of node)waktu, dan perlu waktu O(depth of node)ekstra untuk mempertahankan informasi "jumlah elemen" untuk penyisipan, penghapusan, atau rotasi node. Oleh karena itu, menyimpan informasi tentang jumlah elemen di subpohon kiri menjaga kompleksitas ruang dan waktu dari BST.

Solusi yang lebih sederhana adalah melakukan penelusuran inorder dan melacak elemen yang saat ini akan dicetak (tanpa mencetaknya). Saat kita mencapai k, cetak elemen dan lewati traversal pohon lainnya.

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

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

ini adalah implementasi saya di C # berdasarkan algoritma di atas, saya pikir saya akan mempostingnya sehingga orang-orang dapat lebih memahami cara kerjanya untuk saya

terima kasih IVlad

Solusi yang lebih sederhana adalah melakukan penelusuran inorder dan melacak elemen yang saat ini akan dicetak dengan penghitung k. Saat kita mencapai k, cetak elemennya. Runtime adalah O (n). Ingat jenis fungsi yang dikembalikan tidak boleh kosong, ia harus mengembalikan nilai k yang diperbarui setelah setiap panggilan rekursif. Solusi yang lebih baik untuk ini adalah augmented BST dengan nilai posisi yang diurutkan di setiap node.

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

// tambahkan versi java tanpa rekursi

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

Anda dapat menggunakan traversal inorder iteratif: http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal dengan pemeriksaan sederhana untuk elemen k setelah mengeluarkan node dari tumpukan.

Diberikan hanya pohon pencarian biner biasa, hampir semua yang dapat Anda lakukan adalah mulai dari yang terkecil, dan melintasi ke atas untuk menemukan node yang tepat.

Jika Anda akan sering melakukan ini, Anda dapat menambahkan atribut ke setiap node yang menandakan berapa banyak node di sub-pohon kirinya. Dengan menggunakan itu, Anda dapat menurunkan pohon langsung ke simpul yang benar.

Rekursif In-order Walk dengan penghitung

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

Idenya mirip dengan solusi @prasadvk, tetapi memiliki beberapa kekurangan (lihat catatan di bawah), jadi saya memposting ini sebagai jawaban terpisah.

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

Catatan (dan perbedaan dari solusi @ prasadvk):

1. if( counter == k )tes diperlukan di tiga tempat: (a) setelah subpohon kiri, (b) setelah akar, dan (c) setelah subpohon kanan. Ini untuk memastikan bahwa elemen k terdeteksi untuk semua lokasi , yaitu terlepas dari subpohon tempatnya berada.

2. if( result == -1 )tes diperlukan untuk memastikan hanya elemen hasil yang dicetak , jika tidak semua elemen mulai dari k terkecil hingga akar yang dicetak.

Untuk pohon pencarian yang tidak seimbang, dibutuhkan O (n) .

Untuk pohon pencarian yang seimbang , dibutuhkan O (k + log n) dalam kasus terburuk tetapi hanya O (k) dalam pengertian Amortisasi .

Memiliki dan mengelola integer ekstra untuk setiap node: ukuran sub-pohon memberikan kompleksitas waktu O (log n) . Pohon pencarian yang seimbang seperti itu biasanya disebut RankTree.

Secara umum, ada solusi (tidak berdasarkan pohon).

Salam.

Ini bekerja dengan baik: status: adalah larik yang menampung apakah elemen ditemukan. k: adalah elemen k yang akan ditemukan. count: melacak jumlah node yang dilintasi selama traversal pohon.

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

Meskipun ini jelas bukan solusi optimal untuk masalah ini, ini adalah solusi potensial lain yang menurut saya menarik bagi beberapa orang:

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

tanda tangan:

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

panggil sebagai:

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

definisi:

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

Nah ini 2 sen saya ...

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

Inilah yang saya pikirkan dan berhasil. Ini akan berjalan di 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

Kita cukup menggunakan in order traversal dan mendorong elemen yang dikunjungi ke tumpukan. pop k beberapa kali, untuk mendapatkan jawabannya.

kita juga bisa berhenti setelah elemen k

Solusi untuk kasus BST lengkap: -

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

Kernel Linux memiliki struktur data pohon merah-hitam augmented yang sangat baik yang mendukung operasi berbasis peringkat di O (log n) di linux / lib / rbtree.c.

Porta Java yang sangat kasar juga dapat ditemukan di http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java , bersama dengan RbRoot.java dan RbNode.java. Elemen ke-n dapat diperoleh dengan memanggil RbNode.nth (RbNode node, int n), meneruskan root pohon.

Berikut adalah versi ringkas di C # yang mengembalikan elemen terkecil ke-k, tetapi perlu meneruskan k sebagai argumen ref (pendekatannya sama dengan @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);
}

Itu O (log n) untuk menemukan yang simpul terkecil, dan kemudian O (k) untuk melintasi k-th node, sehingga O itu (k + log n).

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

ini adalah jawaban yang tepat untuk pertanyaan ini: -

1. menggunakan inorder traversal pada waktu O (n) 2. menggunakan pohon Augmented dalam waktu k + log n

Saya tidak bisa menemukan algoritma yang lebih baik..jadi memutuskan untuk menulis satu :) Koreksi saya jika ini salah.

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

}

Ini kode java-nya,

max (Node root, int k) - untuk mencari k terbesar

min (Node root, int k) - untuk mencari 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);
}

ini akan berhasil juga. panggil saja fungsi dengan maxNode di pohon

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

Saya pikir ini lebih baik daripada jawaban yang diterima karena tidak perlu memodifikasi simpul pohon asli untuk menyimpan jumlah simpul anak-anaknya.

Kita hanya perlu menggunakan in-order traversal untuk menghitung simpul terkecil dari kiri ke kanan, berhenti mencari setelah hitungannya sama dengan 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);
}

Pendekatan terbaik sudah ada. Tapi saya ingin menambahkan Kode sederhana untuk itu

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

Menggunakan kelas Hasil tambahan untuk melacak jika node ditemukan dan k saat ini.

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

Solusi Python Kompleksitas Waktu: O (n) Kompleksitas Ruang: O (1)

Ide adalah menggunakan Morris Inorder Traversal

class Solution(object):
def inorderTraversal(self, current , k ):
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                k -= 1
                if(k == 0):
                    return current.val
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R 
            k -= 1
            if(k == 0):
                return current.val
            current = current.right

    return 0

def kthSmallest(self, root, k):
    return self.inorderTraversal( root , k  )

saya menulis fungsi rapi untuk menghitung elemen terkecil ke-k. Saya menggunakan in-order traversal dan berhenti ketika mencapai elemen terkecil ke-k.

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

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

      }
  }

}