트리
데이터를 탐색하고 저장하기에 유용한 구조를 가지고 있다. 데이터를 어떤 방식으로 저장하고 탐색하는지 알아보자.
트리의 특성을 활용하는 분야
- 자동 완성 기능 : 트리는 문자열 처리에도 많이 활용된다. 예를 들어 검색 엔진에서 자동 검색어 추천 기능도 트라이 trie라는 독특한 트리 구조를 활용한 것이다. 이를 활용하면 접두사나 패턴 검색을 쉽게 할 수 있다.
- DB : 데이터베이스를 쉽게 검색, 삽입, 삭제를 할 수 있도록 트리를 활용하여 데이터를 구조화하고 인덱싱한다. 이때 B- 트리나 B+ 트리를 많이 사용한다.
나무를 거꾸로 뒤집어 놓은 모양의 트리
트리를 구성하는 노드
노드중 가장 위에 있는 노드를 루트 노드 라고 한다. 앞의 그림에서는 맨 위에 있는 값 1(A)이 들어 있는 노드가 루트 노드이다.
노드를 연결하는 엣지
노드와 노드 사이를 이어주는 선을 엣지 또는 간선이라고 한다. 트리는 단방향 노드로 연결되어 있으며, 루트 노드에서 각 노드까지의 경로는 유일하다. 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수를 레벨로 표현한다. 예를 들어 루트 노드는 레벨 0, 노드 B,C는 레벨 1이다.
부모-자식, 형제 관계를 가지는 노드
간선으로 연결된 노드들은 서로 부모-자식 관계가 있다고 표현한다. 간선으로 직접 연결된 노드중 상대적으로 위에 있는 노드를 부모 노드, 아래에 있는 노드를 자식 노드라고 한다. F,G처럼 같은 부모를 갖는 노드를 형제노드 라고 한다.
자식이 없는 리프노드 (말단 노드)
자식이 없는 노드는 리프노드 라고 한다.
아래로 향하는 간선의 개수, 차수
차수 란 특정 노드에서 아래로 향하는 간선의 개수이다. 예를 들어 노드 1은 차수가 3이다. 왜냐하면 아래로 향하는 간선이 3개이기 때문이다.
이진 트리 표현하기
이진트리는 다음과 같이 노드 하나가 최대 2개 자식 노드를 갖는다.
배열로 표현하기
배열은 선형 자료구조이고 트리는 계층 자료구조 이다. 따라서 배열로 트리를 표현하려면 다음 3가지 규칙이 필요하다. 참고로 이 규칙은 루트 노드를 배열 인덱스 1번이라고 생각하여 작성한 규칙이다.
인덱스 0부터 시작하는 경우 (부모 노드가 n이라고 할 때)
- 왼쪽 자식 노드의 배열 인덱스 : n x2
- 오른쪽 자식 노드의 배열 인덱스: nx2 +1
- 자식 노드가 인덱스 k 일 때 부모 노드의 인덱스 : (k//2)
인덱스 1부터 시작하는 경우 (부모 노드가 n이라고 할 때)
- 왼쪽 자식 노드의 인덱스 : 2xn + 1
- 오른쪽 자식 노드의 인덱스 : 2xn + 2
- 자식 노드가 인덱스 k 일 때 부모 노드의 인덱스 : (k-1) //2
배열로 트리를 표현하면 빈 값이 꽤 많이 보인다. 자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비된다는 단점이 있다.
하지만 이진 트리를 배열로 표현하는 방식은 굉장히 구현 난이도가 쉬우므로, 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 좋다. 이진 트리의 노드가 N개일 때, 배열로 이진 트리를 생성하면 O(n) 이 걸린다.
배열로 표현한 이진 트리 순회하기
- 전위 순회 : 현재 노드를 부모 노드로 생각했을 때 부모 노드-> 왼쪽 자식 -> 오른쪽 자식 노드 순서로 방문한다.
- 중위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문한다.
- 후위 순회 : 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 -> 오른쪽 자식 -> 부모 노드 순서로 방문한다.
순회에서 주목해야 할 표현은 '현재 노드를 부모 노드로 생각했을 때' 이다. 이 컨셉을 이해해야 순회를 쉽게 이해할 수 있다.
전위 순회 과정
전위 순회는 이렇게 거치는 노드를 우선 방문(출력) 하므로 직관적으로 이해하기 쉽다. 전위 순회는 트리를 복사할 때 많이 사용한다.
중위 순회 과정
중위 순회는 현재 노드를 부모 노드로 생각했을 때 방문 우선 순위가 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 이다. 다시 말해 중위 순회는 거쳐가는 노드 즉, 현재 노드를 거치기만 할 뿐 '방문' 하지 않는다. 바로 이 지점이 처음 공부하는 사람에게 '중위 순회는 난해하다' 라고 여기게 만든다.
방문이란?
방문이란 <탐색을 마친 상태> 를 말한다. 탐색 과정에서 지나치는 것과 그렇지 않은 것을 구분하기 위해 방문이라는 용어를 사용한다.
자식 노드 부터 삭제해야 트리를 유지하며 재귀로 루트 노드까지 삭제할 수 있다. 그래서 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용한다.
포인터로 표현하기
포인터로 트리를 표현하려면 노드부터 정의해야 한다. 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다.
포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않는다. 하지만 실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열로 표현한 트리에 비해 조금 높다.
이진 트리 탐색하기
이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것이다. 이진 트리는 자식 노드가 최대 2개인 트리를 말한다.
이진 탐색 트리 구축하기
이진 탐색 트리는 데이터의 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있다. 데이터를 전부 삽입한 다음 정렬하는 것이 아니라, 데이터를 하나씩 삽입하면서 이진탐색 트리를 구축한다. 즉 삽입과 동시에 정렬을 한다.
이진 탐색 트리 탐색하기
이제 탐색을 해보자. 탐색을 하는 과정은 다음과 같다.
- 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색한다
- 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색한다.
- 값을 찾으면 종료한다. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것으로 판단한다.
배열 탐색과 비교하면 어떨까?
연산 횟수가 현저히 줄어드는 것을 알 수 있다.
모든 탐색 알고리즘에서 탐색 효율을 개선하는 방법은 탐색 대상이 아닌 노드를 한 번에 많이 제외할 수 있으면 된다. 탐색 대상이 아닌 것들을 빠르게 제외하면 원하는 것을 빠르게 찾을 수 있기 때문이다. 이진 탐색 트리의 원리도 동일하다. 이진 탐색 트리의 구축 방식 자체가 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색을 빠르게 만들어준다.
이진 탐색 트리의 시간 복잡도
이진 탐색 트리의 시간 복잡도는 트리 균형에 의존한다. 트리의 균형이 잡혔다는 것은 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 말한다. 균형이 유지되었다고 가정했을 때 삽입과 탐색 연산시, 트리에 저장된 데이터의 갯수가n 개라고 가정하면 시간복잡도는 nlogN 이다. 하지만 균형이 유지되지 못한 경우에는 배열과 시간복잡도가 비슷하다.
균형이 잡혀있다는 것은 왼쪽과 오른쪽 트리의 서브 트리의 높이 차가 1이하인 경우를 말한다.
이진 탐색 트리가 다음과 같은 형태를 하고 있다면 어떨까?
이런 트리에서 7을 찾는다면 모든 노드를 다 탐색해야 하므로 O(n)의 복잡도를 가지게 된다. 다만 이렇게 극단적인 경우는 지극히 예외의 상황이며, 사실 대부분의 상황에서는 이진 탐색 트리의 탐색 성능이 더 좋다.
균형 이진 트리에 대해 자세히 알아보기! (비선형 자료구조)
AVL, 레드 블랙 트리
velog.io
https://product.kyobobook.co.kr/detail/S000210881884
코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고
코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트
product.kyobobook.co.kr
'알고리즘' 카테고리의 다른 글
| [코딩테스트 합격자 되기 10] 집합 (1) | 2024.10.18 |
|---|---|
| [프로그래머스] 영어 끝말잇기 python (0) | 2024.10.13 |
| [코딩테스트 합격자 되기 08] 해시 Q&A (0) | 2024.10.07 |
| [코딩테스트 합격자 되기 08] 해시 (0) | 2024.10.04 |
| [정리] yield 의 동작 방식 (0) | 2024.09.30 |