이진 검색 트리를 어떻게 검증합니까?

이진 검색 트리를 어떻게 검증합니까?

---

이진 검색 트리 유효성 검사로 알려진 인터뷰 연습 문제를 여기에서 읽었습니다.

정확히 어떻게 작동합니까? 이진 검색 트리의 유효성을 검사 할 때 무엇을 찾고 있습니까? 기본 검색 트리를 작성했지만이 개념에 대해 들어 본 적이 없습니다.

---

사실 그것은 모두가 인터뷰에서하는 실수입니다.

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입니다. 그렇지 않으면 그렇지 않습니다.

---

이진 검색 트리를 "검증"한다는 것은 실제로 왼쪽에 작은 항목이 모두 있고 오른쪽에 큰 항목이 있는지 확인하는 것을 의미합니다. 기본적으로 이진 트리가 이진 검색 트리 인지 확인하는 것 입니다.

---

내가 찾은 최고의 솔루션은 O (n)이며 추가 공간을 사용하지 않습니다. inorder traversal과 비슷하지만 배열에 저장 한 다음 정렬되었는지 확인하는 대신 정적 변수를 가져 와서 inorder traversing 동안 배열이 정렬되었는지 확인할 수 있습니다.

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;
}

---

inorder traversal을 사용하는 반복 솔루션.

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;
}

---

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)))

---

BST의 순차 순회는 비 감소 시퀀스이므로이 속성을 사용하여 이진 트리가 BST인지 여부를 판단 할 수 있습니다. Morris traversal을 사용 하고 pre노드를 유지하면 O (n) 시간과 O (1) 공간 복잡도 에서 솔루션을 얻을 수 있습니다. 내 코드는 다음과 같습니다.

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;
}

---

여기 파이썬으로 된 내 대답은 해커 랭크 웹 사이트 에서 해결되고 잘 테스트 된 모든 코너 케이스가 있습니다.

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right)

def checkLeftSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data > subTree.data \
        and checkLeftSubTree(root, subTree.left) \ 
        and checkLeftSubTree(root, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left) \
        and checkRightSubTree(subTree, subTree.right)

def checkRightSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data < subTree.data \ 
        and checkRightSubTree(root, subTree.left) \
        and checkRightSubTree(root, subTree.right) \
        and checkRightSubTree(subTree, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left)

---

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;
}

---

"불변을 먼저 정의하는 것이 더 낫습니다. 여기서 불변은-순회 순회에서 BST의 두 순차 요소는 모양이 엄격하게 증가하는 순서 여야합니다 (동일 할 수 없으며 항상 순서대로 증가). 순회). 따라서 솔루션은 마지막으로 방문한 노드를 기억하고 현재 노드를 마지막으로 방문한 노드와 '<'(또는 '>')를 비교하는 단순한 순회 순회 일 수 있습니다. "

---

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)
            )
        )
    );
}

---

나는 최근에 전화 인터뷰에서이 질문을 받았으며 내가 가져야 할 것보다 더 많은 어려움을 겪었습니다. 저는 자식 노드의 최소값과 최대 값을 추적하려고했지만 인터뷰의 압력을 받아 다른 사례에 대해 뇌를 감쌀 수 없었습니다.

어젯밤에 잠들면서 생각해 본 결과, 순회 동안 방문한 마지막 노드를 추적하는 것만 큼 간단하다는 것을 깨달았습니다. 자바 :

public <T extends Comparable<T>> boolean isBst(TreeNode<T> root) {
    return isBst(root, null);
}

private <T extends Comparable<T>> boolean isBst(TreeNode<T> node, TreeNode<T> prev) {
    if (node == null)
        return true;

    if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 ))
        return isBst(node.right, node);

    return false;
}

---

Java에서 두 하위 트리에서 동일한 값을 가진 노드 허용 :

public boolean isValid(Node node) {
    return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValid(Node node, int minLimit, int maxLimit) {
    if (node == null)
        return true;
    return minLimit <= node.value && node.value <= maxLimit
            && isValid(node.left, minLimit, node.value)
            && isValid(node.right, node.value, maxLimit);
}

---

// 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;
}

---

주어진 BT가 모든 데이터 유형에 대해 BST인지 확인하려면 아래 접근 방식을 사용해야합니다. 1. inorder traversal을 사용하여 리프 노드 끝까지 재귀 함수를 호출합니다. 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;
}

---

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;
}

잘 작동 :)

---

재귀는 쉽지만 반복적 인 접근 방식이 더 낫습니다. 위에 하나의 반복적 인 버전이 있지만 필요 이상으로 너무 복잡합니다. 어디에서나 찾을 수 있는 최고의 솔루션 은 다음과 같습니다 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;
}

---

inorder Traversal BST를 사용하는 솔루션을 작성하고 노드가 공간 O(1)과 시간에 대한 순서를 늘리는 지 확인합니다 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;

}

