비선형 자료구조 - 트리(Tree)

MyeonghoonNam·2021년 6월 22일
0

자료구조

목록 보기
8/9
post-thumbnail

트리

정의

  • 데이터의 각 요소들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조.
  • 데이터의 각 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현한다.
  • 트리노드간선으로 이루어진 자료구조이다.
    1. 트리는 하나의 루트 노드를 갖는다.
    2. 루트 노드0개 이상의 자식 노드를 갖고 있는다.
    3. 자식 노드 또한 0개 이상의 자식 노드를 가지며, 반복적으로 트리가 구성된다.
    4. 각 노드들은 서로를 연결하는 간선으로 이어져있다.
    5. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
  • 트리에는 사이클이 존재할 수 없다(임의의 두 노드간의 경로가 유일).
  • 트리는 그래프의 한 종류최소 연결 트리라고도 불린다.
    1. 사이클이 없는 하나의 연결 그래프
      -> 즉, 루트노드에서 시작하여 같은 방향으로 다시 루트노드에 도착할 수 없다.
    2. DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류.

용어

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


순회

  • 트리를 탐색하는 순회 방법에는 크게 두 가지가 존재한다.

  • 레벨 순회 방식
  • 트리 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현한다.
  • 즉, 트리의 레벨이 가장 낮고 왼쪽의 노드 부터 순서대로 방문한다고 이해하면 된다.
  • 자료구조를 활용하면 구현이 편리하다.

  • 구현 - JavaScript
// 전체 코드인 아래 이진 탐색 트리의 구현을 참고하여 코드를 이해하길 바란다.
// 위 이미지의 트리의 순회 결과는 : A -> B -> C -> D -> E -> F -> G -> H -> J
bfs() {
    let curNode = this.root;

    const queue = [curNode];

    let printTree = '';

    while(queue.length) {
      curNode = queue.shift();
      printTree += curNode.value + ' ';

      if(curNode.left) {
        queue.push(curNode.left);
      }

      if(curNode.right) {
        queue.push(curNode.right);
      }
    }

    console.log(printTree);

    return;
  }
  • 트리에서의 깊이우선탐색은 순회 방식에 따라 3가지로 나뉘어진다.

1. 전위 순회(Preorder Traversal)

  • 전위 순회의 탐색 방법은 다음과 같다.

    1. 루트노드 방문한다.
    2. 왼쪽 서브트리를 전위 순회한다.
    3. 오른쪽 서브트리를 전위 순회한다.
  • 위 트리의 전위 순회 결과는 A->B->C->D->E->F->G 이다.

  • 구현 - JavaScript

// 전체 코드인 아래 이진 탐색 트리의 구현을 참고하여 코드를 이해하길 바란다.
// 1. 전위 순회(Prerder Traversal)
  preOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    console.log(root.value);
    this.preOrder(root.left);
    this.preOrder(root.right);
  }

2. 중위 순회(Inorder Traversal)

  • 중위 순회의 탐색 방법은 다음과 같다.

    1. 왼쪽 서브트리를 중위 순회한다.
    2. 루트노드 방문한다.
    3. 오른쪽 서브트리를 중위 순회한다.
  • 위 트리의 중위 순회 결과는 D->B->E->A->F->C->G 이다.

  • 구현 - JavaScript

// 전체 코드인 아래 이진 탐색 트리의 구현을 참고하여 코드를 이해하길 바란다.
// 2. 중위 순회(Inorder Traversal)
  inOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    this.inOrder(root.left);
    console.log(root.value);
    this.inOrder(root.right);
  }

3. 후위 순회(Postorder Traversal)

  • 후위 순회의 탐색 방법은 다음과 같다.

    1. 왼쪽 서브트리를 후위 순회한다.
    2. 오른쪽 서브트리를 후위 순회한다.
    3. 루트노드 방문한다.
  • 위 트리의 후위 순회 결과는 D->E->B->F->G->C->A 이다.

  • 구현 - JavaScript

// 전체 코드인 아래 이진 탐색 트리의 구현을 참고하여 코드를 이해하길 바란다.
// 3. 후위 순회(Postorder Traversal)
  postOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    this.postOrder(root.left);
    this.postOrder(root.right);
    console.log(root.value);
  }

1. 이진 트리

  • 이진 트리(Binary Tree)는 각 노드가 자식 노드를 최대 2개까지 가지는 트리를 말한다.
  • 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지 지정된다.
  • 이진 트리의 종류에는 완전 이진 트리, 포화 이진 트리, 정 이진 트리, 편향 이진 트리 등이 있다.

