TUTORIAL · Data Structure

이진 검색 트리 확인

주어진 이진 트리가 이진 검색 트리인지 확인하는 방법.

작성자 Harshit Jindal게시일 2021-03-12업데이트 2023-10-12

이진 트리는 비선형 데이터 구조입니다. 각 노드에는 최대 두 개의 자식이 있기 때문에 이진 트리라고합니다. 이 아이들을 왼쪽 아이들과 오른쪽 아이들이라고 부릅니다. 이진 트리가 BST가 되려면 다음 속성을 충족해야합니다.

  • 왼쪽 하위 트리의 모든 노드가 루트 노드보다 작습니다.
  • 오른쪽 하위 트리의 모든 노드가 루트 노드보다 큽니다.
  • 왼쪽 및 오른쪽 하위 트리도 이진 검색 트리 여야합니다.

이진 트리가 이진 검색 트리인지 확인하는 알고리즘

알고리즘 1

이 접근 방식에서는 모든 노드를 하위 트리의 루트로 간주하여 왼쪽 하위 트리에 루트 값보다 큰 요소가 포함되어 있는지, 오른쪽 하위 트리에 루트 값보다 작은 요소가 포함되어 있는지 확인합니다. 최대 및 최소 요소를 찾으려면getMin()및getMax()라는 두 개의 개별 함수를 사용해야합니다.

getMin()

  • temp를root로 초기화합니다.
  • temp에left가있는 동안 다음을 수행합니다.
    • temp를temp->left로 설정합니다. 즉, 가장 작은 요소를 찾으려면 왼쪽으로 이동합니다.
  • 하위 트리 내의 최소값으로temp->val을 반환합니다.

getMax()

  • temp를root로 초기화합니다.
  • temp에right가있는 동안 다음을 수행합니다.
    • temp를temp->right로 설정합니다. 즉, 가장 큰 요소를 찾으려면 오른쪽으로 이동합니다.
  • temp->val을 하위 트리 내의 최대 값으로 반환합니다.

isBST(root)

  • root가NULL이면true를 반환합니다.
  • getMax(root->left)를 호출하여 왼쪽 하위 트리에서 최대 요소maxm을 찾습니다.
  • getMin(root->right)를 호출하여 오른쪽 하위 트리에서 최소 요소minm을 찾습니다.
  • 루트 요소가maxm보다 작거나minm보다 크면 false를 반환합니다.
  • isBST(root->left)및isBST(root->right)를 호출하여 모든 노드를 재귀 적으로 확인합니다. 두 재귀 호출이 모두 true를 반환하면 트리는 BST이고 그렇지 않으면 false를 반환합니다.

위의 알고리즘은 트리가 BST인지 아닌지를 알려주지 만 매우 느린 지 여부를 알려줍니다. 함수getMin()및getMax()는O(n)의 최악의 시간 복잡도를 가지며n노드에 대해 호출되어 총 시간 복잡도를 O(n2).

알고리즘 2 :

이 알고리즘은 반복 계산을 수행하지 않음으로써 이전 알고리즘을 향상시킵니다. 모든 노드에 대해getMin()및getMax()라고하는 이전 접근 방식입니다. 이 접근 방식은 노드를 통과 할 때 허용되는 최소 및 최대 값을 추적함으로써 위의 접근 방식을 개선합니다.

isBST(root)

  • 두 변수min을INT_MIN으로,max를INT_MAX로 초기화합니다.
  • isBST(root, min, max)를 호출합니다.

isBST(루트, 최소, 최대)

  • root가NULL이면true를 반환합니다.
  • min>root->data가 BST 속성을 위반하면 false를 반환합니다.
  • max<root->data이면 BST 속성을 위반하면 false를 반환합니다.
  • isBST(root->left, min, root->data-1)를 호출하여 왼쪽 하위 트리를 재귀 적으로 확인합니다 (인수가 유효한 값을 변경함에 따라min및root->data-1전달). 왼쪽 하위 트리의 BST 범위) 및isBST(root->right, root->data + 1, max)를 호출하여 오른쪽 하위 트리를 선택합니다 (인수로root->data + 1및max전달). 오른쪽 하위 트리의 BST 범위).
  • 두 재귀 호출이 모두true를 반환하면 트리는 BST이고true를 반환합니다.

