algorithm - 二分探索木をどのように検証しますか?

Question

ここでは、二分探索木の検証として知られるインタビューの演習について読みました。

これはどのように機能しますか？二分探索木を検証する際に何を探すでしょうか? 基本的な検索ツリーを作成しましたが、この概念について聞いたことがありません。

score 116 · Accepted Answer

実際、それは面接で誰もがする間違いです。

Leftchild は (minLimitof node,node.value) に対してチェックする必要があります

Rightchild は (node.value,MaxLimit of node) に対してチェックする必要があります

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

別の解決策 (スペースが制約でない場合): ツリーの順序どおりのトラバーサルを実行し、ノード値を配列に格納します。配列がソートされている場合、それは有効な BST であり、そうでない場合はそうではありません。

score 18 · Accepted Answer

二分探索木の「検証」とは、左側にすべての小さな項目があり、右側に大きな項目がすべてあることを確認することを意味します。本質的には、二分木が二分探索木かどうかを確認するためのチェックです。

score 16 · Accepted Answer

私が見つけた最良の解決策は O(n) であり、余分なスペースを使用しません。これは inorder traversal に似ていますが、それを配列に格納してからソートされているかどうかをチェックする代わりに、静的変数を取り、inorder traversal で配列がソートされているかどうかをチェックすることができます。

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

score 7 · Accepted Answer

inorder トラバーサルを使用した反復ソリューション。

bool is_bst(Node *root) {
  if (!root)
    return true;

  std::stack<Node*> stack;
  bool started = false;
  Node *node = root;
  int prev_val;

  while(true) {
    if (node) {
      stack.push(node);
      node = node->left();
      continue;
    }
    if (stack.empty())
      break;
    node = stack.top();
    stack.pop();

    /* beginning of bst check */
    if(!started) {
      prev_val = node->val();
      started = true;
    } else {
      if (prev_val > node->val())
        return false;
      prev_val = node->val();
    }
    /* end of bst check */

    node = node->right();
  }
  return true;
}

score 5 · Accepted Answer

Clojureでの私のソリューションは次のとおりです。

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))

score 3 · Accepted Answer

BST の順序通りのトラバーサルは非減少シーケンスであるため、このプロパティを使用して、バイナリツリーが BST であるかどうかを判断できます。モリストラバーサルを使用してノードを維持することで、 O(n) 時間と O(1) 空間の複雑さpreで解を得ることができました。これが私のコードです

public boolean isValidBST(TreeNode root) {
    TreeNode pre = null, cur = root, tmp;
    while(cur != null) {
        if(cur.left == null) {
            if(pre != null && pre.val >= cur.val) 
                return false;
            pre = cur;
            cur = cur.right;
        }
        else {
            tmp = cur.left;
            while(tmp.right != null && tmp.right != cur)
                tmp = tmp.right;
            if(tmp.right == null) { // left child has not been visited
                tmp.right = cur;
                cur = cur.left;
            }
            else { // left child has been visited already
                tmp.right = null;
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
        }
    }
    return true;
}

score 1 · Accepted Answer

bool BinarySearchTree::validate() {
    int minVal = -1;
    int maxVal = -1;
    return ValidateImpl(root, minVal, maxVal);
}

bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal)
{
    int leftMin = -1;
    int leftMax = -1;
    int rightMin = -1;
    int rightMax = -1;

    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value < currRoot->value) {
            if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false;
            if (leftMax != currRoot->left->value && currRoot->value < leftMax)  return false;
        }
        else
            return false;
    } else {
        leftMin = leftMax = currRoot->value;
    }

    if (currRoot->right) {
        if (currRoot->right->value > currRoot->value) {
            if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false;
            if (rightMin != currRoot->right->value && currRoot->value > rightMin)  return false;
        }
        else return false;
    } else {
        rightMin = rightMax = currRoot->value;
    }

    minVal = leftMin < rightMin ? leftMin : rightMin;
    maxVal = leftMax > rightMax ? leftMax : rightMax;

    return true;
}

score 1 · Accepted Answer

「最初に不変条件を定義することをお勧めします。ここでの不変条件は次のとおりです。順序通りのトラバーサルで BST の任意の 2 つの連続する要素は、それらの外観が厳密に増加する順序でなければなりません (等しいことはできず、常に順序どおりに増加します)。したがって、ソリューションは、最後に訪問したノードを記憶し、現在のノードと最後に訪問したノードを '<' (または '>') で比較する単純な順序でトラバーサルすることができます。

score 0 · Accepted Answer

// using inorder traverse based Impl
bool BinarySearchTree::validate() {
    int val = -1;
    return ValidateImpl(root, val);
}

// inorder traverse based Impl
bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) {
    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value > currRoot->value) return false;
        if(!ValidateImpl(currRoot->left, val)) return false;
    }

    if (val > currRoot->value) return false;
    val = currRoot->value;

    if (currRoot->right) {
        if (currRoot->right->value < currRoot->value) return false;
        if(!ValidateImpl(currRoot->right, val)) return false;
    }
    return true;
}

