BST-də Kth Kiçik Element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Facebook google Kahin
İkili Axtarış Ağacı İkili ağac AğacBaxılıb 19

Bu problemdə bir BST və bir k verdik, bir BST-də ən kiçik elementi tapın.

Nümunələr

Input
ağac [] = {5, 3, 6, 2, 4, null, null, 1}
k = 3

BST-də Kth Kiçik ElementPin
Buraxılış
3

Input
ağac [] = {3, 1, 4, boş, 2}
k = 1

BST-də Kth Kiçik ElementPin
Buraxılış
1

BST-də Kth Kiçik Elementi tapmaq üçün sadəlövh yanaşma

Sınırsız olun xain BST-nin və an array və massivin k elementini qaytarın. BST-nin inorder keçidi sıralanmış bir sıra ilə nəticələndiyinə görə, inorder traversal-dakı kth elementi ən kiçik elementdir.

  1. BST-nin sərhəd keçidini saxlayan tam ədədlərin siyahısını yaradın.
  2. Sərhəd keçidini edin
  3. Kök null deyilsə, sol uşaq üçün qeyri-qanuni keçiş edin.
  4. Cari düyünün məlumatlarını siyahıya daxil edin.
  5. Müvafiq uşaq üçün qeyri-qanuni hərəkət etmək.
  6. Sonda siyahıda k mövqeyində olan elementi qaytarın.

JAVA Kodu

import java.util.ArrayList;

public class KthSmallestInBST {
    // Class representing node of BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to do in order traversal of BST and store it in array
    private static void inorder(Node root, ArrayList<Integer> traversal) {
        if (root != null) {
            inorder(root.left, traversal);
            traversal.add(root.data);
            inorder(root.right, traversal);
        }
    }

    private static int kthSmallest(Node root, int k) {
        ArrayList<Integer> traversal = new ArrayList<>();
        // Do inorder traversal and store in an array
        inorder(root, traversal);
        
        // Return the kth element of the array
        return traversal.get(k - 1);
    }

    public static void main(String[] args) {
        // Example 1
        Node root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(6);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.left.left.left = new Node(1);
        int k = 3;

        System.out.println(kthSmallest(root, k));

        // Example 2
        Node root2 = new Node(3);
        root2.left = new Node(1);
        root2.right = new Node(4);
        root2.left.right = new Node(2);
        k = 1;

        System.out.println(kthSmallest(root2, k));
    }
}

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

// Class representing node of BST
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// Function to do in order traversal of BST and store it in array
void inorder(Node *root, vector<int> &traversal) {
    if (root != NULL) {
        inorder(root->left, traversal);
        traversal.push_back(root->data);
        inorder(root->right, traversal);
    }
}

int kthSmallest(Node *root, int k) {
    vector<int> traversal;
    // Do inorder traversal and store in an array
    inorder(root, traversal);
    
    // Return the kth element of the array
    return traversal[k - 1];
}

int main() {
    // Example 1
    Node *root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(6);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->left->left->left = new Node(1);
    int k = 3;
    
    cout<<kthSmallest(root, k)<<endl;
    
    // Example 2
    Node *root2 = new Node(3);
    root2->left = new Node(1);
    root2->right = new Node(4);
    root2->left->right = new Node(2);
    k = 1;
    
    cout<<kthSmallest(root2, k)<<endl;
    
    return 0;
}
3
1

BST-də Kth Kiçik Elementin tapılmasının mürəkkəblik analizi

Zaman Mürəkkəbliyi = O (n) 
Kosmik Mürəkkəblik = O (n)
burada n BST-dəki qovşaq sayıdır.

BST-də Kth Smallest Elementini tapmaq üçün optimal yanaşma

