[기본원리] 리스트의 응용. 바이너리 서치 트리

이전글에서 배열의 응용, 리스트를 포스팅 했습니다.
2010/07/20 - [Programing/기본원리] - 리스트를 이용한 데이터의 추가/삭제

읽기전에 손가락 한번 클릭~ >_<

고마워요 ~ Chu ~ ♥

그렇다면 리스트의 응용인 바이너리 서치 트리는 무엇일가요?

바이너리 서치 트리

바이너리 서치 트리 ( binary serch tree ) 는 리스트에서 응용된 것으로
배열에 요소를 추가할 때 그 크기에 따라 좌,우 두 방향으로 나뉘어지는 리스트를 만든 것입니다.


예를들어 , 제일 처음 값이 '10' 이라면 다음에 저장되는 값이 10보다 크면 오른쪽에 저장하고, 10보다 작으면 왼쪽에 저장하는 구조이지요~

여기에서 실제 메모리가 두 방향으로 나뉘어져 있는것은 아니며,
이렇게 분류하는 작업은 프로그램 내부적으로 수행됩니다.

바이너리 서치 트리의 구현은 배열이 가진 각각의 요소에 데이터와 좌우 두개의 인덱스 관련 정보를 추가하면 됩니다. 어찌되었든 바이너리 서치 트리는 리스트를 발전시킨 데이터형이기 때문에 데이터의 추가/삭제도 효율적으로 이루어 지겠지요.

데이터 검색에서도 마찬가지로 배열과는 반대로, 찾으려는 데이터가 지금 읽고있는 데이터보다 작으면 리스트의 왼쪽을, 크면 리스트의 오른쪽을 검색하면 되기 때문에 데이터를 조금 더 빨리 찾을 수 있습니다.

지금까지 알아보았던
스택, 큐, 리스트, 바이너리 서치 트리들은 모두 데이터형의 기본이 배열입니다.
2010/07/18 - [Programing/기본원리] - 메모리의 스택과 큐의 이용.



바이너리 서치 트리는 실제 네트워크의 라우팅 테이블 등에서 사용되고 있고,
검색 자료가 많거나 일정한 계층을 이루는 DB 에서도 유용할것 같네요~