logo

TechCodeview

이진 검색 트리 소개 - 데이터 구조 및 알고리즘 튜토리얼

이진 검색 트리 데이터를 정렬된 방식으로 구성하고 저장하기 위해 컴퓨터 과학에서 사용되는 데이터 구조입니다. 이진 검색 트리는 이진 트리의 모든 속성을 따릅니다. 왼쪽 자식에는 부모 노드보다 작은 값이 포함되어 있으며 오른쪽 하위에는 상위 노드보다 큰 값이 포함되어 있습니다. 이 계층 구조는 효율적인 작업을 가능하게 합니다. 수색 , 삽입 , 그리고 삭제 트리에 저장된 데이터에 대한 작업

이진 검색 트리




로마 숫자 1부터 100까지

내용의 테이블

이진 검색 트리란 무엇입니까?

이진 검색 트리(BST) 특별한 유형이다 이진 트리 노드의 왼쪽 자식은 노드 값보다 작은 값을 갖고 오른쪽 자식은 노드 값보다 큰 값을 갖습니다. 이 속성을 BST 속성이라고 하며, 트리 내의 요소를 효율적으로 검색, 삽입, 삭제할 수 있게 해줍니다.



이진 검색 트리의 속성:

  • 노드의 왼쪽 하위 트리에는 해당 노드의 키보다 작은 키를 가진 노드만 포함됩니다.
  • 노드의 오른쪽 하위 트리에는 해당 노드의 키보다 큰 키를 가진 노드만 포함됩니다.
  • 이는 루트 왼쪽에 있는 모든 것이 루트 값보다 작고 루트 오른쪽에 있는 모든 것이 루트 값보다 크다는 것을 의미합니다. 이러한 수행으로 인해 이진 검색이 매우 쉽습니다.
  • 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 합니다.
  • 중복된 노드가 없어야 합니다(BST는 다른 처리 방식에 따라 중복된 값을 가질 수 있음).

이진 검색 트리에서 중복 값 처리:

  • 우리는 전체적으로 일관된 프로세스를 따라야 합니다. 즉, 중복 값을 왼쪽에 저장하거나 중복 값을 루트 오른쪽에 저장하되 접근 방식과 일관성을 유지해야 합니다.

이진 검색 트리의 기본 작업:

1. BST에서 노드 검색:

BST에서 검색한다는 것은 데이터 구조에서 특정 노드를 찾는 것을 의미합니다. 이진 검색 트리에서는 특정 순서로 인해 노드 검색이 쉽습니다. 이진 검색 트리에서 노드를 검색하는 단계는 다음과 같습니다.

  1. 먼저, 검색할 요소를 트리의 루트 요소와 비교합니다.
    • 루트가 대상 요소와 일치하면 노드의 위치를 ​​반환합니다.
    • 일치하지 않으면 항목이 루트 요소보다 작은지 확인하고, 루트 요소보다 작으면 왼쪽 하위 트리로 이동합니다.
    • 루트 요소보다 크면 오른쪽 하위 트리로 이동합니다.
  2. 일치하는 항목을 찾을 때까지 위 절차를 반복적으로 반복합니다.
  3. 요소가 트리에 없거나 존재하지 않으면 NULL을 반환합니다.

이제 예제를 사용하여 이진 트리 검색을 이해해 보겠습니다.

아래에는 BST가 제공되며 요소 6을 검색해야 합니다.




암호:

다음은 BST에서 검색을 구현한 것입니다.

