이진 탐색 트리(Binary Search Tree)
모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가진다.
최소값은 트리의 가장 왼쪽, 최대값은 가장 오른쪽에 존재한다.
중위 순회(inorder traversal)
노드의 값을 오름차순으로 방문한다.
방문 순서
재귀적으로 왼쪽 서브 트리 순회, 현재 노드를 방문(e.g. 값 출), 재귀적으로 오른쪽 서브트리 순회
3 - 5 - 10 - 15 - 17 - 20 - 30 - 40 - 50전위 순회(preorder traversal)
루트 노드를 먼저 방문
방문 순서
현재 노드 방문(e.g. 값 출력), 재귀적으로 왼쪽 서브트리 순회, 재귀적으로 오른쪽 서브 트리 순회
20 - 5 - 3 - 15 - 10 - 17 - 50 - 30 - 40후위 순회(postorder traversal)
서브트리를 문저 순회하고 마지막에 루트 노드를 방문
방문 순서
재귀적으로 왼쪽 서브 트리 순회, 재귀적으로 오른쪽 서브 트리 순회, 현재 노드 방문(e.g. 값 출력)
3 - 10 - 17 - 15 - 5 - 40 - 30 - 50 - 20노드의 successor(후임자)
해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드
ex) 20의 successor : 30, 17의 successor : 20
노드의 predecessor(선임자)
해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드
ex) 20의 predecessor : 17, 10의 predecessor : 5
이진 탐색 트리에서의 삭제
자녀가 없는 노드 삭제인 경우
삭제될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록 처리
자녀가 하나인 노들르 삭제하는 경우
삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변환
자녀가 두개인 노드를 삭제하는 경우
삭제될 노드의 오른쪽 서브트리에서 제일 값이 작은 노드가 삭제될 노드를 대체
시간 복잡도
장점
삽입 삭제가 유연해서 값의 크기에 따라 좌우 서브트리가 나눠지기 때문에 삽입/삭제/검색이 보통은 빠르다. 또한 값의 순서대로 순회 가능하다.
단점
트리가 구조적으로 한쪽으로 편향되면 삽입 삭제 검색 등등 여러 동작들의 수행 시간이 악화된다.
이 문제를 해결하기 위해서 스스로 균형을 잡는 이진 탐색 트리가 사용된다. EX) AVL 트리, Red-Black 트리가 있다.
이 게시글은 https://www.youtube.com/watch?v=i57ZGhOVPcI&list=PLcXyemr8ZeoT-_8yBc_p_lVwRRqUaN8ET&index=30 참조하여 작성하였습니다.
'코딩테스트 준비 > 자료구조 & 알고리즘' 카테고리의 다른 글
| C# - 배열을 문자열로 바꾸는 방법 (0) | 2024.04.08 |
|---|---|
| 알고리즘 - 그리디(Greedy) 알고리즘 (1) | 2024.03.26 |
| C# - 백준 코드 처리 속도(실행 시간) 측정 방법 +) Stopwatch 프로퍼티 및 메서드 설명 (0) | 2024.03.17 |
| C# - 우선순위 큐(Priority Queue)와 힙(Heap) (0) | 2024.03.16 |
| C# - 메서드안에서 재귀호출시 실행과정을 알아보자 (0) | 2023.12.22 |
댓글