แนวคิด
ในส่วนที่เกี่ยวข้องกับ Binary Search Tree (BST) หน้าที่ของเราคือกำหนดค่ามัธยฐานของต้นไม้
สำหรับแม้แต่ไม่ ของโหนด ค่ามัธยฐาน =((โหนด 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 เนื่องจากลำดับของค่ามัธยฐานจะอยู่ในลำดับที่เรียงลำดับแล้วจึงกำหนดค่ามัธยฐาน ในที่นี้ แนวคิดนี้ใช้องค์ประกอบที่เล็กที่สุดของ K ใน BST โดยใช้ O(1) extra Space ตอนนี้ งานนี้ง่ายมาก หากเราได้รับอนุญาตให้ใช้พื้นที่เพิ่มเติม แต่ Inorder traversal การนำ recursion และ stack ไปใช้ Inorder ทั้งคู่ใช้พื้นที่ซึ่งไม่ได้รับอนุญาตที่นี่
ด้วยเหตุนี้ วิธีแก้ไขคือดำเนินการ Morris Inorder Traversal เนื่องจากไม่ต้องการพื้นที่เพิ่มเติม
Morris Inorder Traversal ได้อธิบายไว้ดังนี้ -
- เราเริ่มต้นปัจจุบันเป็นรูท
- ในขณะที่กระแสไม่ใช่ NULL
หากกระแสไม่ทิ้งลูก
- พิมพ์ข้อมูลปัจจุบัน
- เลื่อนไปทางขวา นั่นคือ current =current->right
-
อื่นๆ
- สร้างกระแสให้เป็นลูกด้านขวาของโหนดขวาสุดในทรีย่อยด้านซ้ายของปัจจุบัน
- ย้ายไปที่ลูกด้านซ้ายนี้ นั่นคือ current =current->left
มีการกล่าวถึงการใช้งานขั้นสุดท้ายดังนี้ -
-
เรานับจำนวน ของโหนดใน BST ที่กำหนดซึ่งใช้ Morris Inorder Traversal
-
หลังจากนั้นดำเนินการ 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