C++ 
// C++ function to search a given key in a given BST #include  using namespace std; struct node {  int key;  struct node *left, *right; }; // A utility function to create a new BST node struct node* newNode(int item) {  struct node* temp  = new struct node;  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // 삽입하는 유틸리티 함수 // BST에 주어진 키를 가진 새 노드 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL ) newNode(키)를 반환합니다.  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->키) 노드->왼쪽 = insert(노드->왼쪽, 키);  else if (key> node->key) node->right = insert(node->right, key);  // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST에서 키를 검색하는 유틸리티 함수 struct node* search(struct node* root, int key) root->key == key) return root;  // 키가 루트의 키보다 큽니다. if (root->key< key)  return search(root->오른쪽, 키);  // 키가 루트의 키보다 작습니다. return search(root->left, key);>
씨 
// C function to search a given key in a given BST #include  #include  struct node {  int key;  struct node *left, *right; }; // A utility function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // 삽입하는 유틸리티 함수 // BST에 주어진 키를 가진 새 노드 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL ) newNode(키)를 반환합니다.  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->키) 노드->왼쪽 = insert(노드->왼쪽, 키);  else if (key> node->key) node->right = insert(node->right, key);  // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST에서 키를 검색하는 유틸리티 함수 struct node* search(struct node* root, int key)>
자바 
// Java program to search a given key in a given BST class Node {  int key;  Node left, right;  public Node(int item) {  key = item;  left = right = null;  } } class BinarySearchTree {  Node root;  // Constructor  BinarySearchTree() {  root = null;  }  // A utility function to insert  // a new node with given key in BST  Node insert(Node node, int key) {  // If the tree is empty, return a new node  if (node == null) {  node = new Node(key);  return node;  }  // Otherwise, recur down the tree  if (key < node.key)  node.left = insert(node.left, key);  else if (key>node.key) node.right = insert(node.right, 키);  // (변경되지 않은) 노드 포인터를 반환합니다. return node;  } // BST 노드 검색에서 키를 검색하는 유틸리티 함수(Node root, int key) // 기본 사례: 루트가 null이거나 키가 루트에 존재합니다. if (root == null>
파이썬 
# Python3 function to search a given key in a given BST class Node: # Constructor to create a new node def __init__(self, key): self.key = key self.left = None self.right = None # A utility function to insert # a new node with the given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # (변경되지 않은) 노드 포인터를 반환 return node # BST에서 키를 검색하는 유틸리티 함수 def search(root, key): # 기본 사례: root is 루트가 None이거나 root.key == key: return root인 경우 루트에 null 또는 키가 존재합니다. # root.key인 경우 키가 루트의 키보다 큽니다.< key: return search(root.right, key) # Key is smaller than root's key return search(root.left, key)>
자바스크립트 
// Javascript function to search a given key in a given BST class Node { constructor(key) {  this.key = key;  this.left = null;  this.right = null; } } // A utility function to insert // a new node with given key in BST function insert(node, key) { // If the tree is empty, return a new node if (node === null) {  return new Node(key); } // Otherwise, recur down the tree if (key < node.key) {  node.left = insert(node.left, key); } else if (key>node.key) { node.right = insert(node.right, 키); } // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST 함수에서 키를 검색하는 유틸리티 함수 search(root, key) { // 기본 사례: 루트가 null이거나 키가 루트에 존재합니다. if (root === null || root.key === key ) { 루트를 반환합니다. } // 키가 루트의 키보다 큽니다. if (root.key< key) {  return search(root.right, key); } // Key is smaller than root's key return search(root.left, key); }>


2. BST에 노드 삽입 :

새 키는 항상 리프에 삽입됩니다. 루트부터 리프 노드까지 키 검색을 시작합니다. 리프 노드가 발견되면 새 노드가 리프 노드의 하위로 추가됩니다.


암호:

다음은 이진 검색 트리에 단일 노드 삽입을 구현한 것입니다.

C++ 
// Given Node Structure struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; }>
씨 
// Given Node Structure struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; }>
자바 
class GFG {  // Given Node Structure  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static node insert(node node, int key)  {  // If the tree is empty, return a new node  if (node == null)  return newNode(key);  // Otherwise, recur down the tree  if (key < node.key) {  node.left = insert(node.left, key);  }  else if (key>node.key) { node.right = insert(node.right, 키);  } // 노드를 반환합니다. return node;  } }>
파이썬3 
# Given Node Structure class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # 노드 포인터를 반환 return node>
자바스크립트 
// Given Node Structure class Node {  constructor(key){  this.key = key;  this.left = null;  this.right = null;  } } // Function to insert a new node with // given key in BST function insert(node, key) {    // If the tree is empty, return a new node  if (node == null)  return new Node(key);  // Otherwise, recur down the tree  if (key < node.key)  {  node.left = insert(node.left, key);  }  else if (key>node.key) { node.right = insert(node.right, 키);  } // 노드 포인터를 반환합니다. return node; }>

시간 복잡도: O(N), 여기서 N은 BST의 노드 수입니다.
보조 공간: 오(1)

삼. BST 노드 삭제 :

BST에서 특정 키를 가진 노드를 삭제하고 새로운 BST를 반환하는데 사용됩니다.

노드 삭제에 대한 다양한 시나리오:

삭제할 노드는 리프 노드입니다. :

간단합니다. 그냥 무효화하면 됩니다.

d1

삭제할 노드에 하위 노드가 1개 있습니다. :

노드를 하위 노드로 교체하면 됩니다.

파일

삭제할 노드에 하위 항목이 2개 있습니다. :

여기서 우리는 노드 삭제는 결과 트리가 BST의 속성을 따르는 방식입니다. 비결은 노드의 중위 계승자를 찾는 것입니다. 중위 계승자의 내용을 노드에 복사하고 중위 계승자를 삭제합니다.

d3

BST 노드를 삭제하는 동안 다음 사항에 주의하세요.

