Binary Search Tree(BST)

지식저장공간·2023년 2월 14일
0

자료구조

목록 보기
13/17

Binary Search Tree

기본개념

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값도가 큰 값들만 가진다.

ex) root node를 기준으로 오른쪽 서브트리의 모든 노드들은 20보다 크지만,
왼쪽 서브트리의 노드들은 20보다 작다.

==> ★모든 서브트리를 기준으로도 해당 규칙이 적용된다.

최소값

이진 탐색 트리의 최소값은 트리의 가장 왼쪽에 존재한다.
ex) 3 ==>더이상 왼쪽 서브쿼리가 존재하지 않는다.

최대값

이진 탐색 트리의 최대값은 트리의 가장 오른쪽에 존재한다.
ex) 50 ==>더이상 오른쪽 서브쿼리가 존재하지 않는다.

후임자(successor)

해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드
ex) 해당 노드의 수직선을 기준으로 바로 오른쪽 노드

선임자(predecessor)

해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드
ex) 해당 노드의 수직선을 기준으로 바로 왼쪽 노드

순회 방법

순회란, BST에 존재하는 모든 노드들을 한번씩 탐색한다. 시작은 root node에서 출발하며 순회 방법에는 여러가기 방법이 존재한다.

inorder traversal(중위 순회)

1) 20>5>3 더 이상 왼쪽 노드가 존재하지 않기 때문에 3을 출력
2) 3을 기준으로 오른쪽 노드가 존재하지 않기 때문에 5로 올라간 후 5노드의 왼쪽 순회가 더이상 존재하지 않기 때문에 5를 출력
3) 5>15>10 10출력
4) 10 출력 후 오른쪽 노드가 존재하지 않고 15기준으로 왼쪽 순회가 끝났기 때문에 15 출력 후 17로 이동 후 노드가 존재하지 않아 17 출력
5) root node를 기준으로 왼쪽 서브 트리의 순회가 모두 끝났기 때문에 root node까지 올라가며 20출력 후 root node 오른쪽 서브트리로 이동
6) 30 > 40 > 50을 순서대로 출력한다.

result : 3 5 10 15 17 20 30 40 50

출력 결과를 확인해보면 작은 수 부터 차례대로 출력된다.

preorder traversal(전위 순회)

현재 노드를 먼저 방문하고 출력한다. 그 후 재귀적으로 왼쪽 서브 트리 순회 후 오른쪽 서브 트리를 순회 한다.

postorder traversal(후위 순회)

재귀적으로 왼쪽 서브 트리 순회, 재귀적으로 오른쪽 서브 트리 순회 후 현재 노드 방문 값 출력.

이진 탐색 트리의 삽입/삭제

삽입

insert(50); insert(70); insert(90); insert(80); insert(99);
insert(30); insert(40); insert(20);

삭제

leaf node, 자녀가 없는 노드를 삭제 : 삭제될 노드를 가리키던 레퍼런스가 가리키는 것이 없도록 처리한다.

자녀가 하나인 노드 삭제 : 삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변경한다.

delete(50);

자녀가 둘인 노드 삭제 : 삭제될 노드의 왼쪽 or 오른쪽 서브트리에서 대체할 노드를 선택.
1) 왼쪽 : 삭제될 노드의 값보다 작지만 가장 큰값이 삭제될 노드를 대체한다.
2) 오른쪽 : 삭제될 노드의 값보다 크지만 가장 작은값이 삭제될 노드를 대체한다.
==> 선임자 or 후임자가 삭제될 노드를 대체한다.
==> 이진 탐색 트리의 특성을 유지시킬 수 있다.

add(85);

시간 복잡도

root node를 추가, 삭제, 검색한다 가정하면 best case는 세타(1)

이진탐색 시 평균 O(logN), 1/2씩 줄여 나갈 수 있다.

이진 탐색 트리의 장점

삽입, 삭제가 유연하다.

값의 크기에 따라 좌우 서브트리가 나눠지기 때문에 삽입/삭제/검색이 빠르다.

값의 순서대로 순회가 가능하다. (inorder traversal)

이진 탐색 트리의 단점

worst case

최악의 경우에 모든 노드를 검색해야한다.

트리가 구조적으로 한쪽으로 편향되면 삽입/삭제/검색 등 여러 동작들의 수행시간이 악화된다.
ex) root node가 100인 상태에서 insert되는 값들이 모두 100보다 작은경우

단점 해결 케이스

이 문제를 해결하기 위해 스스로 균형을 잡는 이진 탐색 트리가 사용된다.
:: AVL트리, Red-Black 트리 => 한쪽에 편향되지 않은 이진 탐색 트리
:: worst case에서도 O(logN)

출처 : 쉬운코드 유튜브

profile
발전하는 개발자가 꿈입니다. 지식을 쌓고 지식을 활용해 목표 달성을 추구합니다.

0개의 댓글