algorithm
ツリーがBSTかどうかを確認する
サーチ…
指定された入力ツリーがバイナリ検索ツリーのプロパティに従っているかどうか
例えば
入力が次の場合:
出力はfalseでなければなりません:
左のサブツリーの4が根の値(3)より大きいため、
入力が次の場合:
出力は真でなければならない
与えられたバイナリツリーがBSTかどうかをチェックするアルゴリズム
バイナリツリーは、次のいずれかの条件を満たす場合はBSTです。
- それは空です
- サブツリーはありません
- ツリー内のすべてのノードxに対して、左のサブツリーのすべてのキー(存在する場合)はキー(x)より小さくなければならず、右のサブツリーのすべてのキー(存在する場合)はキー(x)より大きくなければなりません。
したがって、簡単な再帰アルゴリズムは次のようになります。
is_BST(root):
if root == NULL:
return true
// Check values in left subtree
if root->left != NULL:
max_key_in_left = find_max_key(root->left)
if max_key_in_left > root->key:
return false
// Check values in right subtree
if root->right != NULL:
min_key_in_right = find_min_key(root->right)
if min_key_in_right < root->key:
return false
return is_BST(root->left) && is_BST(root->right)
上記の再帰的アルゴリズムは、各ノードを複数回通過するため、正確ではあるが非効率的である。
各ノードの多重訪問を最小限にする別のアプローチは、訪問しているサブツリー内のキーの可能な最小値および最大値を記憶することである。任意のキーの最小値をK_MIN
、最大値をK_MAX
ます。ツリーのルートから始めると、ツリー内の値の範囲は[K_MIN,K_MAX]
です。ルートノードのキーをx
。次に、左のサブツリーの値の範囲は[K_MIN,x)
あり、右のサブツリーの値の範囲は(x,K_MAX]
です。
is_BST(root, min, max):
if root == NULL:
return true
// is the current node key out of range?
if root->key < min || root->key > max:
return false
// check if left and right subtree is BST
return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)
それは当初、次のように呼ばれます:
is_BST(my_tree_root,KEY_MIN,KEY_MAX)
別の方法は、バイナリツリーのインオーダートラバーサルを行うことです。インオーダートラバーサルがソートされたキーシーケンスを生成する場合、指定されたツリーはBSTです。インオーダーシーケンスがソートされているかどうかをチェックするには、以前に訪問したノードの値を覚えて、それを現在のノードと比較します。
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow