컨셉
주어진 BST(Binary Search Tree)와 관련하여 우리의 임무는 그것의 중앙값을 결정하는 것입니다.
아니더라도. 노드의 중앙값 =((n/2번째 노드 + (n+1)/2번째 노드) /2 홀수 노드의 경우 중앙값 =(n+1)/2번째 노드
주어진 BST(노드의 홀수)는 -
7 / \ 4 9 / \ / \ 2 5 8 10
주어진 BST의 순서는 다음과 같습니다. 2, 4, 5, 7, 8, 9, 10 따라서 중앙값은 7입니다.
주어진 BST에 대해(짝수 노드 수)는 -
7 / \ 4 9 / \ / 2 5 8
주어진 BST의 순서는 − 2, 4, 5, 7, 8, 9
입니다.따라서 여기서 중앙값은 (5+7)/2 =6입니다.
방법
중앙값을 결정하기 위해서는 BST의 inorder가 정렬된 순서로 정렬될 것이기 때문에 BST의 inorder를 결정한 다음 중앙값을 결정해야 합니다. 여기에서 개념은 O(1) 추가 공간을 사용하는 BST의 K' 가장 작은 요소를 기반으로 합니다. 이제 추가 공간을 구현하는 것이 허용되지만 재귀와 스택을 구현하는 Inorder 순회는 여기에서 허용되지 않는 공간을 사용하는 경우 작업이 매우 간단합니다.
결과적으로 추가 공간이 필요하지 않기 때문에 Morris Inorder Traversal을 수행하는 것이 솔루션입니다.
Morris Inorder Traversal은 다음과 같이 설명됩니다. -
- 현재를 루트로 초기화합니다.
- 현재가 NULL이 아닌 동안
현재에 왼쪽 자식이 없는 경우
- 현재 데이터 인쇄
- 오른쪽으로 이동, 즉 현재 =현재->오른쪽
-
기타
- current를 현재의 왼쪽 하위 트리에서 가장 오른쪽 노드의 오른쪽 자식으로 구성합니다.
- 이 왼쪽 자식으로 이동합니다. 즉, 현재 =현재->왼쪽
최종 구현은 다음과 같은 방식으로 논의됩니다 -
-
우리는 번호를 계산합니다. Morris Inorder Traversal을 구현하는 주어진 BST의 노드 수
-
그런 다음 노드를 계산하고 count가 중앙값과 같은지 확인하여 Morris Inorder Traversal을 한 번 더 수행합니다.
아니더라도 고려하기 위해. 노드의 이전 노드를 가리키는 추가 포인터가 구현됩니다.
예시
/* C++ program to find the median of BST in O(n) time and O(1)
space*/
#include<bits/stdc++.h>
using namespace std;
/* Implements a binary search tree Node1 which has data, pointer
to left child and a pointer to right child */
struct Node1{
int data1;
struct Node1* left1, *right1;
};
//Shows a utility function to create a new BST node
struct Node1 *newNode(int item1){
struct Node1 *temp1 = new Node1;
temp1->data1 = item1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
/* Shows a utility function to insert a new node with
given key in BST */
struct Node1* insert(struct Node1* node1, int key1){
/* It has been seen that if the tree is empty, return a new node
*/
if (node1 == NULL) return newNode(key1);
/* Else, recur down the tree */
if (key1 < node1->data1)
node1->left1 = insert(node1->left1, key1);
else if (key1 > node1->data1)
node1->right1 = insert(node1->right1, key1);
/* return the (unchanged) node pointer */
return node1;
}
/* Shows function to count nodes in a binary search tree
using Morris Inorder traversal*/
int counNodes(struct Node1 *root1){
struct Node1 *current1, *pre1;
// Used to initialise count of nodes as 0
int count1 = 0;
if (root1 == NULL)
return count1;
current1 = root1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count node if its left is NULL
count1++;
// Go to its right
current1 = current1->right1;
} else {
/* Determine the inorder predecessor of current */
pre1 = current1->left1;
while (pre1->right1 != NULL &&
pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder predecessor */
if(pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* we have to revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
// Now increment count if the current
// node is to be visited
count1++;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
return count1;
}
/* Shows function to find median in O(n) time and O(1) space
using Morris Inorder traversal*/
int findMedian(struct Node1 *root1){
if (root1 == NULL)
return 0;
int count1 = counNodes(root1);
int currCount1 = 0;
struct Node1 *current1 = root1, *pre1, *prev1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count current node
currCount1++;
// Verify if current node is the median
// Odd case
if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
return prev1->data1;
// Even case
else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
return (prev1->data1 + current1->data1)/2;
// Now update prev1 for even no. of nodes
prev1 = current1;
//Go to the right
current1 = current1->right1;
} else {
/* determine the inorder predecessor of current1 */
pre1 = current1->left1;
while (pre1->right1 != NULL && pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder
predecessor */
if (pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* We have to revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
prev1 = pre1;
// Now count current node
currCount1++;
// Verify if the current node is the median
if (count1 % 2 != 0 && currCount1 == (count1+1)/2 )
return current1->data1;
else if (count1%2==0 && currCount1 == (count1/2)+1)
return (prev1->data1+current1->data1)/2;
// Now update prev1 node for the case of even
// no. of nodes
prev1 = current1;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main(){
/* Let us create following BST
7
/ \
4 9
/ \ / \
2 5 8 10 */
struct Node1 *root1 = NULL;
root1 = insert(root1, 7);
insert(root1, 4);
insert(root1, 2);
insert(root1, 5);
insert(root1, 9);
insert(root1, 8);
insert(root1, 10);
cout << "\nMedian of BST is(for odd no. of nodes) "<< findMedian(root1) <<endl;
/* Let us create following BST
7
/ \
4 9
/ \ /
2 5 8
*/
struct Node1 *root2 = NULL;
root2 = insert(root2, 7);
insert(root2, 4);
insert(root2, 2);
insert(root2, 5);
insert(root2, 9);
insert(root2, 8);
cout << "\nMedian of BST is(for even no. of nodes) "
<< findMedian(root2);
return 0;
} 출력
Median of BST is(for odd no. of nodes) 7 Median of BST is(for even no. of nodes) 6