이진 검색 트리에서 최적의 방법으로 k 번째로 작은 요소 찾기
정적 / 전역 변수를 사용하지 않고 이진 검색 트리에서 k 번째로 작은 요소를 찾아야합니다. 효율적으로 달성하는 방법? 내가 생각하는 해결책은 전체 트리의 순서 순회를 계획하고 있기 때문에 최악의 경우 인 O (n)에서 작업을 수행하는 것입니다. 그러나 깊이 나는 여기서 BST 속성을 사용하지 않는다고 생각합니다. 가정 솔루션이 정확합니까, 아니면 더 나은 솔루션이 있습니까?
아이디어의 개요는 다음과 같습니다.
BST에서 노드의 왼쪽 하위 트리 T에는에 저장된 값보다 작은 요소 만 포함됩니다 T. 경우 k좌측 서브 트리 내의 요소의 수보다 작은 k최소 번째 요소는 좌측 서브 트리에 속해야한다. 그렇지 않으면 k더 큰 경우 k가장 작은 요소가 오른쪽 하위 트리에 있습니다.
BST를 보강하여 각 노드가 왼쪽 하위 트리에 요소 수를 저장하도록 할 수 있습니다 (주어진 노드의 왼쪽 하위 트리에 해당 노드가 포함되어 있다고 가정). 이 정보를 사용하면 왼쪽 하위 트리의 요소 수를 반복적으로 요청하여 트리를 순회하여 왼쪽 또는 오른쪽 하위 트리로 재귀를 수행할지 여부를 결정할 수 있습니다.
이제 노드 T에 있다고 가정하십시오.
- 경우 (T의 서브 트리를 왼쪽) K == NUM_ELEMENTS , 우리가 찾고있는 대답은 노드의 값입니다
T. - 경우 K> NUM_ELEMENTS (T의 좌측 서브 트리)은 이들 요소도보다 작을 수 있기 때문에, 그때 분명 우리는 좌측 서브 트리를 무시해
k번째 최소. 따라서k - num_elements(left subtree of T)올바른 하위 트리 의 가장 작은 요소 를 찾는 문제를 줄 입니다. - 경우 K <NUM_ELEMENTS (T의 왼쪽 하위 트리) , 그 다음
k우리가 찾는 문제를 줄일 수 있도록 일 최소의 왼쪽 서브 트리에 어딘가에k왼쪽 하위 트리에서 일 가장 작은 요소.
복잡성 분석 :
이것은 균형 잡힌 BST에서 또는 최악의 경우 무작위 BST 에서 O(depth of node)시간 이 걸립니다 .O(log n)O(log n)
BST에는 O(n)스토리지 가 필요하며 O(n)요소 수에 대한 정보를 저장하려면 다른 스토리지 가 필요합니다 . 모든 BST 작업 O(depth of node)에는 시간이 걸리고 O(depth of node)노드의 삽입, 삭제 또는 회전을 위해 "요소 수"정보를 유지하는 데 시간 이 더 걸립니다 . 따라서, 왼쪽 서브 트리에 요소 수에 대한 정보를 저장하면 BST의 공간 및 시간 복잡성이 유지됩니다.
더 간단한 해결책은 비 순차 순회를 수행하고 현재 인쇄 할 요소를 인쇄하지 않고 추적하는 것입니다. k에 도달하면 요소를 인쇄하고 나머지 트리 탐색을 건너 뜁니다.
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;
}
이것은 위의 알고리즘을 기반으로 C #에서 구현 한 것입니다. 사람들이 나를 위해 더 잘 이해할 수 있도록 게시 할 것이라고 생각했습니다.
IVlad 감사합니다
더 간단한 해결책은 inorder traversal을 수행하고 현재 카운터 k로 인쇄 할 요소를 추적하는 것입니다. k에 도달하면 요소를 인쇄합니다. 런타임은 O (n)입니다. 함수 반환 유형은 void가 될 수 없으므로 각 재귀 호출 후에 업데이트 된 k 값을 반환해야합니다. 이에 대한 더 나은 해결책은 각 노드에서 정렬 된 위치 값을 가진 확장 된 BST입니다.
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;
}
// 재귀없이 자바 버전 추가
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();
}
}
}
http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal 반복 순차 순회를 사용 하면 스택에서 노드를 팝 한 후 kth 요소를 간단히 확인할 수 있습니다 .
일반 이진 검색 트리 만 있으면 가능한 한 작은 것부터 시작하여 위로 이동하여 올바른 노드를 찾습니다.
이 작업을 매우 자주 수행하려는 경우 왼쪽 하위 트리에 몇 개의 노드가 있는지 나타내는 속성을 각 노드에 추가 할 수 있습니다. 이를 사용하여 트리를 올바른 노드로 직접 내릴 수 있습니다.
카운터가있는 재귀 순서대로 걷기
Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack
이 아이디어는 @prasadvk 솔루션과 유사하지만 단점이 있습니다 (아래 참고 참조).이를 별도의 답변으로 게시하고 있습니다.
// 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 );
}
참고 사항 (@prasadvk 솔루션과의 차이점) :
if( counter == k )테스트는 (a) 왼쪽 서브 트리 후, (b) 루트 후 및 (c) 오른쪽 서브 트리 후의 세 위치 에서 필요합니다 . 이는 k 번째 요소가 모든 위치에 대해 , 즉 하위 트리에 관계없이 감지되도록하기위한 것 입니다.if( result == -1 )결과 요소 만 인쇄하려면 테스트가 필요합니다 . 그렇지 않으면 k 번째부터 루트까지 모든 요소가 인쇄됩니다.
들어 있지 트리를 검색 균형, 그것은 소요 O (N)를 .
들면 균형 탐색 트리는 얻어 O (K + 로그 n)이 최악의 경우이지만 단지 O (k)를 에 상각의 의미.
모든 노드에 대해 추가 정수를 보유하고 관리합니다. 하위 트리의 크기는 O (log n) 시간 복잡성을줍니다. 이러한 균형 잡힌 검색 트리를 보통 RankTree라고합니다.
일반적으로 솔루션은 트리가 아닌 솔루션입니다.
문안 인사.
이것은 잘 작동합니다 : status : 요소의 발견 여부를 보유하는 배열입니다. k : 찾을 k 번째 요소입니다. count : 트리 순회 동안 순회 된 노드 수를 추적합니다.
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;
}
이것이 문제에 대한 최적의 해결책은 아니지만, 다른 사람들이 흥미로운 것으로 생각할 수있는 또 다른 잠재적 인 해결책입니다.
/**
* 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 );
}
서명:
Node * find(Node* tree, int *n, int k);
전화 :
*n = 0;
kthNode = find(root, n, k);
정의:
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;
}
여기 내 2 센트는 ...
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;
}
이것은 내가 그래도 작동합니다. 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
순차 순으로 순회를 사용하고 방문한 요소를 스택에 푸시 할 수 있습니다. 대답을 얻으려면 k 번을 팝하십시오.
k 개의 요소 뒤에 멈출 수도 있습니다
완전한 BST 사례에 대한 솔루션 :-
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;
}
Linux Kernel은 linux / lib / rbtree.c의 O (log n)에서 순위 기반 작업을 지원하는 뛰어난 확장 된 레드-블랙 트리 데이터 구조를 가지고 있습니다.
매우 조잡한 Java 포트는 http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java 에서 찾을 수 있습니다 . RbRoot.java 및 RbNode.java와 함께. n 번째 요소는 RbNode.nth (RbNode node, int n)를 호출하여 트리의 루트를 전달하여 얻을 수 있습니다.
다음 은 k 번째로 작은 요소 를 반환 하지만 k를 참조 인수로 전달 해야하는 C # 의 간결한 버전입니다 (@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);
}
가장 작은 노드 를 찾으 려면 O (log n) 이고 k 번째 노드로 이동하려면 O (k)이므로 O (k + log n)입니다.
http://www.geeksforgeeks.org/archives/10379
이것은이 질문에 대한 정확한 답변입니다.
1. O (n) 시간에 순서 순회 사용 2. k + log n 시간에 확장 트리 사용
더 나은 알고리즘을 찾을 수 없었습니다. 그래서 하나를 작성하기로 결정했습니다.
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));
}
}
다음은 자바 코드입니다.
max (Node root, int k) -가장 큰 k를 찾기 위해
min (노드 루트, int k) -가장 작은 k를 찾기 위해
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);
}
이것도 작동합니다. 트리에서 maxNode를 사용하여 함수를 호출하십시오.
def k_largest (self, node, k) : if k <0 : return
k == 0 인 경우 None 반환 : 노드를 반환 : k-= 1 return self.k_largest (self.predecessor (node), k)
자식 트리의 수를 저장하기 위해 원래 트리 노드를 수정할 필요가 없기 때문에 이것이 허용 된 답변보다 낫다고 생각합니다.
순서대로 순회를 사용하여 왼쪽에서 오른쪽으로 가장 작은 노드를 계산하고 카운트가 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);
}
를 사용하는 IVlad 솔루션 order statistics tree이 가장 효율적입니다. 그러나 당신이 사용할 수없고 order statistics tree규칙적인 오래된 BST에 붙어 있다면 가장 좋은 방법은 (순서 순회)를하는 것입니다 (prasadvk가 지적한대로). 그러나 k 번째로 작은 요소를 반환하고 단순히 값을 인쇄하려는 것이 아니라면 그의 해결책은 부적절합니다. 또한 그의 솔루션은 재귀 적이므로 스택 오버플로의 위험이 있습니다. 따라서 k 번째로 작은 노드를 반환하고 스택을 사용하여 In Order Traversal을 수행하는 Java 솔루션을 작성했습니다. 실행 시간은 O (n)이고 공간 복잡도는 O (h)입니다. 여기서 h는 트리의 최대 높이입니다.
// 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;
}
최선의 접근 방식은 이미 존재하지만 간단한 코드를 추가하고 싶습니다.
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 );
}}
보조 결과 클래스를 사용하여 노드가 있는지 및 현재 k를 추적합니다.
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;
}
}
}
k 번째로 작은 요소를 계산하는 깔끔한 함수를 작성했습니다. 나는 순차 순회를 사용하고 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;
}
}
}
'Programing' 카테고리의 다른 글
| Bash에서 시간 초과로 프로세스를 실행하는 방법은 무엇입니까? (0) | 2020.07.30 |
|---|---|
| NPM 스크립트를 순차적으로 실행 (0) | 2020.07.30 |
| 레일에서 모델 제거 (“레일 g 모델 제목…”의 반대) (0) | 2020.07.30 |
| 웹 페이지에서 사용중인 CSS 스타일을 확인하는 방법이 있습니까? (0) | 2020.07.29 |
| 기록 된 매크로는 메모장 ++에 어디에 저장되어 있습니까? (0) | 2020.07.29 |