[자료구조 및 알고리즘] CH6. Tree

 

Tree란?

• Connected, Acyclis, Undirected graph
• Tree는 Graph에 포함된다.

Rooted tree란?

• 하나의 node가 root로 지정된 tree

Tree에서 depth란?

• root 노드로부터 해당 노드까지의 edge 수
• 트리의 depth : lowest leaf의 depth(이것을 트리의 height라고도 한다.)

Tree에서 level이란?

• depth와 비슷하지만 기준이 edge가 아닌 node
• 아래 그림에서 B, D는 각각 레벨이 2, 3인 노드이다.

트리의 레벨(출처 : jiwondh github 블로그)

Binary tree란?

• 모든 node가 최대 2개의 child를 갖는 트리

Binary search tree(BST)란?

• x라는 key value를 갖는 노드의 left subtree에는 x보다 작은 값이, right subtree에는 x보다 큰 값의 children이 자리하는 binary tree
• searching에 최적화된 tree

BST에서 삭제 알고리즘은 어떻게 작동하는가?

• 세 가지 경우가 가능하다.
  • 삭제하려는 노드가 child가 없는 경우 : 그냥 해당 노드를 삭제하면 된다.
  • 삭제하려는 노드가 하나의 child만 갖는 경우 : 삭제하려는 노드의 child와 parent를 연결해주면 된다.
  • 삭제하려는 노드가 두 개의 child를 갖는 경우
    • 왼쪽 서브트리에 있는 값 중 가장 큰 값 혹은 오른쪽 서브트리에 있는 값 중 가장 작은 값으로 삭제하려는 노드를 교체해준다.(근거 : 트리의 변동성 최소화)
    • 아래에서 18을 삭제하려면 12나 22중 하나로 18을 교체하면 된다.

이미지 출처 : mattlee 티스토리

Binary tree traverse 방법엔 어떤 것들이 있나?(이진트리 탐색 방법)

• 우선, traverse란 모든 노드를 한 번씩 방문하는 것이다.
• 이진트리 탐색에는 방문 순서에 따라 3가지 방법이 있다.
  • Preorder : root를 먼저 방문 -> left subtree 방문 -> right subtree 방문
  • Inorder : left subtree 방문 -> root 방문 -> right subtree 방문
  • Postorder : left subtree 방문 -> right subtree 방문 -> root 방문
• 여기서 중요한 부분은 BST를 inorder로 방문하면 sorted된 결과가 출력된다는 것!!!

Full Binary Tree(포화이진트리)란?

• leaft node(단말노드)를 제외한 모든 노드가 두 개의 children을 갖는 이진트리

Full binary tree의 예(반드시 마지막 level 전체가 full 상태여야 한다!!!!!)

Full binary tree가 아닌 예

Complete Binary Tree(완전이진트리)란?

• 마지막 level을 제외한 모든 level의 node들이 완전히 채워져있고(completely filled) 모든 노드가 가능한 한 왼쪽부터 채워지는 이진트리

완전이진트리의 예

Heap이란?

• 모든 노드의 값이 자식 노드의 값보다 작은 이진트리(min-heap, max-heap은 그 반대)
• heap은 가장 작은 값(혹은 가장 큰 값)을 찾는데 효율적
• priority queue나 sorting(heap sort)에 사용된다.

Min-Heap에서 최솟값을 찾아 삭제하는 과정

• 최솟값은 root에 있으므로 이를 삭제하고 last node로 교체한다.
• Heapness를 회복하기 위해 재배치(restore heap)과정을 거친다.
• 아래 그림에서 최솟값 5를 찾아 삭제하려면 last node인 12와 교체해야 한다. 그런데 이 경우 heap의 규칙에 맞지 않으므로 다시 그 아래 그림처럼 restore 해줘야 한다. restore는 새로운 root(bug)를 smaller child와 바꿔주는 과정을 반복하면 된다.

MinHeap 최솟값 삭제

restore heap

MinHeap에서 삽입 과정

• heap의 끝에 새로운 데이터 삽입 -> parent와 크기비교하며 minheap조건을 만족할 때까지 자리 교체

 

Heap에서 삭제, 삽입 과정의 시간복잡도는?

• O(logn) - level을 따라 진행되므로