Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 자바
- 네트워크
- spring
- Flutter
- python
- DB
- CS지식
- 데이터베이스
- backjoon
- 스프링
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- Java
- Spring Security
- postgresql
- 데이터
- javascript
- springboot
- 백준
- CS
- JPA
- 플러터
- 스프링부트
- 자바스크립트
- 자료구조
- 파이썬
- 시큐리티
- 리눅스
- Oracle
- baekjoon
- 프로그래머스
Archives
- Today
- Total
Jin's Dev Story
[자료구조] 이진 탐색 트리(Binary Search Tree) 본문
이진 탐색 트리의 목적
이진 탐색 + 연결 리스트
- 이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능
- 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)
⇒ 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'
⇒ 즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 하기
특징
- 각 노드의 자식이 2개 이하
- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
- 중복된 노드가 없어야 함
중복이 없어야 하는 이유
- 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음
- (트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적)
이진탐색트리의 순회는 '중위순회(inorder)' 방식 (왼쪽 - 루트 - 오른쪽)
중위 순회로 정렬된 순서를 읽을 수 있음
BST 핵심연산
- 검색
- 삽입
- 삭제
- 트리 생성
- 트리 삭제
시간 복잡도
- 균등 트리 : 노드 개수가 N개일 때 O(logN)
- 편향 트리 : 노드 개수가 N개일 때 O(N)
삭제의 3가지 Case
- 자식이 없는 leaf 노드일 때 → 그냥 삭제
- 자식이 1개인 노드일 때 → 지워진 노드에 자식을 올리기
- 자식이 2개인 노드일 때 → 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기
편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음)는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라짐
→ 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, RedBlack Tree
'CS 지식 > [자료구조]' 카테고리의 다른 글
[자료구조] HashMap (0) | 2023.08.01 |
---|---|
[자료구조] 해시(Hash) (0) | 2023.07.19 |
[자료구조] 트리(Tree) (0) | 2023.07.19 |
[자료구조] 힙(Heap) (0) | 2023.07.19 |
[자료구조] 스택 & 큐 (0) | 2023.07.19 |