[자료구조] 트리

그래프와 트리의 차이

그래프

• 노드와 노드를 연결하는 간선으로 이루어진 자료구조
• 무방향, 방향, 양방향 그래프 존재
• 루트 노드 없음 -> 즉, 부모 자식 존재하지 않음
• 비선형 자료구조

트리

• 두 노드사이 반드시 1개의 경로만 가지며, 사이클이 존재하지 않는 방향그래프
• 그래프의 한 종류
• 비선형 자료구조

이진 트리 (Binary Tree)

이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한 개 이거나 두 개만을 갖는 것이다.
완전 이진 트리, 전 이진 트리, 포화 이진 트리 3가지 종류가 있다.

완전 이진 트리 (Complete Binary Tree)

1) 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
3) 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.
4) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.->?

전 이진 트리 (Fully Binary Tree)

1) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

포화 이진 트리 (Perfect Binary Tree)

1) 포화 이진트리는 모든 레벨이 노드로 꽉 차 있는 트리를 뜻한다.
2) 전 이진트리의 성질도 만족해야 한다. 즉 모든 노드가 0개 혹은 2개의 자식 노드를 갖는다.
3) 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
4) 트리의 노드 개수가 정확히 2^k-1 개여야 한다. 여기서 k는 트리의 높이다.

이진 탐색 트리 (Binary Search Tree)

이진 탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조

특징

1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

탐색

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다.
   

-> 트리의 높이 h 이하의 탐색이 진행된다.

삽입

1. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다( 중복 값 허용 X )
2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.
3. 삽입할 값이 루트노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.
   

삭제

1. 삭제하려는 노드가 단말 노드(leaf node) 일 경우
   삭제할 노드의 부모 노드가 있다면 부모 노드의 자식 노드를 NULL로 만들고, 삭제할 노드를 삭제(메모리 해제)
2. 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
   
   삭제할 노드의 자식노드를 삭제할 노드의 부모노드가 가리키게 하고 해당 노드를 삭제
3. 삭제하려는 노드의 서브 트리가 두 개인 경우
   
   1) 삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다.
   
   2) 삭제할 노드 오른쪽 서브 트리의 가장 작은 자손을 해당 노드의 자리에 올린다.
   

참고 :
https://code-lab1.tistory.com/8?category=1213002
https://code-lab1.tistory.com/10#recentComments