데이터 구조(3)-이진 탐색 트리



이진 탐색 트리 (binary search tree)

이진 탐색 트리는 그래프의 트리 구조를 사용한다

- 중복이 불가능 하다

- 각 노드는 최대 2개의 자식 노드를 가진다

- 자식 노드의 왼쪽은 자신보다 작고 오른쪽 자식노드는 자신보다 크다

▷모든 노드는 왼쪽가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다

▷모든 노드는 그 오른쪽가지에 포함되는 어떤 숫자보다 작은 숫자가 된다

이진 탐색 트리

왼쪽 가지만 따라가면 최솟값 오른쪽 가지만 따라가면 최대값이 나온다

 



이진 탐색 트리 삽입

데이터 삽입시 노드와 비교하여 내려간다

 

 

이진 탐색 트리 삭제

삭제 할때 자식노드가 없으면 대상만 삭제하고 만약 자식노드가 1개이면 삭제한 위치로 자식노드를 이동시킨다

자식 노드가 있는 경우

​ ​ ​ ​ ​ ​

​