---

다음은 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;
  }
}

---

재귀 솔루션 :

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)

    }

---

반복적 인 솔루션.

private static boolean checkBst(bst node) {

    Stack<bst> s = new Stack<bst>();
    bst temp;
    while(node!=null){
        s.push(node);
        node=node.left;
    }
    while (!s.isEmpty()){
        node = s.pop();
        System.out.println(node.val);
        temp = node;
        if(node.right!=null){
            node = node.right;
            while(node!=null)
            {
                //Checking if the current value is lesser than the previous value and ancestor.
                if(node.val < temp.val)
                    return false;
                if(!s.isEmpty())
                    if(node.val>s.peek().val)
                        return false;
                s.push(node);
                if(node!=null)
                node=node.left;
            }
        }
    }
    return true;
}

---

이것은 중복에 대해 작동합니다.

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

---

http://www.jiuzhang.com/solutions/validate-binary-search-tree/에서 영감을 얻었습니다 .

두 가지 일반적인 솔루션이 있습니다 : 순회 및 나누기 && 정복.

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);
    }
}

---

짧막 한 농담

bool is_bst(Node *root, int from, int to) {
   return (root == NULL) ? true :
     root->val >= from && root->val <= to &&
     is_bst(root->left, from, root->val) &&
     is_bst(root->right, root->val, to);
}

그래도 꽤 긴 줄.

---

다음은 sedgewick의 알고리즘 클래스의 Java 솔루션입니다. 여기 에서 전체 BST 구현을 확인 하십시오.

몇 가지 설명을 추가했습니다.

private boolean isBST() {
    return isBST(root, null, null);

}

private boolean isBST(Node x, Key min, Key max) {
    if (x == null) return true;
    // when checking right subtree min is key of x's parent
    if (min != null && x.key.compareTo(min) <= 0) return false;
    // when checking left subtree, max is key of x's parent
    if (max != null && x.key.compareTo(max) >= 0) return false;
    // check left subtree and right subtree
    return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);

}

---

• 이 iterative함수는 주어진 트리가 이진 검색 트리인지 반복적으로 확인합니다.
• 이 recurse함수는 주어진 트리가 이진 검색 트리인지 여부를 반복적으로 확인합니다.
• 에서 iterative기능 나는 BST를 확인하기위한 BFS를 사용합니다.
• 에서 recurse기능 나는 BST를 확인하기위한 DFS를 사용합니다.
• 두 솔루션 모두 시간 복잡성이 있습니다. O(n)
• iterative솔루션은 솔루션보다 이점 recurse이 있으며 iterative솔루션은 조기 중지를 수행합니다.
• 심지어 recurse기능은 글로벌 플래그 값에 의해 초기 정지에 최적화 할 수 있습니다.
• 두 솔루션의 아이디어는 왼쪽 자식이 루트 노드 인 부모 노드의 값에 대해 무한대의 범위 내에 있어야한다는 것입니다.
• 오른쪽 자식은 루트 노드 인 부모 노드의 값에 대해 + 무한 범위 내에 있어야합니다.

• 그리고 범위 내에서 현재 노드의 값을 계속 비교하십시오. 노드의 값이 범위에 없으면 False를 반환합니다.

  class Solution:
      def isValidBST(self, root):
          """
          :type root: TreeNode
          :rtype: bool
          """
          return self.iterative(root)
          # return self.recurse(root, float("inf"), float("-inf"))
  
      def iterative(self, root):
          if not root:
              return True
  
          level = [[root, -float("inf"), float("inf")]]
  
          while level:
              next_level = []
  
              for element in level:
                  node, min_val, max_val = element
                  if min_val<node.val<max_val:
                      if node.left:
                          next_level.append([node.left, min_val, node.val])
                      if node.right:
                          next_level.append([node.right, node.val, max_val])
                  else:
                      return False
              level = next_level
  
          return True
  
      def recurse(self, root, maxi, mini):
          if root is None:
              return True
  
          if root.val < mini or root.val > maxi:
              return False
  
          return self.recurse(root.left, root.val-1, mini) and self.recurse(root.right, maxi, root.val+1)
  

---

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))

---

다음은 추가 공간을 사용하지 않는 반복적 인 솔루션입니다.

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;
    }
}

---

 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");
        }
    }
}

---

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));
}

---

다음은 JavaScript로 작성된 재귀 솔루션입니다.

function isBST(tree) {
  if (tree === null) return true;

  if (tree.left != undefined && tree.left.value > tree.value) {
    return false;
  }

  if (tree.right != undefined && tree.right.value <= tree.value) {
    return false;
  }

  return isBST(tree.left) && isBST(tree.right);
}

참고URL : https://stackoverflow.com/questions/499995/how-do-you-validate-a-binary-search-tree