완전 이진 트리

  • 완전 이진 트리(complete binary tree)왼쪽 자식 노드부터 순서대로 노드가 채워지며 마지막 레벨을 제외하고는 모든 자식 노드가 채워져있는 트리를 말한다.
  • 마지막 레벨 역시 노드가 왼쪽에서 부터 순서로 채워져야 한다.


포화 이진 트리

  • 포화 이진 트리(perfect binary tree)모든 노드가 0개 혹은 2개의 자식 노드를 가지며 모든 리프노드가 똑같은 레벨에 있는 경우의 트리를 말한다.


정 이진 트리

  • 정 이진 트리(full binary tree)모든 노드가 0개 혹은 2개의 자식 노드를 가지는 트리를 말한다.


편향 이진 트리

  • 편향 이진 트리(skewed binary tree)는 말 그대로 노드들이 전부 한 방향으로 편향된 트리를 말한다.


2. 이진탐색트리

  • 이진 탐색 트리(binary search tree)이진 트리의 한 종류이다.
  • 이진 트리이지만 왼쪽 자식 노드가 루트 노드보다 값이 작고, 오른쪽 자식 노드가 루트 노드보다 값이 큰 트리를 말한다.

구현 - JavaScript

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

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.length = 0;
  }

  // 노드 탐색
  search(value) {
    let curNode = this.root;

    while (curNode) {
      if (curNode.value === value) {
        console.log('찾으시는 노드는 존재합니다.');
        return;
      }

      if (curNode.value > value) {
        curNode = curNode.left;
      } else {
        curNode = curNode.right;
      }
    }

    console.log('찾으시는 노드는 존재하지 않습니다.');

    return;
  }

  // 노드 삽입
  insert(value) {
    let newNode = new Node(value);
    let curNode = this.root;

    if (!this.root) {
      this.root = newNode;
      this.length++;

      return;
    }

    while (curNode) {
      // 이진탐색트리는 중복값을 허용하지 않는다.
      if (value === curNode.value) return;

      // 추가되는 값이 루트노드의 값보다 작은 경우 왼쪽 서브트리
      if (value < curNode.value) {
        if (!curNode.left) {
          curNode.left = newNode;
          break;
        }

        curNode = curNode.left;
      } else {
        // 추가되는 값이 루트노드의 값보다 큰 경우 오른쪽 서브트리
        if (!curNode.right) {
          curNode.right = newNode;
          break;
        }

        curNode = curNode.right;
      }
    }

    this.length++;
  }

  // 노드 삭제
  remove(value) {
    const removeNode = (node, value) => {
      // 트리가 존재하지 않은 경우
      if (!node) return null;

      if (value === node.value) {
        // 삭제할 노드가 자식 노드가 없는 경우
        if (!node.left && !node.right) {
          return null;
        } else if (!node.right) {
          // 삭제할 노드가 왼쪽 자식 노드만 존재하는 경우
          return node.left;
        } else if (!node.left) {
          // 삭제할 노드가 오른쪽 자식 노드만 존재하는 경우
          return node.right;
        } else {
          // 왼쪽, 오른쪽 모두 자식노드가 있는 경우
          // 삭제할 노드의 오른쪽 자식 중에서 가장 왼쪽 아래의 자식을 선택하여 삭제할 노드의 위치로 변경하는 방법 사용
          let curNode = node.right;

          while (curNode.left) {
            curNode = curNode.left;
          }

          node.value = curNode.value;
          node.right = removeNode(node.right, curNode.value);

          return node;
        }
      } else if (value < node.value) {
        node.left = removeNode(node.left, value);
        return node;
      } else {
        node.right = removeNode(node.right, value);
        return node;
      }
    };

    this.root = removeNode(this.root, value);
    this.length--;
  }

  // Bfs : 너비우선탐색
  bfs() {
    let curNode = this.root;

    const queue = [curNode];

    let printTree = '';

    while (queue.length) {
      curNode = queue.shift();
      printTree += curNode.value + ' ';

      if (curNode.left) {
        queue.push(curNode.left);
      }

      if (curNode.right) {
        queue.push(curNode.right);
      }
    }

    console.log(printTree);

    return;
  }

  // Dfs : 깊이우선탐색
  // 1. 전위 순회(Prerder Traversal)
  preOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    console.log(root.value);
    this.preOrder(root.left);
    this.preOrder(root.right);
  }

  // 2. 중위 순회(Inorder Traversal)
  inOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    this.inOrder(root.left);
    console.log(root.value);
    this.inOrder(root.right);
  }

  // 3. 후위 순회(Postorder Traversal)
  postOrder(root = this.root) {
    // 데이터가 없는 경우
    if (!root) return;

    this.postOrder(root.left);
    this.postOrder(root.right);
    console.log(root.value);
  }
}

