본문 바로가기
[Basic] Data/Data Structure

[Data Structure] 비선형 - Tree(트리)

by song.ift 2023. 2. 21.

트리 구조는 맨 위의 사진과 같이 하나의 뿌리로부터 시작되어서 가지가 여러 갈래로 뻗어있는 자료 구조를 말한다. 트리 구조가 어디서 많이 봤다고 하면 착각은 아니다. 스포츠를 좋아하는 사람이라면 많이 봤을 것이라고 생각되는 토너먼트 대진표도 트리 구조이다. 아래서부터 차례로 올라가서 가장 꼭대기까지 가는 것이 토너먼트이다. 트리구조는 반대로 위의 뿌리 노드부터 시작해서 아래로 내려가는 구조다.

 

Tree (트리)

  • 노드로 이루어진 비선형 자료 구조
  • 그래프가 계층적 구조를 가진 형태
  • 최상위 노드(루트)를 가지고 있음
  • 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다.
  • 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
    • 트리에는 사이클(cycle)이 존재할 수 없다.
    • 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
    • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
    • 각 노드는 어떤 자료형으로도 표현 가능하다

 

트리(Tree) 용어 정리

  • 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • 단말 노드(leaf node) : 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
  • 내부(internal) 노드 : 단말 노드가 아닌 노드
  • 간선(edge) : 노드를 연결하는 선 (link, branch 라고도 부름)
  • 형제(sibling) : 같은 부모를 가지는 노드
  • 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
  • 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
  • 노드의 차수(degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
  • 트리의 차수(degree of tree) : 트리의 최대 차수
  • 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리(Tree)의 특징

  • 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
  • 트리는 계층 모델 이다.
  • 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
    • loop나 circuit이 없다. 당연히 self-loop도 없다.
    • 즉, 사이클이 없다.
  • 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
    • 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.
  • 루트에서 어떤 노드로 가는 경로는 유일하다.
    • 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
  • 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
    • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
  • 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
  • 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

 

이진 트리와 이진 검색 트리

이진 트리는 트리 구조 중 특수한 경우로, 자식 노드가 최대 두개인 트리를 뜻한다. 자식 노드가 두개이기 때문에, 자식 노드는 왼쪽 or 오른쪽으로 구분할 수 있다. (모든 트리가 이진 트리는 아니다.)

한편, 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree), 균형 이진 트리(balanced binary tree) 로 나뉜다.

  • 정 이진 트리(full binary tree) : 각 노드가 0 개 혹은 2 개의 자식 노드를 갖는 경우
  • 완전 이진 트리(complete binary tree) : 마지막 레벨을 제외한 모든 레벨의 노드들이 꽉 채워진 이진트리
    • 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있는 경우
  • 포화 이진 트리(perfect binary tree) : 모든 레벨에서 노드들이 꽉 채워진 이진트리
    • 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있어야 됨.
  • 균형 이진 트리(balanced binary tree) : 리프 노드의 깊이 차가 1을 초과하지 않는 이진 트리

이진 검색 트리는 이진 트리를 이용한 검색 방법을 이용할 때 쓰는 트리구조이다.

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다. 이진 검색 트리를 쓰면 검색에 필요한 시간을 줄일 수 있다. 시간복잡도가 O(N)에서 O(log_2(N))으로 줄어들기 때문이다.
만약에 1부터 10까지 있는 숫자 배열이 있을 때 9이라는 숫자를 찾는다고 가정하자. 그냥 막무가내로 찾는다면 배열을 앞에서부터 찾는다고 가정했을 경우, 9번째가 되어서야 나온다.(만약 10을 찾는다면...) 하지만 이진 트리를 사용한다면 최대 3번이면 끝난다. 이진트리를 사용하는 검색 메소드는 이분법(방정식의 해를 범위를 반으로 줄여나가면서 푸는 알고리즘)과 유사하기 때문이다. 1에서 10까지의 배열 [1,2,3,4,5,6,7,8,9,10]이 있을 때 중간값을 구한다. 중간값은 5.5이기 때문에 5.5를 기준으로 반을 소거시킨다. 그러면 [6,7,8,9,10]의 중간값인 8을 기준으로 또 소거시킨다.(만약 찾는 값이 8이면 여기서 끝) 중간값 8을 소거시시켰으면 나머지 요소인 [9,10] 중에 찾으면 검색이 끝난다. 그냥 막무가내로 앞에서부터 찾는 것보다 문제 해결 시간이 훨씬 단축되는 것을 알 수 있다.

 

