CS 스터디
알고리즘
이진트리(2)
이진 탐색 트리:
- 이진트리 기반의 탐색을 위한 자료구조. 효율적인 탐색 작업을 위한 자료구조
- 부모 기준에서 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진트리

이진탐색트리의 특징
각 노드에는 고유한 key 가 있다
루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드를로 구성되어있다.
루트노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드를로 구성되어있다.
좌우 서브트리도 모두 이진 탐색 트리여야 한다.

평균적으로 탐색의 시간복잡도는 O(logN). 치우친 경우에는 O(N). 그래서 균형이 중요하다
자가균형 이진탐색 트리는 AVL, 레드블랙 트리 등이 있으며 자바의 해시맵이 체이닝 시 연결리스트와 함께 레드블랙 트리를 병행해 저장한다.

이진 탐색 트리 탐색(Search)
1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브트리로 탐색을 진행
3; 찾고자 하는 값이 루트 노드의 키보다 크면 오른쪽 서브트리로 탐색을 진행
값을 찾을때까지 반복하고 찾지 못하면 종료한다. ( 최대 높이 h 만큼 탐색을 진행)
이진 탐색 트리의 삽입(Insert)
이진 탐색 트리의 삭제(Delete)
알고리즘 문제
Merge Two Binary Trees, Range Sum of BST, Search in a Binary Search Tree, Serialize and Deserialize Binary Tree, Balanced Binary Tree, Minimum Height Trees
PS 스터디
'TIL' 카테고리의 다른 글
[TIL]20220526 (0) | 2022.05.26 |
---|---|
[TIL]20220525 (0) | 2022.05.25 |
[TIL]20220523 (0) | 2022.05.23 |
[TIL]20220522 (0) | 2022.05.22 |
[TIL]20220521 (0) | 2022.05.21 |