교수: Srini Devadas |
이진 검색 트리에 대하여 배워 봅니다.
이진 검색 트리를 간략하게 설명하면 이렇습니다.
이진 검색 트리는 이진 트리 자료 구조로서 각 node들은
어떤 값을 갖고 있습니다. 그런데 각 node 들은 왼쪽과 오른쪽에
각각의 서브 트리를 가질 수 있습니다.
그런데 이진 검색 트리에서 어떤 node가 서브 트리를
가질 때에는 특별한규칙이 있습니다.
그것은 어떤 node에 있어서 그 node가 서브트리를 가질 때에
반드시 이진 검색 트리여야 한다는 것입니다. 즉,
그 node 의 왼쪽은 그 node의 값 보다는 반드시 작은 값들의
node 들로 되어 있으며, 그 오른쪽은 그 node의 값보다는
큰 값들을 갖는 그런 node 들로 이루어져 있어야 한다는 것입니다.
그러면 이제 이진 검색 트리에서 검색하는 원리를 알아보겠습니다.
이진 검색 트리에서 주어진 키와 같은 node를 검색한다 합시다.
이럴 때, 이진 검색 트리를 검색하는 방법은 이렇습니다.
이진 검색 트리에 같은 node 가 있다면 그 node를 반환합니다.
검색하려 하는 값을 루트 node와 비교하여 그 값이 같다면
루트 node를 반환합니다. 그런데 값이 다르다면 루트 node 의
크기 보다 작을 때 왼쪽 서브 트리에서 이 과정을 반복합니다.
그런데 이때 값이 루트 node의 크기보다 클 때에는
오른족 서브 트리에서 이 과정을 반복합니다.
다음으로 이진 검색 트리에서 node를 삽입하는 방법을 알아보겠습니다.
이진 검색 트리에서 node를 삽입하는 방법은 이렇습니다.
삽입 하기 위하여 먼저 삽입하려는 트리를 검색 합니다.
그런 다음 주어진 키와 일치 하는 node가 없다면
주어진 키와 제일 끝에 있는 node 를 비교하여 그 node의
왼쪽이나 오른쪽에 node를 새롭게 삽입합니다.
자료 출처 :위키백과 참고