자바스크립트에서 트리에 키 삽입하기

새로 생성된 이진 트리에 처음 삽입하면 루트에 노드가 생성됩니다. 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 바이너리 검색 트리 속성에 따라 추가 삽입이 삽입됩니다.

코드에서 이 알고리즘을 구현하는 방법을 살펴보겠습니다.

예시

insertIter(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node; return;
   }

   let currNode = this.root;
   while (true) {
      if (data < currNode.data) {
         // Set the value here as we've reached a leaf node
         if (currNode.left === null) {
            currNode.left = node;
            break;
         } else {
            currNode = currNode.left;
         }
      } else {
         // Set the value here as we've reached a leaf node
         if (currNode.right === null) {
            currNode.right = node;
            break;
         } else {
            currNode = currNode.right;
         }
      }
   }
}

이 기능이 어떻게 작동하는지 이해합시다. 먼저 루트가 null인지 확인합니다. 그렇다면 트리가 비어 있는 경우 새 노드를 루트로 할당하면 완료됩니다. 그렇지 않은 경우 currNode 변수를 만들고 루트를 가리킵니다. 그런 다음 데이터가 currNode보다 작은지 확인하고, 그렇다면 왼쪽 자식이 null인지 확인합니다. 그렇다면 여기에 데이터를 보관하고 종료합니다. 그렇지 않으면 우리는 잎사귀에 도달할 때까지 반복하고 마침내 거기에 데이터를 배치합니다.

−

예시

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

이 함수를 재귀적으로 만들 수도 있습니다. 트리는 본질적으로 재귀적 구조이며 우리는 이 재귀 속성을 상당히 쉽게 사용할 수 있습니다. insert 의 재귀 버전을 살펴보겠습니다 −

예시

insertRec(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node;
   } else {
      insertRecHelper(this.root, node);
   }
}

재귀할 수 있는 도우미 함수를 만들어야 하지만 이를 클래스의 속성으로 노출하고 싶지 않으므로 이 함수는 클래스 정의에서 벗어납니다.

예시

function insertRecHelper(root, node) {
   if (node.data < root.data) {
      // Set the value here as we've reached a leaf node

      if (root.left === null) {
         root.left = node;
      } else {
         // Recursively call this function with the left subtree
            insertRecHelper(root.left, node);
      }
   } else {
      // Set the value here as we've reached a leaf node
      if (root.right === null) {
         root.right = node;
      } else {
         // Recursively call this function with the right subtree
         insertRecHelper(root.right, node);
      }
   }
}

−

예시

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);