  1. 삭제할 노드를 대체할 것이 무엇인지 파악해야 합니다.
  2. 기존 트리 구조에 대한 중단을 최소화하고 싶습니다.
  3. 삭제된 노드 왼쪽 또는 오른쪽 하위 트리에서 대체 노드를 가져올 수 있습니다.
  4. 왼쪽 하위 트리에서 if를 취하는 경우 왼쪽 하위 트리에서 가장 큰 값을 취해야 합니다.
  5. 오른쪽 하위 트리에서 if를 취하는 경우 오른쪽 하위 트리에서 가장 작은 값을 가져와야 합니다.

암호:

왼쪽 조인 vs 오른쪽 조인

다음은 BST에서 삭제를 구현한 것입니다.

C++ 
// C++ program to delete // a node of BST // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; } // 해당 트리에서 찾은 최소 키 값을 가진 노드를 반환하는 함수 // struct node* minValueNode(struct node* node) { struct node* current = node;  // 가장 왼쪽 리프를 찾기 위해 루프를 돌립니다. while (current && current->left != NULL) current = current->left;  현재 반환; } // 키를 삭제하고 // 새 루트를 반환하는 함수 struct node* deleteNode(struct node* root, int key) { // 기본 사례 if (root == NULL) return root;  // 삭제할 키가 // 루트의 키보다 작으면 // 왼쪽 하위 트리에 놓입니다.< root->key) { root->left = deleteNode(root->left, key);  } // 삭제할 키가 // 루트의 키보다 크면 // 오른쪽 하위 트리에 놓입니다. else if (key> root->key) { root->right = deleteNode(root-> 오른쪽, 키);  } // 키가 루트의 키와 동일하면 // 삭제될 노드입니다. else { // 자식이 하나만 있는 노드 // 또는 자식이 없는 노드 if (root->left == NULL) { 구조체 노드* 임시 = 루트->오른쪽;  무료(루트);  복귀온도;  } else if (루트->오른쪽 == NULL) { 구조체 노드* 임시 = 루트->왼쪽;  무료(루트);  복귀온도;  } // 두 개의 자식이 있는 노드: // 중위 계승자(오른쪽 하위 트리에서 가장 작은 //)를 가져옵니다. struct node* temp = minValueNode(root->right);  // 중위 계승자의 // 내용을 이 노드에 복사합니다. root->key = temp->key;  // 중위 후속자 삭제 root->right = deleteNode(root->right, temp->key);  } 루트를 반환합니다; }>
씨 
// C program to delete // a node of BST // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; } // 해당 트리에서 찾은 최소 키 값을 가진 노드를 반환하는 함수 // struct node* minValueNode(struct node* node) { struct node* current = node;  // 가장 왼쪽 리프를 찾기 위해 루프를 돌립니다. while (current && current->left != NULL) current = current->left;  반환 전류; } // 키를 삭제하고 // 새 루트를 반환하는 함수 struct node* deleteNode(struct node* root, int key) { // 기본 사례 if (root == NULL) return root;  // 삭제할 키가 // 루트의 키보다 작으면 // 왼쪽 하위 트리에 위치합니다.< root->key) { root->left = deleteNode(root->left, key);  } // 삭제할 키가 // 루트의 키보다 크면 // 오른쪽 하위 트리에 놓입니다. else if (key> root->key) { root->right = deleteNode(root-> 오른쪽, 키);  } // 키가 루트의 키와 동일하면 // 삭제될 노드입니다. else { // 자식이 하나만 있는 노드 // 또는 자식이 없는 노드 if (root->left == NULL) { 구조체 노드* 임시 = 루트->오른쪽;  무료(루트);  복귀온도;  } else if (루트->오른쪽 == NULL) { 구조체 노드* 임시 = 루트->왼쪽;  무료(루트);  복귀온도;  } // 두 개의 자식이 있는 노드: // 중위 계승자(오른쪽 하위 트리에서 가장 작은 //)를 가져옵니다. struct node* temp = minValueNode(root->right);  // 중위 계승자의 // 내용을 이 노드에 복사합니다. root->key = temp->key;  // 중위 후속자 삭제 root->right = deleteNode(root->right, temp->key);  } 루트를 반환합니다; }>
자바 
// Java program for Delete a Node of BST class GFG {  // Given Node node  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static node insert(node node, int key)  {  // If the tree is empty, return a new node  if (node == null)  return newNode(key);  // Otherwise, recur down the tree  if (key < node.key) {  node.left = insert(node.left, key);  }  else if (key>node.key) { node.right = insert(node.right, 키);  } // 노드를 반환합니다. return node;  } // 해당 트리에서 발견된 // 최소 키 값을 가진 노드를 반환하는 함수 static node minValueNode(node ​​node) { node current = node;  // 가장 왼쪽 리프를 찾기 위해 루프를 돌립니다. while (current != null && current.left != null) current = current.left;  반환 전류;  } // 키를 삭제하고 // 새 루트 정적 노드를 반환하는 함수 deleteNode(node ​​root, int key) { // 기본 사례 if (root == null) return root;  // 삭제할 키가 // 루트의 키보다 작으면 // 왼쪽 하위 트리에 위치합니다.< root.key) {  root.left = deleteNode(root.left, key);  }  // If the key to be deleted is  // greater than the root's key,  // then it lies in right subtree  else if (key>root.key) { root.right = deleteNode(root.right, key);  } // 키가 루트의 키와 동일하면 // 삭제될 노드입니다. else { // 자식이 하나만 있거나 // 자식이 없는 노드 if (root.left == null) { 노드 온도 = root.right;  복귀온도;  } else if (root.right == null) { 노드 임시 = root.left;  복귀온도;  } // 두 개의 자식이 있는 노드: // 중위 계승자(오른쪽 하위 트리에서 가장 작은 //)를 가져옵니다. node temp = minValueNode(root.right);  // 중위 계승자의 // 내용을 이 노드에 복사합니다. root.key = temp.key;  // 중위 계승자 삭제 root.right = deleteNode(root.right, temp.key);  } 루트를 반환합니다;  }>
파이썬 
# Python program to delete a node of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to insert a new node with # given key in BST def insert(root, key): # If the tree is empty, return a new node if root is None: return Node(key) # Otherwise, recur down the tree if key < root.key: root.left = insert(root.left, key) elif key>root.key: root.right = insert(root.right, key) # 노드 포인터를 반환 return root # BST의 중위 순회를 수행하는 함수 def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # 해당 트리에서 찾은 최소 키 값을 가진 노드를 반환하는 함수 # def minValueNode(node): current = node # 루프 다운하여 가장 왼쪽 리프를 찾는 동안 current and current.left is not None: current = current.left return current # 키를 삭제하고 # 새 루트를 반환하는 함수 def deleteNode(root, key): # base Case if root is None: return root # 키가 될 경우 삭제된 키는 # 루트의 키보다 작습니다. # 키가 있으면 왼쪽 하위 트리에 놓입니다.< root.key: root.left = deleteNode(root.left, key) # If the key to be deleted is # greater than the root's key, # then it lies in right subtree elif key>root.key: root.right = deleteNode(root.right, key) # 키가 루트의 키와 같으면 # 삭제될 노드입니다. else: # 자식이 하나만 있거나 # 자식이 없는 노드입니다. if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # 두 개의 자식이 있는 노드: # 중위 계승자(가장 작은 #를 가져옵니다. 오른쪽 하위 트리) temp = minValueNode(root.right) # 중위 후속 항목의 # 내용을 이 노드에 복사합니다. root.key = temp.key # 중위 후속 항목을 삭제합니다. root.right = deleteNode(root.right, temp.key) 루트 반환>

4. 순회(BST의 중순회) :

BST(이진 검색 트리)의 경우 중위 순회는 노드를 감소하지 않는 순서로 제공합니다. 먼저 왼쪽 자식을 방문하고 그 다음 루트, 오른쪽 자식을 방문합니다.

다음은 이진 검색 트리의 중위 순회를 수행하는 방법을 구현한 것입니다.

C++ 
// C++ program to implement // inorder traversal of BST #include  using namespace std; // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; } // BST의 중위 순회를 수행하는 함수 void inorder(struct node* root) { if (root != NULL) { inorder(root->left);  시합<< ' ' << root->열쇠;  inorder(루트->오른쪽);  } } // 드라이버 코드 int main() { /* 다음 BST를 생성하겠습니다. 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // BST 루트 생성 = insert(root, 50);  insert(루트, 30);  insert(루트, 20);  insert(루트, 40);  insert(루트, 70);  insert(루트, 60);  insert(루트, 80);  // 함수 호출 inorder(root);  0을 반환합니다. } // 이 코드는 shivanisinghss2110이 제공한 것입니다.>
씨 
// C program to implement // inorder traversal of BST #include  #include  // Given Node node struct node {  int key;  struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) {  struct node* temp  = (struct node*)malloc(  sizeof(struct node));  temp->키 = 아이템;  온도->왼쪽 = 온도->오른쪽 = NULL;  복귀온도; } // BST에 // 주어진 키를 사용하여 새 노드를 삽입하는 함수 struct node* insert(struct node* node, int key) { // 트리가 비어 있으면 새 노드를 반환합니다. if (node ​​== NULL) return newNode(키);  // 그렇지 않으면, 트리 아래로 반복됩니다. if (key< node->key) { 노드->왼쪽 = insert(노드->왼쪽, 키);  } else if (key> node->key) { node->right = insert(node->right, key);  } // 노드 포인터를 반환합니다. return node; } // BST의 중위 순회를 수행하는 함수 void inorder(struct node* root) { if (root != NULL) { inorder(root->left);  printf('%d ', 루트->키);  inorder(루트->오른쪽);  } } // 드라이버 코드 int main() { /* 다음 BST를 생성하겠습니다. 50 /  30 70 /  /  20 40 60 80 */ struct node* root = NULL;  // BST 루트 생성 = insert(root, 50);  insert(루트, 30);  insert(루트, 20);  insert(루트, 40);  insert(루트, 70);  insert(루트, 60);  insert(루트, 80);  // 함수 호출 inorder(root);  0을 반환합니다. }>
자바 
import java.io.*; // Java program for Inorder Traversal class GFG {  // Given Node node  static class node {  int key;  node left, right;  };  // Function to create a new BST node  static node newNode(int item)  {  node temp = new node();  temp.key = item;  temp.left = temp.right = null;  return temp;  }  // Function to insert a new node with  // given key in BST  static node insert(node node, int key)  {  // If the tree is empty, return a new node  if (node == null)  return newNode(key);  // Otherwise, recur down the tree  if (key < node.key) {  node.left = insert(node.left, key);  }  else if (key>node.key) { node.right = insert(node.right, 키);  } // 노드를 반환합니다. return node;  } // BST의 중위 순회를 수행하는 함수 static void inorder(node ​​root) { if (root != null) { inorder(root.left);  System.out.print(' ' + root.key);  중위(root.right);  } } // 드라이버 코드 public static void main(String[] args) { /* 다음 BST를 생성하겠습니다. 50 /  30 70 /  /  20 40 60 80 */ node root = null;  // 값 50 삽입 root = insert(root, 50);  // 값 30 삽입 insert(root, 30);  // 값 20 삽입 insert(root, 20);  // 값 40 삽입 insert(root, 40);  // 값 70 삽입 insert(root, 70);  // 값 60 삽입 insert(root, 60);  // 값 80 삽입 insert(root, 80);  // BST inorder(root)를 인쇄합니다.  } } // 이 코드는 abhijitjadhav1998에 의해 제공되었습니다.>
파이썬3 
# Python program to implement # inorder traversal of BST # Given Node node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to create a new BST node def newNode(item): temp = Node(item) temp.key = item temp.left = temp.right = None return temp # Function to insert a new node with # given key in BST def insert(node, key): # If the tree is empty, return a new node if node is None: return newNode(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # 노드 포인터를 반환 return node # BST의 중위 순회를 수행하는 함수 def inorder(root): if root: inorder(root.left) print(root. key, end=' ') inorder(root.right) # 드라이버 코드 if __name__ == '__main__': # 다음 BST를 생성하겠습니다 # 50 # /  # 30 70 # /  /  # 20 40 60 80 root = 없음 # BST 만들기 root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root , 80) # 함수 호출 inorder(root) # 이 코드는 japmeet01이 기여했습니다.>
산출 
 20 30 40 50 60 70 80>

시간 복잡도: O(N), 여기서 N은 BST의 노드 수입니다.
보조 공간: 오(1)

BST의 응용:

