본문으로 건너뛰기

이진 검색 트리

트리

트리는 부모와 자식 노드로 구성된 자료구조이다. 리스트는 선형적이지만, 트리는 비선형적이다.

트리의 구성요소

  • Root: 최상위 노드
  • Child: Root와 멀어지는 방향으로 다른 노드와 직접 연결된 노드
  • Parent: Child의 반대
  • Siblings: 같은 Parent를 가지는 노드들
  • Leaf: Child가 없는 노드
  • Edge: 노드와 노드의 연결

사용처

  • HTML DOM
  • 네트워크 라우팅
  • 추상구문트리
  • 인공지능
  • 운영체제의 폴더들
  • 컴퓨터 파일시스템

이진 트리

이진트리는 각 노드가 최대 두 개의 자식노드를 가지는 자료구조이다.

사용처

  • 결정 트리
  • 데이터베이스 인덱스
  • 정렬 알고리즘

이진 검색 트리

  • 이진검색트리는 각 노드가 최대 두개의 자식 노드를 가진다.
  • 왼쪽 자식노드 키는 부모 노드 키보다 작다.
  • 오른쪽 자식노드 키는 부모 노드 키보다 크다.
  • 중복된 키는 허용하지 않는다.

시간복잡도

  • 삽입: O(log N)
  • 검색: O(log N)
  • 위 시간 복잡도가 보장되지는 않는다. (한쪽으로 치우쳐진 BST인 경우)