이 알고리즘의 시간 복잡도는O(n)이며 이는 이전 방법에 비해 상당히 개선 된 것입니다.

알고리즘 3 :

이 알고리즘은 위의 알고리즘에서INT_MIN및INT_MAX를l및r두 개의 포인터로 대체하여 사용하지 않도록합니다.

isBST(root)

  • 두 노드l및r을NULL로 초기화합니다.
  • isBST(root, l, r)를 호출합니다. (오버로드 된 함수 호출)

isBST(루트, l, r)

  • root가NULL이면true를 반환합니다.
  • l이NULL이 아니고l->data> =root->data가 아니면 BST 속성이 위반되면 false를 반환합니다.
  • r이NULL이 아니고r->data<=root->data가 아니면 BST 속성이 위반되면 false를 반환합니다.
  • isBST(root->left, left, root)(루트를 세 번째 인수로 전달하면 하위 트리의 최소값 제한이 변경됨)를 호출하여 왼쪽 하위 트리를 재귀 적으로 확인하고isBST(root)를 호출하여 오른쪽 하위 트리를 재귀 적으로 확인합니다. ->오른쪽, 루트, 오른쪽)(두 번째 인수로 루트를 전달하면 하위 트리의 최대 값 제한이 변경됨).
  • 두 재귀 호출이 모두true를 반환하면 트리는 BST이고true를 반환합니다.

알고리즘 4 :

이진 검색 트리의 inorder traversal은 정렬 된 순서로 요소를 반환합니다. 이 속성을 사용하여 이진 트리가 BST인지 확인할 수 있습니다. inorder traversal의 모든 요소가 오름차순이 아니면 주어진 트리는 이진 검색 트리가 아닙니다.

isBST(root)

  • 변수prev를INT_MIN으로 초기화합니다. prev는 현재 노드가prev보다 크므로 정렬 된 순서를 따르는 지 확인하는 데 사용됩니다.
  • isBST(root, prev)를 호출합니다. (오버로드 된 함수 호출).

isBST(루트, 이전)

  • root가NULL이면true를 반환합니다.
  • isBST(root->left, prev)로 왼쪽 서브 트리를 재귀 적으로 확인합니다. false를 반환하면 false를 반환합니다.
  • root->data<=prev인 경우. 오름차순이 위반되었습니다. false를 반환합니다.
  • 이전->데이터를루트->데이터로 업데이트합니다.
  • isBST(root->right, prev)로 오른쪽 서브 트리를 재귀 적으로 확인합니다. false를 반환하면 false를 반환합니다.
  • 그렇지 않으면 true를 반환합니다.

이진 트리를 확인하는 알고리즘의 구현이 이진 검색 트리입니다

알고리즘 1

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
int getMin(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

알고리즘 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

알고리즘 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

알고리즘 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

복잡성 분석

시간 복잡성

  • 평균 사례

주어진 이진 트리가 BST인지 여부를 확인하려면 모든n노드를 통과해야합니다. 속성을 무시하는 단일 노드는 트리가 BST가 아닌 것으로 이어지기 때문입니다. 따라서 시간 복잡도는 [Big Theta] :O(n)의 순서입니다.

  • 베스트 케이스

최상의 경우 시간 복잡도는O(n)순서입니다. 평균 케이스 시간 복잡성과 동일합니다.

  • 최악의 경우

최악의 시간 복잡도는O(n)의 순서입니다. 최상의 경우 시간 복잡성과 동일합니다.

공간 복잡성

알고리즘의 공간 복잡성은 재귀 호출에 필요한 추가 공간으로 인해O(n)입니다.

작성자 소개

Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

작성자 프로필 보기
LinkedIn