트리 순회 알고리즘

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회(Tree traversal)라고 한다. 윗 문단에서 숫자 9를 찾기 위하여 중간값을 조회하고 자르고의 과정을 반복했다. 이러한 과정도 일종의 트리 순회이다. 트리 노드를 순회하는 방법은 루트 노드를 언제 거치느냐에 따라서 세 가지로 나뉜다(전위 순회, 중위 순회, 후위 순회). 트리를 순회할 때에는 항상 왼쪽이 우선이다.

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

 

 

  • 전위 순회(pre-order traversal) : 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 하는 방식.
    • 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
    • 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14
/**
 * @params {Node} root - 트리의 루트
 * @returns {Array} 방문 순서대로 노드를 넣은 배열
 */
const preorder = root => {
    if(!root) return [];
    return [root.data].concat(preorder(root.left), preorder(root.right));
}
  • 중위 순회(in-order traversal) : 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색하는 방식.
    • 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
    • 8 -> 4 -> 9 -> 2 -> 10 -> 5 -> 11 -> 1 -> 13 -> 6 -> 3 -> 14 -> 7
/**
 * @params {Node} root - 트리의 루트
 * @returns {Array} 방문 순서대로 노드를 넣은 배열
 */
const inorder = root => {
    if(!root) return [];
    return inorder(root.left).concat([root.data], inorder(root.right));
}
  • 후위 순회(post-order traversal) : 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문하는 방식.
    • 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
    • 8 -> 9 -> 4 -> 10 -> 11 -> 5 -> 2 -> 13 -> 6 -> 14 -> 7 -> 3 -> 1
/**
 * @params {Node} root - 트리의 루트
 * @returns {Array} 방문 순서대로 노드를 넣은 배열
 */
const preorder = root => {
    if(!root) return [];
    return preorder(root.left).concat(preorder(root.right), [root.data]);
}

 

Ex) 트리 구현

class Tree {
  constructor(value) {
    // constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    this.children = [];
  }

  // 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
    // 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
    // TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  // 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
    // TODO: 값이 포함되어 있다면 true를 반환하세요. 
    if (this.value === value) return true;
    
    // TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
    for (let i=0;i<this.children.length;i++) {
      const childNode = this.children[i];
      if (childNode.contains(value)) return true;
    }
	
    // 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
    return false;
  }
}

Ex) 이진 검색 트리 구현

class BinarySearchTree {
    //BST의 constructor를 구현합니다.
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    
    // tree에 value를 추가합니다.
    insert(value) {
      // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
      if (value < this.value) {
        // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
        if (this.left === null) {
          this.left = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
        else {
          this.left.insert(value);
        }
      }
      // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
      else if (value > this.value) {
        // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
        if (this.right === null) {
          this.right = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
        else {
          this.right.insert(value);
        }
      } else {
        // 이미 value값을 포함하고 있습니다.
      }
    
    // tree의 value값을 탐색합니다.
    contains(value) {
      // 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
      if (value === this.value) {
        return true;
      }
      // 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
      if (value < this.value) {
        return !!(this.left && this.left.contains(value));
      }
      // 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
      if (value > this.value) {
        return !!(this.right && this.right.contains(value));
      }
    }
    
    //tree를 전위 순회
    preorder(callback) {
      callback(this.value);
      if (this.left) {
        this.left.preorder(callback);
      }
      if (this.right) {
        this.right.preorder(callback);
      }
    }
    
    // tree를 중위 순회
    inorder(callback) {
      if (this.left) {
        this.left.inorder(callback);
      }
      callback(this.value);
      if (this.right) {
        this.right.inorder(callback);
      }
    }
    
    //tree를 후위 순회
    postorder(callback) {
      if (this.left) {
        this.left.postorder(callback);
      }
      if (this.right) {
        this.right.postorder(callback);
      }
      callback(this.value);
    }
  }

 

그래프와 트리의 차이

저작자표시

'[Basic] Data > Data Structure' 카테고리의 다른 글

[Data Structure] 선형 자료구조  (0) 2023.03.16
[Data Structure] 비선형 - Heap(힙)  (0) 2023.02.21
[Data Structure] 비선형 - Graph(그래프)  (0) 2023.02.21
[Data Structure] 비선형 - Hash Table(해시 테이블)  (0) 2023.02.21
[Data Structure] 선형 - Queue(큐)  (0) 2023.02.21

관련글

댓글

티스토리툴바