C ++のO（n）時間とO（1）空間でBSTの中央値を見つけます

コンセプト

与えられた二分探索木（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の順序がソートされた順序になるため、BSTの順序を決定してから、中央値を決定する必要があります。ここでの概念は、O（1）エクストラスペースを使用したBSTのK番目に小さい要素に基づいています。これで、追加のスペースを実装することが許可されている場合、タスクは非常に簡単ですが、再帰とスタックを実装するInorderトラバーサルは、ここでは許可されていないスペースを使用します。

この結果、解決策は、余分なスペースを必要としないため、MorrisInorderTraversalを実行することです。

MorrisInorderTraversalは次のように説明されます-

• currentをrootとして初期化します
• 電流がNULLではない場合

  現在の子供がいない場合

  • 現在のデータを印刷する
  • 右に移動します。つまり、current =current-> right

  • それ以外の場合

  • currentをcurrentの左側のサブツリーの右端のノードの右の子として構築します
  • この左の子に移動します。つまり、current =current-> left

最終的な実装については、次のように説明します-

• いいえを数えます。 MorrisInorderTraversalを実装する特定のBST内のノードの数。

• その後、ノードをカウントし、カウントが中央値に等しいかどうかを確認して、MorrisInorderTraversalをもう一度実行します。

いいえでも検討してください。ノードのうち、前のノードを指す追加のポインタが実装されています。

例

/* 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