트리(Tree)란?

트리는 나뭇가지가 나뉘어 퍼져 나가는 형태의 자료 구조이다.

위의 이미지 처럼 구조가 나무를 뒤집어 놓은 모양이라 하여 트리라고 부른다.

그래프 자료구조의 특수한 형태(계층구조를 가진 그래프)로 보기도 한다 (그래프 문서 참고)

트리는 부모노드-자식노드로 계층구조를 추상화하며, 정보를 쉽게 검색하기 위해 저장할때 유용한 구조이다.

트리는 가계도, 회사조직도 같은 계층구조(hierarchical structure)를 추상화한 자료구조로서,
정보를 쉽게 검색하기 위해 저장할때 유용한 구조이다.

트리는 부모-자식 관계를 가지는 노드들로 구성되어 있으며, 각 노드는 한 개의 부모 노드와 여러 개의 자식 노드를 가질 수 있다.

컴퓨터 과학에서는 이진 트리(binary tree)가 주로 활용된다.

특히 컴퓨터 과학에서 주로 많이 활용되는 트리는 이진 트리(binary tree)이다.

이진 트리는 최대 2개의 자식노드만 가질 수 있도록 제한된 트리인데, 노드의 삽입, 조회, 삭제를 효과적으로 수행할 수 있기 때문이다.

이진트리를 NEXT 포인터를 2개가진 단방향 리스트로 보기도 한다.

따라서 여기서도 트리는 기본적으로 이진 트리임을 전제로 이야기하기로 한다.

트리 관련 용어 및 개념

노드 Node

트리를 구성하는 각 요소를 의미한다.
KEY, LEFT포인터, RIGHT포인터로 구성되어 있다.

루트 Root

최상위 노드 (부모 노드가 없다)

리프 Leaf

자식 노드가 없는 노드

간선 Edge

노드간의 연결 관계

서브 트리 Sub Tree

트리를 구성하는 부분 트리

깊이 Depth

루트에서 특정 노드에 도달하기까지의 경로의 길이

높이 Height

최대 깊이

레벨 Level

루트로부터의 내려오는 깊이 단계(층)를 표현.
루트는 레벨 0이고 아래로 내려갈 수록 1층씩 증가한다.

트리 순회 Traversal

트리의 모든 노드를 방문해서 각 노드마다 특정 작업을 수행하는 것을 의미한다.

어느 노드부터 방문할지 결정하는 기준에 따라 중위, 전위, 후위 순회로 나뉜다.

중위 순회(in-order traverse)

왼쪽 자식 → 자기 자신 → 오른쪽 자식 순으로 순회한다.
트리 정렬시 사용된다.

전위 순회(pre-order traverse)

자기 자신 → 왼쪽 자식 → 오른쪽 자식 순으로 순회한다.
구조화된 문서 출력시 사용된다.

후위 순회(post-order traverse)

왼쪽 자식 → 오른쪽 자식 → 자기 자신 순으로 순회한다.
디렉토리와 하위 디렉토리 파일 용량을 계산할때 사용된다.

균형트리 Balanced Tree

뿌리로부터 모든 잎까지의 거리가 거의 같은(차이가 최대1) 트리를 의미한다.

완전 이진 트리 Complete Binary Tree

이진 트리이면서, 마지막 레벨을 제외한 모든 레벨의 노드가 빠짐 없이 채워져있어야 한다.
마지막 레벨은 왼쪽 노드들부터 채워져 있어야한다.
완전 이진 트리는 배열을 사용해 효율적으로 표현할 수 있다.

인터페이스

insert(key) - 노드를 추가한다.
search(key) - 노드가 있는지 확인한다.
remove(key) - 노드를 삭제한다.
inOrderTraverse(callback) - 중위 순회를 수행한다.
preOrderTraverse(callback) - 전위 순회를 수행한다.
postOrderTraverse(callback) - 후위 순회를 수행한다.

구현 - JavaScript에서의 트리

이진 탐색 트리가 아닌 일반 이진 트리라 검색/삽입/삭제가 효율적이지 못하다.

class BinaryTreeNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

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

  insert(key) {
    const node = new BinaryTreeNode(key);

    if (!this.root) {
      this.root = node;
    } else {
      insertNode(this.root, node);
    }

    function insertNode(node, newNode) {
      if (!node) {
        return;
      }

      if (!node.left) {
        node.left = newNode;
      } else if (!node.right) {
        node.right = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    }
  }

  search(key) {
    if (!this.root) {
      return false;
    }

    return searchNode(this.root, key);

    function searchNode(node, key) {
      if (!node) {
        return false;
      }

      if (node.key === key) {
        return true;
      }

      if (searchNode(node.left, key)) {
        return true;
      }

      if (searchNode(node.right, key)) {
        return true;
      }

      return false;
    }
  }

  remove(key) {
    if (!this.root) {
      return;
    }

    this.root = removeNode(this.root, key);

    function removeNode(node, key) {
      if (!node) {
        return null;
      }

      if (node.key === key) {
        if (!node.left && !node.right) {
          node = null;
          return node;
        }

        if (!node.left) {
          node = node.right;
          return node;
        } else if (!node.right) {
          node = node.left;
          return node;
        }

        if (node.left && node.right) {
          let leafNode = findRightmostDeepestLeaf(node);
          const tempKey = leafNode.key;
          removeNode(node, leafNode.key);

          node.key = tempKey;

          return node;
        }
      } else {
        node.left = removeNode(node.left, key);
        node.right = removeNode(node.right, key);
        return node;
      }
    }

    function findRightmostDeepestLeaf(node) {
      return findRightmostDeepestLeafNode(node);

      function findRightmostDeepestLeafNode(node) {
        if (!node) {
          return;
        }

        if (node.right) {
          return findRightmostDeepestLeafNode(node.right);
        }

        if (node.left) {
          return findRightmostDeepestLeafNode(node.left);
        }

        return node;
      }
    }
  }

  inOrderTraverse(callback) {
    if (!this.root) {
      return;
    }

    inOrderTraverseNode(this.root, callback);

    function inOrderTraverseNode(node, callback) {
      if (!node) {
        return;
      }

      inOrderTraverseNode(node.left, callback);
      callback(node.key);
      inOrderTraverseNode(node.right, callback);
    }
  }

  preOrderTraverse(callback) {
    if (!this.root) {
      return;
    }

    preOrderTraverseNode(this.root, callback);

    function preOrderTraverseNode(node, callback) {
      if (!node) {
        return;
      }

      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  }

  postOrderTraverse(callback) {
    if (!this.root) {
      return;
    }

    postOrderTraverseNode(this.root, callback);

    function postOrderTraverseNode(node, callback) {
      if (!node) {
        return;
      }

      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
}

// Test
it("BinaryTree 클래스는 잘 동작한다.", () => {
  const tree = new BinaryTree();
  tree.insert("쿠스");
  tree.insert("톰");
  tree.insert("막달레나");
  tree.insert("사와디캅");
  tree.insert("맥베스");

  expect(tree.search("쿠스")).toEqual(true);
  expect(tree.search("톰")).toEqual(true);
  expect(tree.search("막달레나")).toEqual(true);
  expect(tree.search("사와디캅")).toEqual(true);
  expect(tree.search("와우")).toEqual(false);

  tree.remove("쿠스");
  expect(tree.search("쿠스")).toEqual(false);
  expect(tree.search("톰")).toEqual(true);
  expect(tree.search("막달레나")).toEqual(true);
  expect(tree.search("사와디캅")).toEqual(true);

  tree.remove("톰");
  expect(tree.search("톰")).toEqual(false);
  expect(tree.search("막달레나")).toEqual(true);
  expect(tree.search("사와디캅")).toEqual(true);

  tree.remove("사와디캅");
  expect(tree.search("막달레나")).toEqual(true);
  expect(tree.search("사와디캅")).toEqual(false);

  tree.preOrderTraverse(key => console.log(key));
  tree.postOrderTraverse(key => console.log(key));
  tree.inOrderTraverse(key => console.log(key));
});

확장 - 이진 탐색 트리 Binary Search Tree (BST)

이진 트리 이면서, '왼쪽노드는 중심노드보다 작고 오른쪽 노드는 중심 노드보다 크다'는 규칙성을 가지고있는 트리이다.

정렬된 트리이므로 이진 검색, 최소/최대값 찾을때 용이하다.
특히 이진 탐색 트리가 균형트리일 경우에는 검색에 O(log n) 실행시간이 보장된다.

구현

앞서 만든 이진 트리 클래스를 상속받아 메서드를 오버라이드 하고 더 필요한 메서드를 추가하는 방식으로 구현했다.

class BinarySearchTree extends BinaryTree {
  insert(key) {
    const node = new BinaryTreeNode(key);

    if (!this.root) {
      this.root = node;
    } else {
      insertNode(this.root, node);
    }

    function insertNode(node, newNode) {
      if (!node) {
        return;
      }

      if (node.key > newNode.key) {
        if (node.left) {
          insertNode(node.left, newNode);
        } else {
          node.left = newNode;
        }
      } else if (node.key < newNode.key) {
        if (node.right) {
          insertNode(node.right, newNode);
        } else {
          node.right = newNode;
        }
      }
    }
  }

  search(key) {
    if (!this.root) {
      return false;
    }

    return searchNode(this.root, key);

    function searchNode(node, key) {
      if (!node) {
        return false;
      }

      if (node.key === key) {
        return true;
      }

      if (node.key > key) {
        return searchNode(node.left, key);
      }

      if (node.key < key) {
        return searchNode(node.right, key);
      }

      return false;
    }
  }

  remove(key) {
    if (!this.root) {
      return;
    }

    this.root = removeNode(this.root, key);

    function removeNode(node, key) {
      if (!node) {
        return null;
      }

      if (key < node.key) {
        node.left = removeNode(node.left, key);
        return node;
      } else if (key > node.key) {
        node.right = removeNode(node.right, key);
        return node;
      } else {
        if (!node.left && !node.right) {
          node = null;
          return node;
        }

        if (!node.left) {
          node = node.right;
          return node;
        } else if (!node.right) {
          node = node.left;
          return node;
        }

        const smallest = findMinNode(node.right);
        node.key = smallest.key;
        node.right = removeNode(node.right, smallest.key);
        return node;
      }

      function findMinNode(node) {
        if (!node) {
          return null;
        }

        if (!node.left) {
          return node;
        } else {
          return findMinNode(node.left);
        }
      }
    }
  }

  min() {
    return findMin(this.root);

    function findMin(node) {
      if (!node) {
        return null;
      }

      if (!node.left) {
        return node.key;
      } else {
        return findMin(node.left);
      }
    }
  }

  max() {
    return findMax(this.root);

    function findMax(node) {
      if (!node) {
        return null;
      }

      if (!node.right) {
        return node.key;
      } else {
        return findMax(node.right);
      }
    }
  }
}

// Test
it("BinarySearchTree 클래스는 잘 동작한다.", () => {
  const bst = new BinarySearchTree();

  expect(bst.search(5)).toEqual(false);
  bst.insert(5);
  expect(bst.search(5)).toEqual(true);

  bst.insert(7);
  bst.insert(3);
  bst.insert(2);
  bst.insert(4);
  bst.insert(6);
  bst.insert(9);

  expect(bst.min()).toEqual(2);
  expect(bst.max()).toEqual(9);

  bst.remove(5);
  expect(bst.search(5)).toEqual(false);
  expect(bst.search(7)).toEqual(true);
  expect(bst.search(3)).toEqual(true);
  expect(bst.search(2)).toEqual(true);
  expect(bst.search(4)).toEqual(true);
  expect(bst.search(6)).toEqual(true);
  expect(bst.search(9)).toEqual(true);

  bst.preOrderTraverse(key => console.log(key));
  bst.postOrderTraverse(key => console.log(key));
  bst.inOrderTraverse(key => console.log(key));
});

확장 - 힙 Heap

부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다.
상세 설명은 힙 Heap 페이지에 정리했다.

확장 - AVL 트리 (Adelson-Velskii and Landis' Tree)

AVL 트리는 스스로 균형을 잡는 이진 탐색 트리다.

처음은 균형트리였다해도 노드의 추가/삭제가 진행될 수록 특정 서브트리의 깊이만 길게 늘어져 균형이 깨지게 된다.

이처럼 불균형한 트리는 성능이 떨어진다.

AVL 트리는 이 문제에 대한 대안으로 나온 트리로서, 노드를 추가/삭자해도 가능한한 완벽한 균형트리 모양을 스스로 유지한다.
(좌 우측 서브트리의 높이가 1 이상 차이가 나지 않도록 조정)

확장 - 트라이(Trie) 또는 Prefix Tree

이진 트리 이면서, 키가 연속된 요소로 분리할 수 있는 경우에 효율적이다.(ex. 문자열)

확장 - 레드-블랙 트리 Red-Black Tree

아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
스기우라 켄, 『그림으로 배우는 알고리즘』, 서재원, 영진(2016)
이소 히로시, 『모던 자바스크립트 입문』, 서재원, 길벗(2018)
Martin Erwig, 『그들은 알고리즘을 알았을까?』, 송원형, 영진(2017)
Loiane Groner, 『자바스크립트 자료 구조와 알고리즘』, 이일웅, PACKT-에이콘(2015)

트리(Tree)란 무엇인가