const bst = new BinarySearchTree();

bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);
bst.insert(14);
bst.insert(9);
bst.insert(4);
bst.insert(7);
bst.insert(13);

bst.bfs();
console.log('----------');

bst.preOrder();
console.log('----------');

bst.inOrder();
console.log('----------');

bst.postOrder();
console.log('----------');

bst.remove(10);
bst.preOrder();

console.log(bst.root);

결과


3. 힙

  • 완전 이진 트리의 일종으로 우선순위 큐 개념을 구현하기에 적합한 자료구조이다.
  • 데이터의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기에 최적화된 자료구조이다.
  • 부모 노드의 값이 자식 노드의 값 보다 항상 크거나 작은 이진 트리를 말한다.
  • 이진 탐색 트리와 다르게 중복된 값을 허용한다.
  • 최대힙(Max Heap)최소힙(Min Heap)으로 종류가 나뉘어진다.

우선순위 큐 ?

  • 우선순위의 개념을 큐에 도입한 자료구조이다.
  • 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가는 자료구조.

  • 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하며 이 중 힙이 가장 효율적이다.

최대 힙(Max Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
  • 최대 힙루트 노드는 가장 큰 값이 된다.

구현 - JavaScript

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  // 삽입연산 : 힙을 구성
  insert(value) {
    this.heap.push(value);
    this.moveUp();
  }

  // 삭제연산 : 최댓값을 뽑아내는 연산
  pop() {
    // 최대값을 저장
    const max = this.heap[0];

    // 힙의 가장 마지막 요소를 루트에 저장
    this.heap[0] = this.heap.pop();
    // 루트노드 부터 아래로 대소 비교 시작하여 위치 조정
    this.moveDown(0);

    return max;
  }

  // 힙의 하단에서 부터 상단으로 값을 변경한다.
  moveUp() {
    // 힙의 맨 마지막 요소에 값이 추가 되었으므로
    let curIdx = this.heap.length - 1;

    // 최댓값을 가장 최상단으로 올리는 작업을 반복
    while (curIdx > 0) {
      const parentIdx = Math.floor((curIdx - 1) / 2);

      if (this.heap[parentIdx] >= this.heap[curIdx]) break;

      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];

      curIdx = parentIdx;
    }
  }

  // 힙의 상단에서 부터 하단으로 값을 변경한다.
  moveDown(idx) {
    const leftIdx = 2 * idx + 1;
    const rightIdx = 2 * idx + 2;
    const length = this.heap.length;
    let maxIdx = idx;

    // 힙의 왼쪽 자식과 변경 여부
    if (leftIdx < length && this.heap[leftIdx] > this.heap[maxIdx]) {
      maxIdx = leftIdx;
    }

    // 힙의 왼쪽 자식으로 인덱스 바뀌어 있어도 오른쪽이 더 큰 요소였다면 오른쪽 인덱스 요소로 변경된다.
    if (rightIdx < length && this.heap[rightIdx] > this.heap[maxIdx]) {
      maxIdx = rightIdx;
    }

    // swap 후 재귀 호출울 통해 계속 값 변경
    if (maxIdx !== idx) {
      [this.heap[idx], this.heap[maxIdx]] = [this.heap[maxIdx], this.heap[idx]];

      this.moveDown(maxIdx);
    }
  }
}

const maxHeap = new MaxHeap();

maxHeap.insert(4);
maxHeap.insert(7);
maxHeap.insert(6);
maxHeap.insert(5);
maxHeap.insert(2);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(3);
maxHeap.insert(2);
maxHeap.insert(3);

console.log(maxHeap.heap);

maxHeap.pop();
console.log(maxHeap.heap);

결과



