algorithm/자료구조

insert : 이진탐색트리(Binary Search Tree, BST)

yongfront 2024. 2. 25. 10:31
반응형
SMALL

이진탐색트리(Binary Search Tree, BST)의 insert 함수를 구현하는 것은 자료구조의 기본을 이해하는 좋은 방법입니다.

이진탐색트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큰 특성을 가지고 있습니다. 이러한 성질을 이용하여 데이터를 정렬된 상태로 저장할 수 있으며, 검색, 삽입, 삭제 작업을 효율적으로 수행할 수 있습니다.

아래는 자바스크립트로 이진탐색트리를 구현하고, insert 메소드를 추가하는 간단한 예제입니다.

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function(node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null; // 동일한 값은 트리에 추가하지 않음
        }
      };
      return searchTree(node);
    }
  }

  // 이후에 다른 메소드(예: 검색, 삭제)를 구현할 수 있습니다.
}

이 예제에서 BST 클래스는 이진탐색트리를 표현하며, Node 클래스는 트리의 각 노드를 표현합니다. BST 클래스 내에 insert 메소드는 새로운 데이터를 적절한 위치에 삽입하는 역할을 합니다. insert 메소드는 재귀적인 방식으로 작동하며, 삽입할 데이터가 현재 노드의 데이터보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동하여 삽입 위치를 찾습니다. 삽입할 위치의 자식 노드가 **null**이면 새 노드를 생성하여 연결하고, 그렇지 않으면 계속해서 탐색을 진행합니다.

재귀는 insert 메소드 내에서 searchTree 함수를 통해 동작합니다. searchTree 함수는 insert 메소드의 내부에 정의된 함수로, insert 메소드가 삽입하려는 데이터를 트리에 추가할 적절한 위치를 찾기 위해 자기 자신을 호출합니다. 이 재귀적 호출은 삽입하려는 데이터가 현재 노드의 데이터보다 작거나 클 때, 즉, 트리의 왼쪽이나 오른쪽으로 이동해야 할 때 발생합니다.

여기서 재귀가 발생하는 부분을 자세히 살펴보겠습니다:

  1. 데이터가 현재 노드의 데이터보다 작을 때:
    • 현재 노드의 왼쪽 자식이 null이면, 새로운 노드를 왼쪽 자식으로 할당하고 재귀는 종료됩니다.
    • 만약 왼쪽 자식이 null이 아니라면, searchTree 함수는 현재 노드의 왼쪽 자식을 새로운 현재 노드로 하여 자기 자신을 다시 호출합니다. 이 과정은 적절한 삽입 위치를 찾을 때까지 계속됩니다.
  2. 데이터가 현재 노드의 데이터보다 클 때:
    • 현재 노드의 오른쪽 자식이 null이면, 새로운 노드를 오른쪽 자식으로 할당하고 재귀는 종료됩니다.
    • 만약 오른쪽 자식이 null이 아니라면, searchTree 함수는 현재 노드의 오른쪽 자식을 새로운 현재 노드로 하여 자기 자신을 다시 호출합니다. 이 과정 역시 적절한 삽입 위치를 찾을 때까지 계속됩니다.

재귀 호출의 종료 조건은 삽입할 위치의 자식 노드가 null이 되는 경우입니다. 이때 새로운 Node 인스턴스가 생성되어 삽입 위치에 할당되며, 재귀 호출이 종료됩니다.

이러한 재귀적 접근 방식은 트리의 깊이에 따라 호출 스택이 증가하게 되므로, 매우 깊은 트리에서는 스택 오버플로를 유발할 수 있습니다. 하지만, 평균적인 경우와 균형 잡힌 트리에서는 효율적으로 작동합니다.

이 코드를 사용하면 간단한 이진탐색트리를 생성하고, 데이터를 삽입할 수 있습니다. 추가로 검색, 삭제 등의 기능을 구현하여 이진탐색트리의 다양한 연산을 지원할 수 있습니다.

728x90
반응형
LIST