  • 그래프 알고리즘: BST는 최소 스패닝 트리 알고리즘과 같은 그래프 알고리즘을 구현하는 데 사용될 수 있습니다.
  • 우선순위 대기열: BST는 우선순위 큐를 구현하는 데 사용할 수 있습니다. 여기서 우선순위가 가장 높은 요소는 트리의 루트에 있고 우선순위가 낮은 요소는 하위 트리에 저장됩니다.
  • 자체 균형 이진 검색 트리: BST는 AVL 트리, 레드-블랙 트리와 같은 자체 균형 데이터 구조로 사용될 수 있습니다.
  • 데이터 저장 및 검색: BST는 로그 시간 내에 특정 레코드를 검색할 수 있는 데이터베이스와 같이 데이터를 신속하게 저장하고 검색하는 데 사용할 수 있습니다.

장점:

  • 빠른 검색: BST에서 특정 값을 검색하는 경우 평균 시간 복잡도는 O(log n)입니다. 여기서 n은 트리의 노드 수입니다. 이는 최악의 경우 시간 복잡도가 O(n)인 배열이나 연결 목록에서 요소를 검색하는 것보다 훨씬 빠릅니다.
  • 순회: BST는 순서대로 탐색할 수 있으며 왼쪽 하위 트리, 루트 및 오른쪽 하위 트리를 방문합니다. 이는 데이터 세트를 정렬하는 데 사용할 수 있습니다.
  • 공간 효율성: BST는 배열 및 연결 목록과 달리 중복 정보를 저장하지 않으므로 공간 효율적입니다.

단점:

