-
[묘공단] 코딩 테스트 합격자 되기 4주차 - 트리[묘공단] 코딩 테스트 합격자 되기 책 정리 2024. 5. 7. 16:56
이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.
트리
- 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다
- 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤접어 놓은 모양이다
- 나무 밑둥 즉, root가 맨 위에 있다
- 트리는 부모 - 자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조
트리 구성
루트 노드
-> 노드 중 가장 위에 있는 노드를 루트 노드라고 한다
에지
-> 노드와 노드 사이에는 이어주는 선이 있다 이것을 간선 또는 에지 라고 한다
노드
-> 간선으로 연결된 노드들은 서로 부모 - 자식 관계가 있다고 표현한다
간선으로 직접 연결된 노드중 상대적으로 위에 있는 노드를 부모노드, 아래에 있는 노드를 자식 노드라고 한다
자식이 없는 노드는 리프 노드라고 한다
이진 트리 표현
- 트리를 표현하는 방법에는 배열 표현법과 링크 표현법이 있다
배열 표현법 : 각 노드에 인덱스를 부여하여 배열에 저장하는 방법
링크(포인터) 표현법 : 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법
배열 표현법
- 이진 트리의 노드가 N개 일 때 배열로 이진 트리 생성 시 O(N)이 걸림
3가지 규칙 필요
1) 루트 노드는 배열 인덱스 1번에 저장
2) 왼쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2
3) 오른쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2 + 1
포인트 표현법
- 포인터로 트리 표현 시에 노드 부터 정의가 필요하다
- 각 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다
왼쪽 자식 노드 값 오른쪽 자식 노드 이런식으로 노드가 되어 있다
순회
- 전위 순회(Preorder)
현재 노드를 부모 노드로 생각했을 때
부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문 - 중위 순회(Inorder)
현재 노드를 부모 노드로 생각했을 때
왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 방문 - 후위 순회(Postorder)
현재 노드를 부모 노드로 생각했을 때
왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순서로 방문
이진 트리 탐색하기
- 탐색을 효율적으로 할 수 있도록 트리 구축하는 것이다
이진 탐색 트리 (Binary Search Tree)
- 정렬 방식 : 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치한다
- 탐색
- 1) 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드 탐색
- 2) 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드 탐색
- 3) 값을 찾으면 종료. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것이다
- 장점 : 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외 즉, 검색이 빠랄진다
- 시간 복잡도 -> O(logN)
균형 이진 탐색 트리 (Balanced Binary Search Tree)
- 한 쪽으로만 치우쳐지지 않도록 균형을 유지하는 이진 탐색 트리
- AVL 트리, 레드 - 블랙 트리 등으로 구분
- 장점 : 이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN이므로 탐색 시간 복잡도를 O(logN)으로 유지 가능
- 단점 : 구현 난이도가 높다
출처
https://goldenrabbit.co.kr/product/javapass/
[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗
신입 사원 코딩 테스트를 준비하고 계신가요? 코딩 테스트는 문제만 열심히 푼다고 통과할 수 없습니다. 시험은 전략적으로 준비해야 합니다. 《코딩 테스트 합격자 되기》(자바 편)은 신입 사
goldenrabbit.co.kr
'[묘공단] 코딩 테스트 합격자 되기 책 정리' 카테고리의 다른 글
[묘공단] 코딩 테스트 합격자 되기 6주차 (0) 2024.05.25 [묘공단] 코딩 테스트 합격자 되기 5주차 (0) 2024.05.22 [묘공단] 코딩 테스트 합격자 되기 4주차 (0) 2024.05.06 [묘공단] 코딩 테스트 합격자 되기 3주차 (0) 2024.04.29 [묘공단] 코딩 테스트 합격자 되기 2주차 (1) 2024.04.21 - 전위 순회(Preorder)