Javascript를 이용한 tree 구현

Trees

tree는 관계 기반의 자료구조로, 계층형 구조를 전문적으로 나타냅니다. linked list와 마찬가지로 node는 data와 pointer를 가지고 있습니다.
tree의 최상단을 'root node'라 하며 아래로 연결된 node는 'child node'입니다.
tree의 흔한 타입으로 'binary search tree'가 있으며 binary tree는 보다 쉽게 저장된 데이터를 찾도록 합니다.

binary tree의 rule

1. root node의 왼쪽 node는 root node의 데이터보다 작아야 합니다.
2. root node의 오른쪽 node는 root node의 데이터보다 커야 합니다.
3. root node의 child node들도 1,2의 rule을 따라야 합니다.
4. 똑같은 value를 가진 node들이 없어야 합니다.
   
   

binary tree의 Advantages

1. 계층형 데이터를 저장시 용이
2. 동적인 size를 지님
3. 빠른 insert / delete 작업
4. binary tree에서 삽입된 node는 즉시 정렬됨
   
   

binary tree의 Disadvantages

1. node들을 재배열시 느림
2. child node는 상위 node의 정보를 갖고있지 않음
3. binary tree는 hash table보다 빠르지 않음
4. binary tree가 균형잡힌 하위 트리를 갖고잊지 않다면
   선형검색(scanning all elements)로 전락할 수 있음.
   
   

tree의 적용

• file 위치와 같이 계층형 데이터 저장시 사용
• 데이터 검색 및 정렬시 적합
  
  

binary tree 구현

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

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

  add(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) {
            //left에 함수 있을 시 재귀 함수 적용
            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);
    }
  }

  remove(data) {
    //제거할 data의 파라미터를 두번째에 놓았다.
    const removeNode = function (node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // node has no children ~ 밑에 뿌리가 없는 노드
        if (node.left == null && node.right == null) {
          return null;
        }
        // node has no left child  ~ left는 없는 경우 node right가 해당 삭제 데이터에 들어간다.
        if (node.left == null) {
          return node.right;
        }
        // node has no right child 
        if (node.right == null) {
          return node.left;
        }
        // node has two children
        var tempNode = node.right;
        //tempNode는 삭제할 node의 right가 되고
        while (tempNode.left !== null) {
          tempNode = tempNode.left; //다시 node right의 left가 된다.
        }
        node.data = tempNode.data; //그리고 삭제 node에는 위의 tempnode가 들어가게된다.
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    this.root = removeNode(this.root, data);
  }
}

const bst = new BST();

bst.add(9);
bst.add(4);
bst.add(17);
bst.add(3);
bst.add(6);
bst.add(22);
bst.add(5);
bst.add(7);
bst.add(20);
//console.log(bst)
//bst.remove(4)
console.log(bst)