최소 힙(Min Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
  • 최소 힙루트 노드는 가장 작은 값이 된다.

구현 - JavaScript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  // 삽입연산 : 힙을 구성
  insert(value) {
    this.heap.push(value);
    this.moveUp();
  }

  // 삭제연산 : 최솟값을 뽑아내는 연산
  pop() {
    // 최솟값을 저장
    const min = this.heap[0];

    // 힙의 가장 마지막 요소를 루트에 저장
    this.heap[0] = this.heap.pop();
    // 루트노드 부터 아래로 대소 비교 시작하여 위치 조정
    this.moveDown(0);

    return min;
  }

  // 힙의 하단에서 부터 상단으로 값을 변경한다.
  moveUp() {
    // 힙의 맨 마지막 요소에 값이 추가 되었으므로
    let curIdx = this.heap.length - 1;

    // 최솟값을 가장 최상단으로 올리는 작업을 반복
    while (curIdx > 0) {
      const parentIdx = Math.floor((curIdx - 1) / 2);

      if (this.heap[parentIdx] <= this.heap[curIdx]) break;

      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];

      curIdx = parentIdx;
    }
  }

  // 힙의 상단에서 부터 하단으로 값을 변경한다.
  moveDown(idx) {
    const leftIdx = 2 * idx + 1;
    const rightIdx = 2 * idx + 2;
    const length = this.heap.length;
    let minIdx = idx;

    // 힙의 왼쪽 자식과 변경 여부
    if (leftIdx < length && this.heap[leftIdx] < this.heap[minIdx]) {
      minIdx = leftIdx;
    }

    // 힙의 왼쪽 자식으로 인덱스 바뀌어 있어도 오른쪽이 더 작은 요소였다면 오른쪽 인덱스 요소로 변경된다.
    if (rightIdx < length && this.heap[rightIdx] < this.heap[minIdx]) {
      minIdx = rightIdx;
    }

    // swap 후 재귀 호출울 통해 계속 값 변경
    if (minIdx !== idx) {
      [this.heap[idx], this.heap[minIdx]] = [this.heap[minIdx], this.heap[idx]];

      this.moveDown(minIdx);
    }
  }
}

const minHeap = new MinHeap();

minHeap.insert(4);
minHeap.insert(7);
minHeap.insert(6);
minHeap.insert(5);
minHeap.insert(2);
minHeap.insert(9);
minHeap.insert(1);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(3);

console.log(minHeap.heap);

minHeap.pop();
console.log(minHeap.heap);

결과



4. 트라이

  • 트라이(Trie)문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.

  • 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있습니다.

  • 문자열의 탐색을 하고자할 때 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. (시간복잡도가 가장 긴 문자열의 길이만큼 걸린다. 즉, O(N))

  • 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다.

  • 아래 사진은 be, bee, can, cat, cd가 들어가 있습니다.

구현 - JavaScript

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(node) {
    if (this.size() === 0) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;

    return;
  }

  dequeue() {
    if (this.size() === 0) {
      console.log('큐가 이미 비었습니다.');
      return;
    }

    const deleteNode = this.head;

    if (this.size() === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = deleteNode.next;
    }

    this.length--;

    return deleteNode;
  }

  size() {
    return this.length;
  }
}

class Node {
  constructor(value = '') {
    this.value = value; //현재 경로까지의 누적값
    this.end = false; //해당 노드에서 끝나는 문자열이 있는지 여부
    this.child = {}; //자식
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let curNode = this.root; //루트노드를 시작으로 탐색하면서 삽입한다

    for (let i = 0; i < string.length; i++) {
      const char = string[i];

      //만일, 해당 키를 가진 자식이 없다면 새 노드를 만들어준다.
      if (!curNode.child[char]) {
        curNode.child[char] = new Node(curNode.value + char);
      }

      curNode = curNode.child[char]; // 자식 노드로 이동한다.
    }

    curNode.end = true; //해당 노드에서 끝나는 단어가 있음을 알린다.
  }

  search(string) {
    let curNode = this.root;

    for (let i = 0; i < string.length; i++) {
      const char = string[i];

      if (curNode.child[char]) {
        curNode = curNode.child[char];
      } else {
        return false;
      }
    }

    return curNode;
  }

  // 자동완성기능
  autoComplete(string) {
    const findNode = this.search(string); // 자동검색을 위한 입력 단어의 노드

    if (!findNode) return; // 입력단어가 존재 하지 않는 경우

    const queue = new Queue();
    const result = []; // 자동완성단어의 리스트

    queue.enqueue(findNode);

    while (queue.size()) {
      const curNode = queue.dequeue();

      if (curNode.end) result.push(curNode.value);

      Object.values(curNode.child).forEach((node) => {
        if (node) queue.enqueue(node);
      });
    }

    return result.sort(); // 자동완성된 단어들을 사전 순으로 정렬하여 반환하였다.
  }
}

const trie = new Trie();

trie.insert('be');
trie.insert('bee');
trie.insert('can');
trie.insert('cat');
trie.insert('cd');

console.log(trie.autoComplete('ca')); // ['can', 'cat']

console.log(trie.search('can')); // 찾아야함
console.log(trie.search('cbn'));
console.log(trie.search('bee')); // 찾아야함
console.log(trie.search('bt'));

결과



참고자료

profile
꾸준히 성장하는 개발자를 목표로 합니다.

0개의 댓글