트리 개념
데이터를 저장하고 탐색하기에 유용한 구조
트리의 특성을 활용하는 분야
계층구조를 표현하는 용도로 많이 사용함. 예를 들어 파일 시슴템이나 디렉터리 구조 등을 트리로 구성하거나 관리 할 수 있다.
1. 인공지능(AI)
- 인공지능의 판단 기준을 만들때 의사 결정 트리를 사용
2. 자동 완성 기능
- 검색 엔진 등에서 자동 검색어 추천 기능 등
3. 데이터 베이스
- 데이터를 쉽게 검색, 삽입, 삭제 할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱 함.
트리의 구성 요소
- 노드: 트리를 구성하는 요소이다. 노드 중 가장 위에 있는 요소를 루트 노드라고 한다. 가장 아래의 자식이 없느 노드는 리프 노드라고한다.
- 에지: 노드와 노드 사이를 이어주는 선. 녿와 노드는 단방향으로 이루어져있고, 루트 노드에서 각 노드까지의 경로는 유일하다.
- 차수: 특정 노드에서 아래로 향하는 간선의 개수
부모-자식, 형제 관계를 가지는 노드
간선으로 연결된 노드들은 서로 부모-자식 관계를 가진다고 표현한다. 상대적으로 위에 존재하는 노드를 부모 노드 아래에 있는 노드를 자식 노드라고 한다. 같은 부모노드를 같는 노드를 형제 노드라고 한다.
이진 트리 표현하기
이진 트리는 배열이나 포인터로 구현 할 수 있다.
배열로 표현하기
배열은 선형 자료구조이고, 노드는 계층 자료구조이다. 따라서 배열로 트리를 표현하렴면 3가지 규칙이 필요하다/
- 루트 노드는 배열 인덱스 1번에 저장한다.
- 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x2 이다.
- 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x2+1 이다.
트리를 표현한 배열은 빈 값이 존재한다. 노드들의 부모-자식 관계를 곱셈 연산하여 배열의 인덱스로 사용하기 때문에 실제 노드 갯수보다 많은 공간을 사용하기 때문에 메모리의 낭비가 존재한다. 메모리가 넉넉하다면 구현 시간을 단축하기 위해 사용하는것도 괜찮다.
이진 트리 순회하기
전위 순회
- 현재 노드를 부모 노드로 생각했을때 부모노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문
중위 순회
- 현재 노드를 부모 노드로 생각했을때 왼쪽 자식 노드 -> 부모노드 -> 오른쪽 자식 노드 순서로 방문
후위 순회
- 현재 노드를 부모 노드로 생각했을때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모노드 순서로 방문
포인터로 표현하기
노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다.
이진 트리 탐색하기
이진 트리에서 가장 중요한 것은 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것이다.
이진 탐색 트리 구축하기
- 이진 탐색 트리는 데이터의 크기를 다져 현재 노드보다 값이 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 가진다.
- 데이터는 한번에 삽입후 정렬하는 것이 아니라 데이터를 하나씩 삽입하면서 이진 탐색 트리를 구축한다.
이진 탐색 트리 탐색하기
탐색의 방법은 아래와 같다.
- 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색한다.
- 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색한다.
- 값을 찾으면 종료한다. 노드가 없을 때 까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것이다.
배열탐색과의 차이점
- 배열에서는 값을 순차적으로 탐색하며 값을 찾으나 이진 탐색 트리는 비교 연산을 통해 더 적은 횟수의 탐색으로 값을 찾는다. 즉 이진 탐색 트리가 훨씬 빠르다
- 이진 탐색 트리의 구축 방식 자체가 갖는 특성은 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색을 빠르게 만들어준다.
이진 탐색 트리의 시간 복잡도
- 이진 탐색 트리의 시간 복잡도는 균형에 의존한다. 균형이 유지된다고 가정했을 때 시간 복잡도는 O(logN)이다. 균형이 맞지 않을 경우 시간 복잡도는 O(N)으로 배열과 비슷하다.