Bu problemi həll etmək üçün daha yaxşı yanaşma genişlənmiş BST-dən istifadə etməkdir, yəni hər alt nöqtədə sol alt ağacdakı qovşaq sayını saxlayırıq. Bunun sol hesabla təmsil olunmasına icazə verin.

  1. Ağacın kökündən başlayın.
  2. Cari düyünün sol Sayı (k - 1) olduqda, bu k ən kiçik düyündür, düyünü qaytarın.
  3. Cari düyünün sol Sayı (k - 1) -dən azdırsa, sağ alt ağacda axtarın və k-nı (k - leftCount - 1) olaraq yeniləyin.
  4. Cari düyünün solCount (k - 1) -dən çoxdursa, başqa alt ağacda axtarın.

Zaman Mürəkkəbliyi = O (h), burada h BST hündürlüyüdür

Ayrıca, BST-də əlavə, kimi dəyişdirilir
Yeni düyün cari düyünün sol alt ağacına daxil ediləcəksə, cari düyünün leftCount dəyərini 1 artırın, əks halda normal BST-də etdiyimiz kimi daxil edin.

JAVA Kodu

public class KthSmallestInBST {
    // class representing Node of augmented BST
    static class Node {
        int data;
        int leftCount;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.leftCount = 0;
            left = right = null;
        }
    }

    private static Node insert(Node root, int value) {
        // Base Case
        if (root == null) {
            return new Node(value);
        }
        
        // If the new node is to be inserted in the left subtree, increment the leftCount
        // of the current node by 1
        if (value < root.data) {
            root.left = insert(root.left, value);
            root.leftCount++;
        } else if (value > root.data) {
            root.right = insert(root.right, value);
        }
        return root;
    }

    private static int kthSmallest(Node root, int k) {
        // kth smallest element does not exist
        if (root == null) {
            return -1;
        }
        
        // If lefCount is equals to k - 1, this is the kth smallest element
        if (root.leftCount == k - 1) {
            return root.data;
        } else if (root.leftCount > k - 1) {
            // If leftCount is greater than k - 1, search in the left subtree
            return kthSmallest(root.left, k);
        } else {
            // Else search in the right subtree
            return kthSmallest(root.right, k - root.leftCount - 1);
        }
    }

    public static void main(String[] args) {
        // Example 1
        Node root = null;
        root = insert(root, 5);
        root = insert(root, 3);
        root = insert(root, 6);
        root = insert(root, 2);
        root = insert(root, 4);
        root = insert(root, 1);
        int k = 3;

        System.out.println(kthSmallest(root, k));

        // Example 2
        Node root2 = null;
        root2 = insert(root2, 3);
        root2 = insert(root2, 1);
        root2 = insert(root2, 4);
        root2 = insert(root2, 2);
        k = 1;

        System.out.println(kthSmallest(root2, k));
    }
}

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

// class representing Node of augmented BST
class Node {
    public:
    int data;
    int leftCount;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        leftCount = 0;
        left = right = NULL;
    }
};

Node* insert(Node *root, int value) {
    // Base Case
    if (root == NULL) {
        return new Node(value);
    }
    
    // If the new node is to be inserted in the left subtree, increment the 
    // leftCount of the current node by 1
    if (value < root->data) {
        root->left = insert(root->left, value);
        root->leftCount++;
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

int kthSmallest(Node* root, int k) {
    // kth smallest element does not exist
    if (root == NULL) {
        return -1;
    }
    
    // If lefCount is equals to k - 1, this is the kth smallest element
    if (root->leftCount == k - 1) {
        return root->data;
    } else if (root->leftCount > k - 1) {
        // If leftCount is greater than k - 1, search in the left subtree
        return kthSmallest(root->left, k);
    } else {
        // Else search in the right subtree
        return kthSmallest(root->right, k - root->leftCount - 1);
    }
}

int main() {
    // Example 1
    Node *root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 1);
    int k = 3;
    
    cout<<kthSmallest(root, k)<<endl;
    
    // Example 2
    Node *root2 = NULL;
    root2 = insert(root2, 3);
    root2 = insert(root2, 1);
    root2 = insert(root2, 4);
    root2 = insert(root2, 2);
    k = 1;
    
    cout<<kthSmallest(root2, k)<<endl;
    
    return 0;
}
3
1

References

Translate »