Data Structure 공부 중 이해한 부분을 정리합니다. 각 자료구조의 구현은 JavaScript를 이용하였습니다.

Tree

트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다.

Tree 구조에서 용어

• A, B, C, D 등 트리의 구성요소를 노드(node) 라고 합니다.
• 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다.
• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 깊이(depth) 라고 합니다.
• 같은 부모를 가지면서 같은 깊이에 존재하는 노드들은 형제(sibling) 관계에 있습니다.
• 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다.
• 노드와 노드를 잇는 선을 edge(또는 link, branch) 라고 합니다.
• 자식이 없는 노드는 leaf 라고 합니다.
• 루트 노드에서 가장 깊숙히 있는 노드의 깊이를 높이(height)라고 합니다.
• 레벨은 루트노드에서 해당 노드까지 노드의 갯수를 의미하며 깊이 + 1의 값을 가집니다.

트리와 그래프는 얼핏 비슷하지만 트리는 계층구조를 가진다는 점에서 그래프와 차이를 가집니다!

Tree 구현 💻

구현한 메소드

• insertNode(value) - 트리에 노드를 추가합니다.
• contains(value) - 트리에 해당 노드가 존재하는지 여부를 반환합니다.

Pesuedo Code

• insertNode(value) - 새로운 노드를 생성해 Tree의 children에 push합니다.
• contains(value) - 해당 value가 존재하는지 Tree를 탐색합니다. 노드가 chidren이 존재하면 재귀를 사용하는데, 이때 찾는 value가 존재하면 true를 return하고 모든 노드를 탐색했음에도 해당하는 value가 없다면 false를 return 합니다.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    let node = new TreeNode(value);
    this.children.push(node);
  }

  contains(value) {
    let result = false;

    function recursion(node) {
      if (node.value === value) {
        result = true;
        return ;
      }
      for (let i of node.children) {
        recursion(i);
      }
    }

    recursion(this);

    return result;
  }
}

Binary Search Tree

이진탐색 트리는 최대 2개의 자식만 가지는 트리입니다. 이진탐색트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재합니다. 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값과 같거나 큰 값이 존재합니다.

Tree 순회 방식

이진 탐색 트리를 순회하는 방법은 크게
깊이 우선 탐색 (DFS, Depth-First Search)과
너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘이 존재합니다.

+)
전위 순회(Preorder Traversal): 부모 → 좌 → 우
중위 순회(Inorder Traversal): 좌 → 부모 → 우
후위 순회(Postorder Traversal): 좌 → 우 → 부모

Binary Tree의 종류

이진트리는 다양한 종류가 있습니다.(이진 탐색트리가 아닌 이진트리입니다!)

• 정 이진 트리(Full Binary Tree) - 리프노드를 제외한 모든 노드가 자식노드가 2개 있는 트리를 의미합니다.
• 완전 이진 트리(Complete Binary Tree) - 완전 이진트리는 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리를 의미합니다.
• 포화 이진 트리(Perfect Binay Tree) -마지막 레벨까지 모든 노드가 가득 차있는 이진트리를 의미합니다.

Binary Search Tree 구현 💻

이 구현에서는 깊이우선탐색, 중위순회를 사용하였습니다.

구현한 메소드

• insert(value) - 이진 탐색 트리에 노드를 추가합니다.
• contains(value) - 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환합니다.
• inorder(callback) - 이진 탐색 트리를 중위순회 합니다.

Pesuedo Code

• insert(value) - 이진탐색트리에 노드를 삽입할 때에는 현재 노드의 value보다 작으면 left, 크거나 같으면 right로 삽입 해줘야 합니다. 그러나 이미 left나 right가 값이 있다면 다시 탐색을 해줘야하는데 이때 재귀를 사용합니다.

• contains(value) - 이도 역시 재귀를 통해 만듭니다. 재귀의 탈출 조건은 들어오는 node.value와 찾고자 하는 value가 같으면 탈출합니다. 이때 true를 return해줘야 합니다. 만약 일치하지 않으나 node가 left나 right가 있으면 재귀를 통해 탐색합니다.

• inorder(callback) - 중위 순회는 좌, 부모, 우 순으로 순회하는 것 이므로, 만약 왼쪽 서브트리가 존재한다면 마지막까지 내려가고 callback(this.value)하고 다음 오른쪽 서브트리를 순회합니다.

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insert(value) {
    let node = new BinarySearchTreeNode(value);
    
    function recursion(ele){
      if(ele.value > node.value){
        if(ele.left){
          recursion(ele.left);
        }else{
          ele.left = node;
        }
      }else if(ele.value <= node.value){
        if(ele.right){
          recursion(ele.right);
        }else{
          ele.right = node;
        }
      }
    }
    recursion(this);
  }

  contains(value) {
    let result = false;

    let recursion = (ele) =>{
      if(ele.value === value){
        result = true;
        return ;
      }else if(ele.left && ele.value > value){
        recursion(ele.left);
      }else if(ele.right && ele.value < value){
        recursion(ele.right);
      }
    }
    recursion(this);
    return result;
    
  }

  inorder(callback) {
    if(this.left){
      this.left.inorder(callback);
    }
    
    callback(this.value);
    
    if(this.right){
      this.right.inorder(callback);
    }
  }
}