검색 트리
-
이진 검색 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 8. 10. 12:06
이진 검색 트리 이진 검색 트리의 특성은 다음과 같다. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 최상위 레벨에 루트가 있으며, 각 노드는 최대 두 개의 자식 노드를 가진다. 노드의 왼쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 작다. 노드의 오른쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 크다. 이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾..
-
검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 9. 15:26
검색 트리 저장된 데이터를 빠른 시간에 검색하기 위해 트리를 사용하는 검색 알고리즘이다. 검색 트리의 요소 레코드 여러 개의 필드로 구성되는 개체의 모든 정보가 저장된 구조 ex) 사람의 레코드: 주민 번호, 이름, 집 주소, 직장 주소, 집 전화번호 등이 포함될 수 있다. 필드 레코드의 각 정보를 나타내는 부분 검색 키(또는 키) 다른 레코드와 중복되지 않고 레코드를 대표할 수 있는 필드 검색 트리의 종류 자식의 수에 따른 분류 이진 검색 트리 최대 두 개의 자식 노드를 가지는 트리 다진 검색 트리 세 개 이상의 자식 노드를 가지는 트리 저장되는 장소에 따른 분류 내부 검색 트리 메인 메모리 내에 모든 데이터가 존재하는 트리 외부 검색 트리 디스크에 저장된 상태로 검색을 진행하는 트리 검색 키가 포함하..