score 0 · Accepted Answer

以下は、BST 検証の Java 実装です。ここでは、ツリーの順序に従って DFS を移動し、最後の数値よりも大きい数値を取得すると false を返します。

static class BSTValidator {
  private boolean lastNumberInitialized = false;
  private int lastNumber = -1;

  boolean isValidBST(TreeNode node) {
    if (node.left != null && !isValidBST(node.left)) return false;

    // In-order visiting should never see number less than previous
    // in valid BST.
    if (lastNumberInitialized && (lastNumber > node.getData())) return false;
    if (!lastNumberInitialized) lastNumberInitialized = true;

    lastNumber = node.getData();

    if (node.right != null && !isValidBST(node.right)) return false;

    return true;
  }
}

score 0 · Accepted Answer

bool isBST(struct node* root)
{
    static struct node *prev = NULL;
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
            return false;
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
            return false;
        prev = root;
        return isBST(root->right);
    }
    return true;
}

正常に動作します：）

score 0 · Accepted Answer

再帰的な解決策:

isBinary(root)
    {
        if root == null 
          return true
       else if( root.left == NULL and root.right == NULL)
          return true
       else if(root.left == NULL)
           if(root.right.element > root.element)
               rerturn isBInary(root.right)
        else if (root.left.element < root.element)
              return isBinary(root.left)
        else
              return isBInary(root.left) and isBinary(root.right)

    }

score 0 · Accepted Answer

これは重複に対して機能します。

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = int.min, max = int.max):
    if node == null:
        return true
    if node.value <= min || max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

これは、型を使用する値に対しても機能int.minしint.maxますNullable。

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = null, max = null):
    if node == null:
        return true
    if min != null && node.value <= min
        return false
    if max != null && max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

score 0 · Accepted Answer

bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX)
{
    return
    (
        pCurrentNode == NULL
    )
    ||
    (
        (
            !pCurrentNode->pLeftNode ||
            (
                pCurrentNode->pLeftNode->value < pCurrentNode->value &&
                pCurrentNode->pLeftNode->value < nMax &&
                ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value)
            )
        )
        &&
        (
            !pCurrentNode->pRightNode ||
            (
                pCurrentNode->pRightNode->value > pCurrentNode->value &&
                pCurrentNode->pRightNode->value > nMin &&
                ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax)
            )
        )
    );
}

score 0 · Accepted Answer

http://www.jiuzhang.com/solutions/validate-binary-search-tree/に触発されました

トラバーサルと分割 && 征服の 2 つの一般的な解決策があります。

public class validateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return isBSTTraversal(root) && isBSTDivideAndConquer(root);
    }

    // Solution 1: Traversal
    // The inorder sequence of a BST is a sorted ascending list
    private int lastValue = 0; // the init value of it doesn't matter.
    private boolean firstNode = true;
    public boolean isBSTTraversal(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }

        // firstNode is needed because of if firstNode is Integer.MIN_VALUE,
        // even if we set lastValue to Integer.MIN_VALUE, it will still return false
        if (!firstNode && lastValue >= root.val) {
            return false;
        }

        firstNode = false;
        lastValue = root.val;

        if (!isValidBST(root.right)) {
            return false;
        }

        return true;

    }

    // Solution 2: divide && conquer
    private class Result {
        int min;
        int max;
        boolean isBST;
        Result(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public boolean isBSTDivideAndConquer(TreeNode root) {
        return isBSTHelper(root).isBST;
    }

    public Result isBSTHelper(TreeNode root) {
        // For leaf node's left or right
        if (root == null) {
            // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE
            // because of in the previous level which is the leaf level,
            // we want to set the min or max to that leaf node's val (in the last return line)
            return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        }

        Result left = isBSTHelper(root.left);
        Result right = isBSTHelper(root.right);

        if (!left.isBST || !right.isBST) {
            return new Result(0,0, false);
        }

        // For non-leaf node
        if (root.left != null && left.max >= root.val
                && root.right != null && right.min <= root.val) {
            return new Result(0, 0, false);
        }

        return new Result(Math.min(left.min, root.val),
                Math.max(right.max, root.val), true);
    }
}

score 0 · Accepted Answer

inorder Traversal BST を使用し、ノードが space O(1)AND timeの順序で増加しているかどうかを確認するソリューションを作成しましたO(n)。TreeNode predecessor前のノードです。解決策が正しいかどうかはわかりません。inorder Traversal ではツリー全体を定義できないためです。

public boolean isValidBST(TreeNode root, TreeNode predecessor) {
    boolean left = true, right = true;
    if (root.left != null) {
        left = isValidBST(root.left, predecessor);
    }
    if (!left)
        return false;

    if (predecessor.val > root.val)
        return false;

    predecessor.val = root.val;
    if (root.right != null) {
        right = isValidBST(root.right, predecessor);
    }

    if (!right)
        return false;

    return true;

}

score 0 · Accepted Answer

inOrder トラバーサルの使用..

最初に、ツリーの値を順序通りのトラバーサルで配列に追加します。

次に、フラグ値 true を追加して配列を反復処理し、ルート要素の後とルート要素の前で要素を分割します。

ツリーに同じルート値を持つ要素があるかどうかを確認するためにカウンターが追加されます。

min と max は範囲に設定されます

var isValidBST = function(root) 
{

    
    if(!root) return false;
    
 
    let current = root;
    let data = [];
    let flag = false;
    let counter = 0;
    
    function check(node){
        if(node.left){
            check(node.left);
        }
        data.push(node.val);
        if(node.right){
            check(node.right);
        }
       
    }
    
    
    let min = Number.MIN_SAFE_INTEGER;
    let max = root.val;
    for(let i = 0; i < data.length; i++){
        
        if(data[i] == root.val){
            flag = true;
            counter++;
        }
        
        if(flag){
            if(data[i] < root.val || data[i] < max || counter > 1){
                return false;
            }
            else{
                
                max = data[i];
            }
            
            
        }
        else{
            if(data[i] > root.val || data[i] <= min|| counter > 1){
                return false
            }
            else {
                min = data[i]
            }
        }
    }
    
    return true;
    

};

score 0 · Accepted Answer

特定の BT が任意のデータ型の BST であるかどうかを調べるには、以下のアプローチを使用する必要があります。1. inorder トラバーサルを使用して、リーフノードの最後まで再帰関数を呼び出します。 2. 最小値と最大値を自分で作成します。

ツリー要素には、より小さい/より大きい演算子が定義されている必要があります。

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}

