이진 검색 트리
트리
트리는 부모와 자식 노드로 구성된 자료구조이다. 리스트는 선형적이지만, 트리는 비선형적이다.
트리의 구성요소
- Root: 최상위 노드
- Child: Root와 멀어지는 방향으로 다른 노드와 직접 연결된 노드
- Parent: Child의 반대
- Siblings: 같은 Parent를 가지는 노드들
- Leaf: Child가 없는 노드
- Edge: 노드와 노드의 연결
사용처
- HTML DOM
- 네트워크 라우팅
- 추상구문트리
- 인공지능
- 운영체제의 폴더들
- 컴퓨터 파일시스템
이진 트리
이진트리는 각 노드가 최대 두 개의 자식노드를 가지는 자료구조이다.
사용처
- 결정 트리
- 데이터베이스 인덱스
- 정렬 알고리즘
이진 검색 트리
- 이진검색트리는 각 노드가 최대 두개의 자식 노드를 가진다.
- 왼쪽 자식노드 키는 부모 노드 키보다 작다.
- 오른쪽 자식노드 키는 부모 노드 키보다 크다.
- 중복된 키는 허용하지 않는다.
시간복잡도
- 삽입: O(log N)
- 검색: O(log N)
- 위 시간 복잡도가 보장되지는 않는다. (한쪽으로 치우쳐진 BST인 경우)