트리

WooBuntu·2020년 8월 24일
자료구조자바스크립트트리
0

자바스크립트 자료구조

목록 보기
4/8


- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

트리는 부모/자식 관계에 있는 노드들로 구성된 자료 구조이다.

  • 트리의 종류

    • 트리

    • 이진 트리

    • 이진 검색 트리

    • 자가 균형 이진 검색 트리(AVL 트리)

  • 예시

이진 검색 트리

  • 모든 부모 노드는 최대 2개의 자식 노드를 갖는다.

  • 부모 노드의 왼쪽 자식은 부모 노드보다 작은 값이며, 부모 노드의 오른쪽 자식은 부모 노드보다 큰 값이다.

모든 부모 노드는 최대 2개의 자식 노드를 갖는다.

const Node = {
  init: function (val) {
    this.val = val;
    this.left = null;
    this.right = null;
  },
};

트리는 루트 노드로부터 진입한다.

const BinarySearchTree = {
  init: function () {
    this.root = null;
  },
};

insert

  • 위 그림과 같이 트리 구조를 구현하기 위해 insert함수를 사용한다고 가정해보자.
const BinarySearchTree = {
  // 앞 생략
  insert: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let currentNode = this.root;

    while (true) {
      if (val == currentNode.val) {
        return currentNode;
      }
      if (val < currentNode.val) {
        if (currentNode.left == null) {
          currentNode.left = newNode;
          return this;
        }
        currentNode = currentNode.left;
        continue;
      }

      if (val > currentNode.val) {
        if (currentNode.right == null) {
          currentNode.right = newNode;
          return this;
        }
        currentNode = currentNode.right;
        continue;
      }
    }
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

find

const BinarySearchTree = {
  // 앞 생략
  find: function (val) {
    if (!this.root) {
      return;
    }

    let currentNode = this.root;

    while (true) {
      if (val == currentNode.val) {
        return currentNode;
      }

      if (val < currentNode.val) {
        if (currentNode.left) {
          currentNode = currentNode.left;
          continue;
        }
        return;
      }

      if (val > currentNode.val) {
        if (currentNode.right) {
          currentNode = currentNode.right;
          continue;
        }
        return;
      }
    }
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(15);
bst.insert(3);
bst.insert(8);
bst.insert(13);
bst.insert(20);

이진 검색 트리의 삽입과 검색의 시간 복잡도

  • 위와 같이 균형을 이루는 이진 검색 트리의 경우, 계층이 하나 깊어질 때마다 이전 계층의 노드 수의 2배가 늘어난다.

  • 따라서 insert와 find의 시간 복잡도는 log n이 된다.

  • 하지만 위와 같이 균형을 이루지 못한 이진 검색 트리의 경우, 연결 리스트와 다를 것이 없어 insert와 find의 시간 복잡도는 최대 n까지 올라간다.

트리 순회

  • 이 절의 내용은 비단 '이진 검색 트리'에만 해당되는 내용이 아니라 모든 종류의 트리에 적용된다.

너비 우선 탐색(BFS)

재귀함수로 BFS 짜기

const BinarySearchTree = {
  // 앞 생략
  bfsByRecursion: function (queue = [this.root], visited = []) {
    if (queue.length == 0) {
      return visited;
    }
    const shifted = queue.shift();
    if (shifted.left) {
      queue.push(shifted.left);
    }
    if (shifted.right) {
      queue.push(shifted.right);
    }
    visited.push(shifted.val);
    debugger;
    return this.bfsByRecursion(queue, visited);
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

  • 이와 같이 재귀함수는 값을 반환하기 최종 값을 반환하기까지 콜스택이 계속 쌓이게 되므로 트리의 규모가 크다면 stack overflow가 발생할 수도 있다.

반복문으로 BFS 짜기

const BinarySearchTree = {
  // 앞 생략
  bfsByLoop: function () {
    const queue = [this.root];
    const visited = [];

    while (queue.length) {
      const shifted = queue.shift();
      if (shifted.left) {
        queue.push(shifted.left);
      }
      if (shifted.right) {
        queue.push(shifted.right);
      }
      visited.push(shifted.val);
      debugger;
    }
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

  • 반면, 반복문을 이용할 경우 하나의 콜스택에서 문제를 해결한다.

  • 따라서 재귀문과 반복문으로 해결이 가능한 문제라면 반복문으로 해결하는 편이 좋다.

깊이 우선 탐색(DFS)

선순위(pre-order) DFS

반복문

const BinarySearchTree = {
  // 앞 생략
  preOrderDFSByLoop: function () {
    const stack = [this.root];
    const visited = [];

    while (stack.length) {
      const popped = stack.pop();
      if (popped.right) {
        stack.push(popped.right);
      }
      if (popped.left) {
        stack.push(popped.left);
      }
      visited.push(popped.val);
      debugger;
    }
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

재귀문(내 풀이)

const BinarySearchTree = {
  // 앞 생략
  preOrderDFSByRecursive: function (stack = [this.root], visited = []) {
    if (stack.length == 0) {
      return visited;
    }
    const popped = stack.pop();
    if (popped.right) {
      stack.push(popped.right);
    }
    if (popped.left) {
      stack.push(popped.left);
    }
    visited.push(popped.val);
    // debugger;
    return this.preOrderDFSByRecursive(stack, visited);
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

  • helper함수를 쓰지 않고 재귀문으로 풀려는 시도였다.

  • 다만, 이 방식으로는 post-order와 in-order를 풀 수 없다.
    (풀 수 있겠지... 내가 모를 뿐 ㅠ)

재귀문(Colt풀이)

const BinarySearchTree = {
  // 앞 생략
  preOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      visited.push(node.val);
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);
  • 이 방식을 활용하면 아래의 post-order와 pre-order의 구현도 쉽게 할 수 있다.

후순위(post-order) DFS

const BinarySearchTree = {
  // 앞 생략
  postOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
      }
      visited.push(node.val);
    }
    traverse(this.root);
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

중순위(in-order) DFS

const BinarySearchTree = {
  // 앞 생략
  inOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
      }
      visited.push(node.val);
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

bst.insert(10);
bst.insert(6);
bst.insert(3);
bst.insert(8);
bst.insert(15);
bst.insert(20);

전체 코드

const Node = {
  init: function (val) {
    this.val = val;
    this.left = null;
    this.right = null;
  },
};

const BinarySearchTree = {
  init: function () {
    this.root = null;
  },
  insert: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let currentNode = this.root;

    while (true) {
      if (val == currentNode.val) {
        return currentNode;
      }
      if (val < currentNode.val) {
        if (currentNode.left == null) {
          currentNode.left = newNode;
          return this;
        }
        currentNode = currentNode.left;
        continue;
      }

      if (val > currentNode.val) {
        if (currentNode.right == null) {
          currentNode.right = newNode;
          return this;
        }
        currentNode = currentNode.right;
        continue;
      }
    }
  },
  find: function (val) {
    if (!this.root) {
      return;
    }

    let currentNode = this.root;

    while (true) {
      if (val == currentNode.val) {
        return currentNode;
      }

      if (val < currentNode.val) {
        if (currentNode.left) {
          currentNode = currentNode.left;
          continue;
        }
        return;
      }

      if (val > currentNode.val) {
        if (currentNode.right) {
          currentNode = currentNode.right;
          continue;
        }
        return;
      }
    }
  },
  bfsByLoop: function () {
    const queue = [this.root];
    const visited = [];

    while (queue.length) {
      const shifted = queue.shift();
      if (shifted.left) {
        queue.push(shifted.left);
      }
      if (shifted.right) {
        queue.push(shifted.right);
      }
      visited.push(shifted.val);
      debugger;
    }
    return visited;
  },
  bfsByRecursion: function (queue = [this.root], visited = []) {
    if (queue.length == 0) {
      return visited;
    }
    const shifted = queue.shift();
    if (shifted.left) {
      queue.push(shifted.left);
    }
    if (shifted.right) {
      queue.push(shifted.right);
    }
    visited.push(shifted.val);
    debugger;
    return this.bfsByRecursion(queue, visited);
  },
  preOrderDFSByLoop: function () {
    const stack = [this.root];
    const visited = [];

    while (stack.length) {
      const popped = stack.pop();
      if (popped.right) {
        stack.push(popped.right);
      }
      if (popped.left) {
        stack.push(popped.left);
      }
      visited.push(popped.val);
      debugger;
    }
    return visited;
  },
  //   preOrderDFSByRecursive: function (stack = [this.root], visited = []) {
  //     if (stack.length == 0) {
  //       return visited;
  //     }
  //     const popped = stack.pop();
  //     if (popped.right) {
  //       stack.push(popped.right);
  //     }
  //     if (popped.left) {
  //       stack.push(popped.left);
  //     }
  //     visited.push(popped.val);
  //     // debugger;
  //     return this.preOrderDFSByRecursive(stack, visited);
  //   },
  preOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      visited.push(node.val);
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return visited;
  },
  postOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
      }
      if (node.right) {
        traverse(node.right);
      }
      visited.push(node.val);
    }
    traverse(this.root);
    return visited;
  },
  inOrderDFSByRecursive: function () {
    const visited = [];
    function traverse(node) {
      if (node.left) {
        traverse(node.left);
      }
      visited.push(node.val);
      if (node.right) {
        traverse(node.right);
      }
    }
    traverse(this.root);
    return visited;
  },
};

const bst = Object.create(BinarySearchTree);

bst.init();

결론

  • BFS나 DFS나 시간복잡도는 동일하다.
    (어차피 전체 노드를 순회하니까)

  • 결국 BFS와 DFS가 차이를 보이는 부분은 공간복잡도이다.

  • 위 그림에서 깊이를 하나 내려올 때마다 큐의 길이는 2배가 된다.

  • 따라서 깊이가 조금만 깊어져도 큐의 길이는 기하급수적으로 증가해 메모리를 많이 잡아먹는다.

  • 반면, DFS에서는 가지 치는 분기점마다 재귀 함수가 호출되어 콜스택이 하나씩 추가되기 때문에 BFS에 비해 상대적으로 메모리가 크게 절약된다.

  • 반대로 위와 같은 상황에서는 BFS가 압도적으로 메모리를 적게 사용한다.

  • 큐에 언제나 1개의 원소만 존재할 것이기 때문이다.

  • 반면, DFS의 경우 재귀 함수가 노드마다 호출되기 때문에 콜스택을 잡아먹고 있다.

  • AVL트리에 대해서는 이후에 기회가 된다면 이 포스팅에 내용을 추가할 예정이다.

profile
WooBuntu
이전 포스트

스택/큐

다음 포스트

힙

0개의 댓글