Binary search Tree

Binary search Tree

1. 탐색작업을 효율적으로 하기 위한 자료구조

2. 모든 원소는 서로 다른 유일한 키를 가짐

3. key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)

4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리

5. 중위 순회하면 오름차순으로 정렬된 값을 얻는다.

 

탐색 연산

1. 루트에서 시작

2. 탐색할 키값 x를 루트 노드의 키값과 비교

- 키값 x = 루트 노드의 키값 : 원하는 원소를 찾았으므로 성공

- 키값 x < 루트 노드의 키값 : 루트 노드의 왼쪽 서브트리에 대해서 탐색 연산 수행

- 키값 x > 루트 노드의 키값 : 루트 노드의 오른쪽 서브트리에 대해서 탐색 연산 수행

3. 서브트리에 대해서 순환적으로 탐색 연산 반복

 

삽입 연산

1. 먼저 탐색 연산 수행

- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인

- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치

2. 탐색 실패한 위치에 원소 삽입

 

Binary search Tree의 성능

1. 탐색(searching), 삽입(insertion), 삭제(deletion) 시간은 트리의 높이에 좌우됨. O(h)

2. 평균의 경우 : 이진 트리가 균형적으로 생성되어 있는 경우. O(log n)

3. 최악의 경우 : 한쪽으로 치우친 경사 이진 트리의 경우. O(n). 순차탐색과 시간복잡도가 같음.

완전 이진 트리 또는 균형 트리로 바꿀 수 있다면 최악의 경우를 없앨 수 있음. 평균과 최악의 시간이 O(long n)

 

 

 

by SW expert academy