C++のBSTからの床と天井

ここでは、BSTから床と天井の値を見つける方法を説明します。たとえば、空きノードがBSTに配置されているメモリ管理システムを作成する場合です。入力リクエストに最適なものを見つけます。キー値よりも大きい最小のデータでツリーを下に移動するとします。3つのケースが考えられます。

• ルートが鍵です。その場合、ルート値は上限値です
• ルートデータ<キーの場合、上限値は左側のサブツリーにないため、右側のサブツリーに進み、問題のあるドメインを減らします
• ルートデータ>キーの場合、上限値は右側のサブツリーにある可能性があり、左側のサブツリーにキーよりも大きいデータを持つノードが見つかる可能性があります。そのような要素が存在しない場合、ルートは上限値です。
>

ツリーが次のようになっているとします-

0、1、2の天井は2、3の天井、4は4など

ここでは、天井関数のみを表示します。これを少し変更すると、床の値を取得できます。

例

#include <iostream>
using namespace std;
class node {
   public:
   int key;
   node* left;
   node* right;
};
node* getNode(int key) {
   node* newNode = new node();
   newNode->key = key;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
int ceiling(node* root, int num) {
   if (root == NULL)
   return -1;
   if (root->key == num)
      return root->key;
   if (root->key < num)
      return ceiling(root->right, num);
   int ceil = ceiling(root->left, num);
   return (ceil >= num) ? ceil : root->key;
}
int main() {
   node* root = getNode(8);
   root->left = getNode(4);
   root->right = getNode(12);
   root->left->left = getNode(2);
   root->left->right = getNode(6);
   root->right->left = getNode(10);
   root->right->right = getNode(14);
   for (int i = 0; i < 16; i++)
   cout << i << "\tCeiling: " << ceiling(root, i) << endl;
}

出力

0 Ceiling: 2
1 Ceiling: 2
2 Ceiling: 2
3 Ceiling: 4
4 Ceiling: 4
5 Ceiling: 6
6 Ceiling: 6
7 Ceiling: 8
8 Ceiling: 8
9 Ceiling: 10
10 Ceiling: 10
11 Ceiling: 12
12 Ceiling: 12
13 Ceiling: 14
14 Ceiling: 14
15 Ceiling: -1