Khái niệm
Đối với Cây tìm kiếm nhị phân (BST) nhất định, nhiệm vụ của chúng tôi là xác định giá trị trung bình của nó.
Đối với thậm chí không. số nút, trung vị =((n / nút thứ 2 + (n + 1) / nút thứ 2) / 2 Đối với số nút lẻ, trung vị =(n + 1) / nút thứ 2.
Đối với BST đã cho (với số nút lẻ) là -
7 / \ 4 9 / \ / \ 2 5 8 10
Inorder of Given BST sẽ là:2, 4, 5, 7, 8, 9, 10 Vì vậy, ở đây trung bình sẽ là 7.
Đối với BST đã cho (thậm chí không có số nút) là -
7 / \ 4 9 / \ / 2 5 8
Inorder của BST Given sẽ là - 2, 4, 5, 7, 8, 9
Vì vậy, ở đây trung vị sẽ (5 + 7) / 2 =6.
Phương pháp
Để xác định giá trị trung bình, chúng ta cần xác định giá trị trung bình của BST bởi vì phân tử nhỏ hơn của nó sẽ được sắp xếp theo thứ tự và sau đó xác định trung vị. Ở đây, khái niệm dựa trên phần tử nhỏ nhất K’th trong BST sử dụng thêm Khoảng trống O (1). Bây giờ, nhiệm vụ rất đơn giản nếu chúng ta được phép triển khai thêm không gian nhưng Inorder truyền tải thực hiện đệ quy và ngăn xếp đều sử dụng không gian không được phép ở đây.
Do đó, giải pháp là thực hiện Morris Inorder Traversal vì nó không yêu cầu thêm dung lượng.
Morris Inorder Traversal được giải thích theo cách sau -
- Chúng tôi khởi tạo hiện tại dưới dạng gốc
- Trong khi hiện tại không phải là NULL
Nếu dòng điện không có con trái
- In dữ liệu hiện tại
- Di chuyển sang phải, tức là current =current-> sang phải
-
Khác
- Xây dựng dòng điện làm nút con bên phải của nút ngoài cùng bên phải trong cây con bên trái của hiện tại
- Di chuyển sang con bên trái này, tức là current =current-> left
Việc triển khai cuối cùng được thảo luận theo cách sau -
-
Chúng tôi đếm số không. của các nút trong BST đã cho đang triển khai Morris Inorder Traversal.
-
Sau đó, thực hiện Morris Inorder Traversal một lần nữa bằng cách đếm các nút và xác minh xem số lượng có bằng điểm trung bình hay không.
Đối với việc xem xét thậm chí không. của các nút, một con trỏ bổ sung trỏ đến nút trước đó được triển khai.
Ví dụ
/* 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;
} Đầu ra
Median of BST is(for odd no. of nodes) 7 Median of BST is(for even no. of nodes) 6