(Javascript) [자료구조] Tree(BinarySearch)

Tree

• 관계 기반의 자료구조로, 계층형 구조를 전문적으로 나타낸다
• Tree의 최상단을 root node라고 부르며 아래에 연결된 node는 child node

class BinaryNode {
        constructor(data) {
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
      class BinarySearchTree {
        constructor(data) {
          this.root = null;
        }
        insert(data) {
          if (!this.root) {
            this.root = new BinaryNode(data);
            return;
          }
          let node = this.root;
          while (true) {
            if (node.data > data) {
              if (node.left) {
                node = node.left;
              } else {
                node.left = new BinaryNode(data);
                return;
              }
            } else if (node.data < data) {
              if (node.right) {
                node = node.right;
              } else {
                node.right = new BinaryNode(data);
                return;
              }
            } else return;
          }
        }
        remove(data, node = this.root) {
          if (!this.root) return;
          if (node.data > data) {
            if (node.left) {
              node.left = this.remove(data, node.left);
            }
          } else if (node.data < data) {
            if (node.right) {
              node.right = this.remove(data, node.right);
            }
          } else {
            if (!node.left && !node.right) {
              if (node === this.root) this.root = undefined;
              return undefined;
            } else if (!node.left) {
              if (node === this.root) this.root = node.right;
              return node.right;
            } else if (!node.right) {
              if (node === this.root) this.root = node.left;
              return node.left;
            } else {
              let tempNode = node.right;
              while (tempNode.left) {
                tempNode = tempNode.left;
              }
              node.data = tempNode.data;
              node.right = this.remove(tempNode.data, node.right);
            }
          }
        }
      }

• Insert 메서드
  • 만약 현재 root가 없다면 현재 루트에 데이터를 매개변수로 하는 BinaryNode를 생성
  • 현재 root가 있다면 node라는 변수에 초기화하고 입력한 데이터가 node의 데이터보다 작으면서 node의 왼쪽이 있으면 node의 왼쪽을 node에 재정의.
    node의 왼쪽이 없으면 새로운 BinaryNode를 생성
  • 반대로 입력한 데이터가 node의 데이터보다 크다면 오른쪽 확인 후 생성
• Remove 메서드
  • 지울 데이터와 node에 대한 매개변수를 받는 remove메서드.
  • node 매개변수가 없으면 root로 정의
    만약 root가 없으면 함수 탈출, 노드의 데이터가 지울 데이터보다 크면 노드의 왼쪽을 확인해서 있으면 노드의 왼쪽을 기준점으로 다시 remove메서드를 호출
    반대로 지울 데이터가 더 크면 노드의 오른쪽으로 기준점을 바꾸고 다시 remove 메서드 호출
  • 노드의 데이터가 지울 데이터라면 일단 노드의 왼쪽과 오른쪽이 없는지 확인. 둘 다 없고 그 노드가 root라면 undefined라고 정의하고 아니면 undefined를 반환하여 종료
  • 둘 중 왼쪽이 없으면 오른쪽을 반환하고, 반대로 오른쪽이 없으면 왼쪽을 반환
  • 둘 다 있으면 노드의 오른쪽을 임시로 tempNode에 정의하고 그 왼쪽이 없을 때까지 tempNode의 왼쪽으로 내려가서 그 데이터를 현 노드의 데이터로 정의. 그러면 tempNode의 데이터가 반복이므로 tempNode의 데이터를 지울 데이터로 넣고 현 노드의 오른쪽을 기준으로 remove 메서드를 재 호출 한다