이 포스팅의 알고리즘 강의는 이곳에서 보실 수 있습니다.

트리 (Tree)

• 계층적인 구조를 표현(디렉토리, 파일구조 등등 )
• 트리는 node와 node들을 연결하는 link들로 구성됨.

용어

• 부모-자식 관계 - 노드의 상하 구조
• 형제관계 : 동등란 level의 노드들
• 리프노드 : 자식이 없는 노드
• 조상-자손 관계 : 부모-자식 관계를 확장한 것 루트-리프노드
• subtree: 트리에서 어떤 한 노드와 그 노드들의 자손들로 이루어진 트리.

기본적인 성질

• 노드가 n개인 트리는 항상 n-1개의 링크를 가진다.
• 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건에서)

이진 트리(Binary tree)

• 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.
• 이진 트리 응용의 예로는 Expression Tree, Huffman Code 등이 있다.
• 높이가 h인 full binary tree는 2의 h승 - 1개의 노드를 가진다.
• 노드가 N개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다. -> 최악의 경우 이진트리의 높이는 N이 될수도 있다.

이진트리의 표현

• 연결구조(Linked Structure) 표현
• 각 노드에 하나의 데이터 필드와 왼쪽자식, 오른쪽 자식 그리고 부모노드의 주소를 저장( node-> left, data, P, right)
• 첫 번째 노드의 주소는 시작점이므로 따로 보관해야한다.

이진트리의 순회(trabersal)

• 순회: 이진 트리의 모든 노드를 방문하는 일
• 중순위(inorder), 선순위(preorder), 후순위(postorder) 순회
  • 중순위: 왼쪽부트리, 루트, 오른쪽부트리 순으로 순회
  • 선순위: 루트, 왼쪽 부트리, 오른쪽부트리 순으로 순회
  • 중순위: 왼쪽부트리, 오른쪽부트리, 루트 순으로 순회
  • inorder순회를 postorder 순회를 하면 후위 표기식이 출력된다.
• 레벨 오더 (level-order) 순회 : 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로, 주로 큐(queue)를 이용하여 구현한다.

이진검색트리(Binary Search Tree)

Dynamic Set(집합)

• 여러개의 키(key)를 저장한다.
• Insert, Search, Delete를 지원하는 자료구조다.
• 정렬된 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용한 경우 Insert, Search, Delete 중 하나는 O(n)이 걸린다.
• 그래서 Dynamic set에는 대표적으로 Tree와 hash가 있다.
• 일반적으로 Insert, Search, Delete 연산이 트리의 높이에 비례하는 시간복잡도를 가진다.(이진검색트리, 레드-블랙 트리, B-트리 등)

BST

• 이진트리이면서 각 노드에 하나의 키를 저장한다.
• 각 노드 v에 대해서 그 노드의 왼쪽 부트리에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.
• 최소값은 트리의 가장 왼쪽값이고 최대값은 가장 오른쪽 값이다.

Successor

• 노드 x의 successor란 key[x]보다 크면서 가장 작은 키를 가진 노드를 말한다.
• 모든 키들이 서로 다르다고 가장한다.
• successor가 항상 존재하지는 않는다.
• Successor은 3가지 경우가 있는데 1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최소값이다. 2. 오른쪽 부트리가 없는 경우, 어떤 노드 y의 왼쪽 부트리의 최대값이 x가 되는 그런 노드 y가 x의 successor..(쉽게 말해 왼쪽 부트리의 최대값에서 부모를 찾아 올라가는데 이때 부모가 자식을 보는 방향이 왼쪽이 나오면 그것이 successor이다.) 3. 그런 노드 y가 존재하지 않을 경우, successor가 존재하지 않음(즉 x가 최대값)
• Predecessor: 노드 x의 Predecessor란 key[x]보다 작으면서 가장 큰 키를 가진 노드(Successor와 정 반대)

Search

• 루트를 따라서 값이 큰지 작은지 비교해가며 리프노드까지 내려가며 값을 찾는다.

Insert

• 루트를 따라서 값이 큰지 작은지 비교해가며 리프노드까지 내려간 후 값을 추가한다.(기존 구조가 변경되지 않는다.)

Delete

• 사전작업으로 Search를 이미 했다고 가정한다.
• 3가지 케이스가 있다