[Data Structure] Binary Search Tree(이진 탐색 트리)

 

이진 탐색 트리(BST)

이진 탐색 트리란 정렬된 이진 트리로 다음과 같은 속성을 가지고 있다.

 

• 왼쪽 자식 노드에 있는 값은 부모 노드의 값 보다 작아야 한다
• 오른쪽 자식 노드에 있는 값은 부모 노드의 값 보다 커야 한다

** 일반적으로 BST는 중복 값을 허용하지 않는다

 

데이터를 삽입, 삭제, 검색할 때 평균적으로 O(log n)의 시간 복잡도를 가진다

한쪽으로 치우친 편향 트리인 경우 O(n)의 시간 복잡도를 가질 수 있다

 

주요 연산

탐색(Search)

• 트리의 루트 부터 시작하여 특정 값을 찾는다
• 특정 값이 현재 노드보다 작으면 왼쪽 크면 오른쪽
• 원하는 값을 찾거나 탐색할 노드가 없으면 종료한다

삽입(Insertion)

• 루트부터 시작하여 새로운 값을 삽입한다
• 현재 노드보다 작으면 왼쪽, 크면 오른쪽
• 빈 자리를 발견하면 그 자리에 새로운 노드를 추가한다

삭제(Deletion)

노드를 삭제하는 경우는 세 가지의 상황이 존재한다

• 자식이 없는 노드 삭제
  단순히 해당 노드만 제거하면 된다.
• 자식이 하나인 노드 삭제
  자식을 부모 노드에 연결하여 삭제한 노드를 대체한다.
• 자식이 두 개인 노드를 삭제
  삭제된 노드의 자리를 오른쪽 서브트리 최소값 또는 왼쪽 서브트리의 최대 값으로 대체한 뒤 해당 노드를 삭제한다.

정렬된 데이터 관리

• BST는 데이터를 정렬된 형태로 유지하며, 삽입/삭제 후에도 이 속성을 유지한다
• 중위 순회(in-order traversal) 를 하면 값들이 항상 오름차순으로 출력된다

중위순회 : 이진 트리를 순회하는 방법으로 다음 순서에 따라 트리의 노드를 방문한다

1. 왼쪽 서브트리를 순회
2. 루트 노드를 방문
3. 오른쪽 서브트리를 순회

장점

• 중위 순회를 통해 정렬된 데이터 제공, 별도의 정렬 작업이 필요없음
• 효율적인 검색 작업
• 데이터의 삽입/삭제에 따라서 크기가 자동으로 조정(동적 자료구조)
• 다양한 조건 검색 가능(최소값, 최대값 찾기/ 특정 값보다 작은 값, 큰 값/ 특정 범위 내의 값)
• 구현의 간단함

실제활용

• 데이터베이스 인덱스
• 검색 알고리즘
• 정렬된 데이터 출력

트리가 한쪽으로 치우치면(편향트리) 성능이 저하되는 단점이 있음

 

BST 구현

삽입

특정값 찾기

최소값, 최대값 찾기

삭제

https://github.com/9mans/tree-practice/blob/master/src/bst/BSTTest.java