15장 트리

  • 이진 트리는 자식 노드가 왼쪽과 오른쪽뿐인 트리이다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class BinaryTreeNode {
      constructor (value) {
        this.value = value;
        this.left = null;
        this.right = null;
      }
    }

    class BinaryTree {
      this._root = null;
    }
  • 트리를 순회하려면 인덱스를 사용해 트리에 접근한 다음 크기 제한에 도달할 때까지 인덱스를 증가한다
  • 선순위, 후순위, 중순위, 단계순위 순회 등이 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    // 선순위
      traversePreOrder () {
        traversePreOrderHelper(this._root);

        function traversePreOrderHelper(node) {
          if(!node) return;
          console.log(node.value);
          traversePreOrderHelper(node.left);
          traversePreOrderHelper(node.right);
        }
      }

      traversePreOrderInterative() {
        let nodeStack = [];
        nodeStack.push(this._root);

        /*
        1) 항목을 출력
        2) 오른쪽 자식을 스택에 추가
        3) 왼쪽 자식을 스택에 추가
        스택구조이므로 오른쪽을 먼저 넣고 왼쪽을 나중에 넣음 (pop으로 꺼내면 왼쪽이 먼저 처리됨)
        */
        while (nodeStack.length) {
          let node = nodeStack.pop();
          console.log(node.value);
          if(node.right) nodeStack.push(node.right);
          if(node.left) nodeStack.push(node.left);
        }
      }

    // 중순위
      traverseInOrder() {
        traverseInOrderHelper(this._root);

        function traverseInorderHelper(node) {
          if(!node) return;
          traverseInOrderHelper(node.left);
          console.log(node.value);
          traverseInOrderHelper(node.right);
        }
      }

      traverseInOrderInterative() {
        let current = this._root,
            s = [],
            done = false;
        
        while (!done) {
          // 현재 노드의 가장 왼쪽에 있는 노드로 이동
          if (current != null) {
            // 왼쪽 하위 트리를 순회하기 전에 포인터가 스택의 트리 노드를 가리키도록 함
            s.push(current);
            current = current.left
          } else {
            if(s.length) {
              current = s.pop();
              console.log(current.value);
              current = current.right;
            } else {
              done = true;
            }
          }
        }
      }

    // 후순위
      traversePostOrder() {
        traversePostOrderHelper(this._root);

        function traversePostOrderHelper(node) {
          if (node.left) 
            traversePostOrderHelper(node.left)
          if (node.right)
            traversePostOrderHelper(node.right)
          console.log(node.value);
        }
      }

      traversePostOrderInterative() {
        let s1 = [], s2 = [];
        s1.push(this._root);
        while(s1.length) {
          let node = s1.pop();
          s2.push(node)

          if (node.left) 
            s1.push(node.left);
          if (node.right) 
            s1.push(node.right);
        }
        while(s2.length) {
          let node = s2.pop();
          console.log(node.value);
        }
      }
    // 단계순위 순회
      traverseLevelOrder() {
        let root = this._root, queue = [];
        if(!root) return;
        queue.push(root);
        
        while(queue.length) {
          let temp = queue.shift();
          console.log(temp.value);
          if(temp.left) queue.push(temp.left);
          if(temp.right) queue.push(temp.right);
        }
      }
  • 리프 노드를 방문하기 전에 루트를 조사할 필요가 있는 경우 선순위 순회 를 선택
  • 리프 노드를 검색할 때 루트를 조사하느라 시간을 낭비하기 싫다면 후순위 순회 를 선택
  • 트리를 원래 순서대로 방문하고 싶은 경우에는 중순위 순회 를 선택
  • 이진 검색 트리의 경우 왼쪽 자식이 부모보다 작고 오른쪽 자식이 부모보다 크다
  • 자식이 부모 값보다 큰 노드만 있는 경우 불균형 이진 검색트리가 되고 이 트리는 완전 균형 이진 트리에 비해 복잡도가 O(log2n)에서 O(n)으로 늘어난다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    class BinarySearchTree {
      constructor () {
        this._root = null;
      }

      insert(value) {
        let thisNode = { left : null, right : null, value: value};
        if (!this._root) {
          this._root = thisNode;
        } else {
          let curRoot = this._root;
          while(true) {
            if (curRoot.value > value) {
              // 현재 노드보다 값이 작다면 왼쪽에 삽입
              if (curRoot.left != null) {
                curRoot = curRoot.left;
              } else {
                curRoot.left = thisNode;
                break;
              }
            } else if (curRoot.value < value) {
              // 현재 노드보다 값이 크면 오른쪽에 삽입
              if (curRoot.right != null) {
                curRoot = curRoot.right;
              } else {
                curRoot.right = thisNode;
                break;
              }
            } else {
              // 현재 노드와 값이 같을 경우
             break; 
            }
          } 
        }
      } // insert() end

      /*
        삭제하고자 하는 노드를 찾기 위해 트리를 순회해야 한다
        노드에 자식이 없을 경우에는 null을 반환하고 해당 노드를 삭제하면 된다
        노드에 자식이 하나 있다면 현재 자식을 반환하고 해당 자식이 위 단계로 올라가서 부모를 대체해야 한다
        노드에 자식이 두개 있다면 왼쪽 하위 트리의 최대치를 찾거나 오른쪽 하위 트리 최소치를 찾아서 해당 노드를 대체한다
      */
      remove (value) {
        return deleteRecursively(this._root, value);

        function deleteRecursively(root, value) {
          if (!root) {
            return null;
          } else if (value < root.value) {
            root.left = deleteRecursively(root.left, value);
          } else if (value > root.value) {
            root.right = deleteRecursively(root.right, value);
          } else {
            if (!root.left && !root.right) { 
              return null;
            } else if (!root.left) {
              root = root.right;
              return root;
            } else if (!root.right) {
              root = root.left;
              return root;
            } else {
              let temp = findMin(root.right);
              root.value = temp.value;
              root.right = deleteRecursively(root.right, temp.value)
              return root;
            }
          } 
          return root;
        }

        function findMin(root) { // 이진트리에서 가장 왼쪽에 있는 값은 최소값이다
          while(root.left) {
            root = root.left;
          }
           return root;
        }
      } // remove() end

      findNode(value) {
        let curRoot = this._root,
            found = false;

        while (curRoot) {
          if (curRoot.value > value) {
            curRoot = curRoot.left
          } else if (curRoot.value < value) {
            curRoot= curRoot.right
          } else {
            found = true;
            break;
          }
        }
        return found;
      }
    }
  • AVL 트리는 스스로 균형을 잡는 이진 검색 트리로, 트리의 높이를 최소로 유지하면서 검색과 삽입, 삭제 연산의 시간 복잡도 O(log2(n))을 보장한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    class AVLTree {
      constructor (value) {
        this.left = null;
        this.right = null;
        this.value = value;
        this.depth = 1;
      }
      
      setDepthBasedOnChildren() {
        if (this.node === null) this.depth = 1;

        if (this.left !== null) this.depth = this.left.depth + 1;

        if (this.right !== null && this.depth <= this.right.depth) {
          this.depth = this.right.depth + 1;
        }
      }
      // 삽입 이후에 균형을 유지하기 위해 자식들을 회전
      rotateRR() {
        let valueBefore = this.value;
        let leftBefore = this.left;
        this.value = this.right.value;

        this.left = this.right;
        this.right - this.right.right;
        this.left.right = this.left.left;
        this.left.left = leftBefore;
        this.left.value = valueBefore;

        this.left.setDepthBasedOnChildren();
        this.setDepthBasedOnChildren();
      }

      rotateLL() {
        let valueBefore = this.value;
        let rightBefore = this.right;
        this.value = this.left.value;

        this.right = this.left;
        this.left - this.left.left;
        this.right.left = this.right.right
        this.right.right = rightBefore;
        this.right.value = valueBefore;

        this.right.setDepthBasedOnChildren();
        this.setDepthBasedOnChildren();
      }

      // 만약 한번 회전을 하고 나서도 AVL 트리가 여전히 불균형이라면 완전한 균형을 위해 두 번 회전해야 함 
      balance() {
        let ldepth = this.left === null ? 0 : this.left.depth;
        let rdepth = this.right === null ? 0 : this.right.depth;
        
        if (ldepth > rdepth + 1) {
          let lldepth = this.left === null ? 0 : this.left.depth;
          let lrdepth = this.right === null ? 0 : this.right.depth;

          if (lldepth < lrdepth) {
            // LR 회전은 왼쪽 자식의 RR회전과 현재 노드의 LL회전으로 구성된다
            this.left.rotateRR();
          }
          this.rotateLL();
        } else if (ldepth + 1 < rdepth) {
          let rrdepth = this.right.right === null ? 0 : this.right.right.depth;
          let rldepth = this.right.left === null ? 0 : this.right.left.depth;

          if (rldepth > rrdepth) {
            // RR회전은 오른쪽 자식의 LL회전과 현재 노드의 RR회전으로 구성됨
            this.right.rotateLL();
          }
          this.rotateRR();
        }
      } // balance() end

      insert (value) {
        let childInserted = false;
        if (value === this.value) {
          return false;
        } else if (value < this.value) {
          if (this.left === null) {
            this.left = new AVLTree(value);
            childInserted = true;
          } else {
            childInserted = this.left.insert(value);
            if (childInserted === true) this.balance();
          }
        } else if (value > this.value) {
          if (this.right === null) {
            this.right = new AVLTree(value);
            childInserted = true;
          } else {
            childInserted = this.right.insert(value);
            if(childInserted === true) this.balance();
          }
        }
        if (childInserted === true) this.setDepthBasedOnChildren();
        return childInserted;
      } // insert() end

      remove(value) {
        return deleteRecursively(this, value);

        function deleteRecursively(root, value) {
          if (!root) {
            return null;
          } else if (value < root.value) {
            root.left = deleteRecursively(root.left, value);
          } else if (value > root.value) {
            root.right = deleteRecursively(root.right, value);
          } else {
            if (!root.left && !root.right) {
              return null;
            } else if (!root.left) {
              root = root.right;
              return root;
            } else if (!root.right) {
              root = root.left;
              return root;
            } else {
              let temp = findMin(root.right);
              root.value = temp.value;
              root.right = deleteRecursively(root.right, temp.value);
              return root;
            }
          }
          root.setDepthBasedOnChildren();
          return root;
        }

        function findMin(root) {
          while (root.left) root = root.left;
          return root;
        }
      } // remove() end
    }
  • 이진 검색 트리는 검색에는 매우 뛰어나지만 삽입과 삭제의 연산 시간 복잡도가 O(log2(n))으로 느림
  • 트리가 불균형이 되면 모든 연산이 O(n)이 되니 이를 개선하기 위해 AVL 트리와 같은 자가 균형 트리를 사용해야 한다
  • 주어진 이진트리에서 두 개의 노드의 가장 가까운 공통 조상 찾기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function findLowestCommonAncester(root, value1, value2) {
      function findLowestCommonAncesterHelper(root, value, value2) {
        if (!root) return;
        if (Math.max(value1, value2) < root.value)
          return findLowestCommonAncesterHelper(root.left, value1, value2);
        if (Math.min(value1, value2) > root.value)
          return findLowestCommonAncesterHeleper(root.right, value1, value2);
        return root.value;
      }
      return findLowestCommonAncesterHelper(root, value1, value2);
    }
  • 루트의 n번째 거리에 있는 노드 출력하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    const printKthLevels = (root, k) => {
      let arrayKth = [], queue = [];

      if (!root) return;

      queue.push([root, 0]);

      while(queue.length) {
        let tuple = queue.shift(),
            temp = tuple[0];
            height = tuple[1];
        if (height === k) {
          arrayKth.push(temp.value);
        }
        if (temp.left) 
          queue.push([temp.left, height+1]);
        if (temp.right)
          queue.push([temp.right, height+1]);
      }
      console.log(arrayKth);
    }
  • 이진 트리가 다른 트리의 하위 트리인지 확인하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    const isSameTree = (root1, root2) => {
      if (root1 === null && root2 === null) return true;
      if (root1 === null || root2 === null) return false;

      return root1.value === root2.value 
        && isSameTree(root1.left, root2.left) 
        && isSameTree(root1.right, root2.right)
    }

    const checkIfSubTree = (root, subtree) => {
      let queue = [], counter = 0;

      if(!root) return;

      queue.push(root);

      while (queue.length) {
        let temp = queue.shift();
        if (temp.data === subtree.data === isSameTree(temp, subtree)) {
          return true
        }
        if (temp.left)
          queue.push(temp.left);
        if (temp.right)
          queue.push(temp.right);
      }
      return false;
    }
  • 트리가 다른 트리와 대칭인지 확인하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /*
    1. 두 트리의 루트 노드 키가 동일해야 함
    2. 트리 a의 루트 왼쪽 하위 트리와 트리 b의 오른쪽 하위 트리가 대칭
    3. 트리 a의 오른쪽 하위 트리와 트리 b의 왼쪽 하위 트리가 대칭
    */

    const isMirrorTrees = (tree1, tree2) => {
      // 기저의 경우 둘 다 빈 상태
      if (!tree1 && !tree2) return true;
      // 둘 중 하나가 빈 상태라면 대칭이 아님
      if (!tree1 || !tree2) return false;

    // 한쪽 트리의 왼쪽 하위 트리와 다른 트리의 오른쪽 하위 트리를 전달
      let checkLeftwithRight = isMirrorTrees(tree1.left, tree2.right),
          checkRightwithLeft = isMirrorTrees(tree2.right, tree1.left);
      return tree1.value === tree2.value && checkLeftwithRight && checkRightwithLeft;
    }