  • 비뚤어진 나무: 트리가 왜곡되면 검색, 삽입 및 삭제 작업의 시간 복잡도는 O(log n)이 아닌 O(n)이 되어 트리를 비효율적으로 만들 수 있습니다.
  • 추가 시간 필요: 자체 균형 트리에는 삽입 및 삭제 작업 중에 균형을 유지하는 데 추가 시간이 필요합니다.
  • 능률: BST는 공간을 낭비하므로 중복이 많은 데이터 세트에는 효율적이지 않습니다.

FAQ(자주 묻는 질문)이진 검색 트리에서:

1. 이진 검색 트리란 무엇입니까?

이진 검색 트리(BST)는 다음과 같습니다. 왼쪽 하위 트리의 모든 노드가 루트보다 작고 오른쪽 하위 트리의 모든 노드가 루트보다 큰 값을 갖는 이진 트리 . 이진 검색 트리의 속성은 재귀적입니다. 어떤 노드를 루트로 간주하면 이러한 속성은 true로 유지됩니다.

2. 이진 검색 트리 작업이란 무엇입니까?

이진 검색 트리에는 주요 세 가지 작업이 있습니다. 1. 삽입, 2. 삭제, 3. 검색. 그 속성으로 인해 이진 검색 트리의 모든 요소를 ​​검색하는 것이 효율적입니다.

3. 이진 검색 트리와 AVL 트리란 무엇입니까?

이진 검색 트리 : BST(이진 검색 트리)는 왼쪽 하위 트리의 모든 노드가 루트보다 작고 오른쪽 하위 트리의 모든 노드가 루트보다 큰 값을 갖는 이진 트리입니다.

AVL 트리 : 자체 균형을 맞추고 자동으로 회전하는 이진 검색 트리(BST)를 AVL 트리라고 합니다.

4. 이진 검색 트리의 용도는 무엇입니까?

이진 검색 트리는 다음과 같은 추상 데이터 유형을 구현하는 데 사용될 수 있습니다. 동적 세트, 조회 테이블 및 우선순위 큐, 그리고 사용 정렬 알고리즘 예를 들어 트리 정렬.

5. 이진 검색 트리와 이진 트리의 차이점은 무엇입니까?

이진 검색 트리는 요소를 정렬하기 위해 어떤 순서를 따르는 트리인 반면, 이진 트리는 어떤 순서도 따르지 않습니다.

관련 기사:

  • BST의 적용
  • 이진 검색 트리의 응용, 장점 및 단점
  • 이진 검색 트리(BST)에 삽입
  • 이진 검색 트리(BST)에서 검색
  • 이진 검색 트리(BST)에서의 삭제