score 0 · Accepted Answer

再帰は簡単ですが、反復アプローチの方が優れています。上記の反復バージョンが 1 つありますが、必要以上に複雑すぎます。これは、どこにでもある最高のソリューションです。c++

このアルゴリズムはO(N)時間内に実行され、O(lgN)スペースが必要です。

struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
};

bool isBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* prev = nullptr;
    while (root || stack.size()) {
        if (root) {
           stack.push_back(root);
           root = root->left;
        } else {
            if (prev && stack.back()->value <= prev->value)
                return false;
            prev = stack.back();
            root = prev->right;                    
            stack.pop_back();
        }
    }
    return true;
}

score 0 · Accepted Answer

Python の実装例。この例では、型注釈を使用しています。ただし、 Node クラスはそれ自体を使用するため、モジュールの最初の行として含める必要があります。

from __future__ import annotations

そうしないと、name 'Node' is not definedエラーが発生します。この例でもデータクラスを例として使用しています。BST かどうかを確認するために、再帰を使用して左右のノードの値を確認します。

"""Checks if Binary Search Tree (BST) is balanced"""

from __future__ import annotations
import sys
from dataclasses import dataclass

MAX_KEY = sys.maxsize
MIN_KEY = -sys.maxsize - 1


@dataclass
class Node:
    value: int
    left: Node
    right: Node

    @property
    def is_leaf(self) -> bool:
        """Check if node is a leaf"""
        return not self.left and not self.right


def is_bst(node: Node, min_value: int, max_value: int) -> bool:
    if node.value < min_value or max_value < node.value:
        return False
    elif node.is_leaf:
        return True

    return is_bst(node.left, min_value, node.value) and is_bst(
        node.right, node.value, max_value
    )


if __name__ == "__main__":
    node5 = Node(5, None, None)
    node25 = Node(25, None, None)
    node40 = Node(40, None, None)
    node10 = Node(10, None, None)

    # balanced tree
    node30 = Node(30, node25, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

    # unbalanced tree
    node30 = Node(30, node5, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

score -1 · Accepted Answer

これは、余分なスペースを使用しない反復ソリューションです。

Node{
     int value;
     Node right, left
  }

  public boolean ValidateBST(Node root){
    Node currNode = root;
    Node prevNode = null;
    Stack<Node> stack = new Stack<Node>();
    while(true){
        if(currNode != null){
            stack.push(currNode);
            currNode = currNode.left;
            continue;
        }
        if(stack.empty()){
            return;
        }
        currNode = stack.pop();
        if(prevNode != null){
            if(currNode.value < prevNode.value){
                return false;
            }
        }
        prevNode = currNode;
        currNode = currNode.right;
    }
}

score -1 · Accepted Answer

 private void validateBinarySearchTree(Node node) {
    if (node == null) return;

    Node left = node.getLeft();
    if (left != null) {
        if (left.getData() < node.getData()) {
            validateBinarySearchTree(left);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }

    Node right = node.getRight();
    if (right != null) {
        if (right.getData() > node.getData()) {
            validateBinarySearchTree(right);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }
}

score -3 · Accepted Answer

boolean isBST(Node root) {
    if (root == null) { return true; }
    return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data <= root.data) && (root.right == null || root.right.data > root.data));
}

algorithm - 二分探索木をどのように検証しますか?

33 に答える 33

Related

Reference