JavaScript에서 이진 검색 트리 구현

트리 데이터 구조

트리는 일부 에지로 연결된 노드의 모음입니다. 일반적으로 트리의 각 노드는 일부 데이터와 해당 하위 항목에 대한 참조를 보유합니다.

이진 검색 트리

이진 검색 트리는 왼쪽에 값이 작은 노드를 저장하고 오른쪽에 값이 높은 노드를 저장하는 이진 트리입니다.

예를 들어, 유효한 BST의 시각적 표현은 -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

이제 JavaScript 언어로 자체 바이너리 검색 트리를 구현해 보겠습니다.

1단계:노드 클래스

이 클래스는 BST의 다양한 지점에 있는 단일 노드를 나타냅니다. BST는 위에서 설명한 규칙에 따라 배치된 데이터 및 하위 참조를 저장하는 노드의 모음일 뿐입니다.

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

새로운 Node 인스턴스를 생성하기 위해 우리는 이 클래스를 약간의 데이터와 함께 다음과 같이 호출할 수 있습니다 -

const newNode = new Node(23);

이렇게 하면 데이터가 23으로 설정되고 왼쪽 및 오른쪽 참조가 모두 null인 새 노드 인스턴스가 생성됩니다.

2단계:이진 검색 트리 클래스:

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

그러면 트리 인스턴스를 만들기 위해 new 키워드로 호출할 수 있는 이진 검색 트리 클래스가 생성됩니다.

이제 기본 작업을 마쳤으므로 올바른 위치에 새 노드를 삽입하는 방법으로 넘어갑니다(정의에 설명된 BST 규칙에 따라).

3단계:BST에 노드 삽입

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

예시

전체 이진 검색 트리 코드:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);