-1) 트리 개념
트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖는 자료구조
프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용
트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양
- 노드 : 트리를 구성하는 요소
- 루트 노드 : 노드 중 가장 위에 있는 노드
- 간선 (엣지) : 노드와 노드 사이를 이어주는 선
트리는 노드가 단방향 간선으로 연결되어 있고 루트노드에서 각 노드까지의 경로는 유일함 - 레벨 : 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수 (depth)
- 부모-자식 관계 : 연결된 것 중 상대적으로 위에 있는 노드를 부모노드, 아래 있는 노드를 자식 노드
- 형제 노드 : 같은 부모를 갖는 노드
- 말단 노드 : 자식이 없는 노드
- 차수 : 특정 노드에서 아래로 향하는 간선의 개수
트리의 종류는 굉장히 다양하지만 코딩 테스트에서는 이진 트리만 제대로 알고 있으면 충분하다 !
이진 트리란 모든 노두의 최대 차수가 2를 넘지 않는 트리 ( 간선이 최대 2개인 트리 )
-2) 이진 트리 표현하기
1. 배열로 표현하기
배열은 선형 자료구조이고 트리는 계층 자료구조
따라서 배열로 트리를 표현하려면 아래 3가지 규칙이 필요함
- 루트 노드는 배열 인덱스 1번에 저장한다
- 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x2이다
- 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x2+1이다
부모-자식 관계를 곱셈 연산하여 배열의 인덱스로 사용하기 때문에 실제 노드 개수보다 많은 공간을 사용함 -> 메모리 낭비
하지만 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 좋고 대부분 코딩 테스트에서는 배열로 이진 트리를 구현해도 괜찮은 경우가 많다 !
cf ) 이진 트리의 노드가 N개 일 때 배열로 이진 트리를 생성한다면 O(N)이 걸림
이진트리 순회하기
순회란 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것
이진트리에서의 순회에는 아래 3가지 방법이 있음
그리고 순회에서 주목해야할 것은 " 현재 노드를 부모 노드로 생각했을 때 "
-
전위 순회 : 현재 노드를 부모 노드로 생각했을 때 부모 노드-왼쪽 자식노드-오른쪽 자식 노드
-> 전위 순회는 거치는 노드를 우선 방문(출력)하므로 직관적으로 이해하기 쉬움
-> 트리를 복사할 때 많이 사용 -
중위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식노드-부모 노드-오른쪽 자식 노드
-> 중위 순회는 거쳐가는 노드, 즉 현재 노드를 거치기만 할 뿐 방문하지 않음
-> 트리에서 정렬된 순서대로 값을 가져올 때 사용 -
후위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식노드-오른쪽 자식 노드-부모 노드
-> 노드를 삭제할 때는 부모 노드가 아닌 자식 노드 부터 삭제해야함
-> 트리 삭제에 자주 사용
2. 포인터로 표현하기
배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않지만,
실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열보다 조금 높음
-3) 이진트리 탐색하기
이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것
-> 이진 탐색 트리
이진 탐색 트리 구축하기
이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 가짐
데이터를 전부 삽입한 다음 정렬하는 것이 아니라 데이터를 하나씩 삽입하면서 이진 탐색 트리를 구축함 즉, 삽입과 동시에 정렬 !
이진 탐색 트리 탐색하기
- 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색
- 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색
- 값을 찾으면 종료, 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것
배열 탐색과 비교하면 어떨까?
배열은 각각 비교 연산을 하지만 이진탐색 트리는 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 탐색이 훨씬 빠름
이진 탐색 트리의 시간 복잡도
이진 탐색 트리의 시간 복잡도는 트리 균형에 의존
균형이 잘 잡혀있는 트리는 O(logN), 아니라면 배열과 동일 O(N)
균형이 잘 잡혀 있다는 것은 왼쪽과 오른쪽 서브 트리의 높이 차가 1 이하인 경우
치우쳐진 형태의 트리 vs 균형 이진 탐색 트리 (AVL 트리, 레드블랙트리 등)
균형 이진 탐색 트리 구현은 난이도가 너무 높아서 내가 보게 될 코딩 테스트에는 나오지 않을 가능성이 매우 높음 !
