BST에서 K 번째로 작은 요소

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 Facebook 구글 신탁
이진 검색 트리 이진 트리 나무조회수 19
링크드 인버퍼레딧텀블러

이 문제에서 우리는 BST와 숫자 k를 주어 BST에서 k 번째로 작은 요소를 찾습니다.

예

입력
tree [] = {5, 3, 6, 2, 4, null, null, 1}
k = 3

BST에서 K 번째로 작은 요소핀
산출
3

입력
트리 [] = {3, 1, 4, null, 2}
k = 1

BST에서 K 번째로 작은 요소핀
산출
1

BST에서 K 번째 가장 작은 요소를 찾기위한 순진한 접근 방식

순서대로 순회 BST에 저장하고 정렬 배열의 k 번째 요소를 반환합니다. BST의 inorder traversal은 정렬 된 배열을 생성하므로 inorder traversal의 k 번째 요소는 k 번째로 작은 요소입니다.

  1. BST의 순회 순회를 저장하는 정수 목록을 만듭니다.
  2. 순서 순회 수행
  3. 루트가 null이 아닌 경우 재귀 적으로 왼쪽 자식에 대해 순회 순회를 수행합니다.
  4. 현재 노드의 데이터를 목록에 삽입합니다.
  5. 오른쪽 자식에 대해 재귀 적으로 순회를 수행합니다.
  6. 마지막으로 목록의 k 번째 위치에있는 요소를 반환합니다.

JAVA 코드

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 ++ 코드

#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에서 K 번째 가장 작은 원소 찾기의 복잡성 분석

시간 복잡성 = O (N) 
공간 복잡성 = O (N)
여기서 n은 BST의 노드 수입니다.

BST에서 K 번째로 작은 원소를 찾기위한 최적의 접근 방식

이 문제를 해결하는 더 나은 접근 방식은 증강 BST를 사용하는 것입니다. 즉, 모든 노드와 함께 왼쪽 하위 트리에 노드 수를 저장합니다. 이것을 leftCount로 표현하자.

  1. 나무의 뿌리에서 시작하십시오.
  2. 현재 노드의 leftCount가 (k – 1)이면 k 번째로 작은 노드 인 경우 노드를 반환합니다.
  3. 현재 노드의 leftCount가 (k – 1)보다 작 으면 오른쪽 하위 트리에서 검색하고 k를 (k – leftCount – 1)로 업데이트합니다.
  4. 그렇지 않으면 현재 노드의 leftCount가 (k – 1)보다 크면 왼쪽 하위 트리에서 검색합니다.

시간 복잡성 = 오), 여기서 h는 BST의 높이입니다.

또한 BST의 삽입은 다음과 같이 수정됩니다.
새 노드를 현재 노드의 왼쪽 하위 트리에 삽입하려면 현재 노드의 leftCount 값을 1 씩 늘리고 그렇지 않으면 일반 BST에서와 같이 삽입합니다.

JAVA 코드

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 ++ 코드

#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

참조

링크드 인버퍼레딧텀블러
Translate »