초록 ▼

본 발명은 연속된 키(key) 값을 가지고 있는 레코드(record)들이 같은 내용을 보유하고 있을 때 특정 키 값에 해당하는 레코드의 내용을 효율적으로 탐색할 수 있도록 하는 구간 이진 탐색 트리 자료 구조를 개시한다. 또한, 본 발명은 상기 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법 및 상기 탐색 방법을 실현하기 위한 프로그램이 저장된 기록매체를 개시하는데, 그 기록매체에 저장된 프로그램에 의한 이진 탐색 트리 자료구조에 대한 탐색 방법은, 동일한 정보를 가지고 있는 연속된 구간에 포함된 복수의 노드를 표현하는 구간

본 발명은 연속된 키(key) 값을 가지고 있는 레코드(record)들이 같은 내용을 보유하고 있을 때 특정 키 값에 해당하는 레코드의 내용을 효율적으로 탐색할 수 있도록 하는 구간 이진 탐색 트리 자료 구조를 개시한다. 또한, 본 발명은 상기 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법 및 상기 탐색 방법을 실현하기 위한 프로그램이 저장된 기록매체를 개시하는데, 그 기록매체에 저장된 프로그램에 의한 이진 탐색 트리 자료구조에 대한 탐색 방법은, 동일한 정보를 가지고 있는 연속된 구간에 포함된 복수의 노드를 표현하는 구간 노드를 생성하는 제1과정; 상기 구간 노드에 의해 생성된 이진 탐색 트리에서 탐색대상이 되는 키가 현재 탐색중인 노드의 구간에 속하면, 상기 노드의 포인터를 상기 키의 포인터로 출력하는 제2과정; 상기 키가 현재 탐색중인 노드의 구간에 속하지 않으면, 상기 키가 포함되는 구간이 검출될 때까지 상기 노드의 하위 서브 트리에 구성되는 노드들에 대해 상기 키에 대한 상기 제2과정을 수행하는 제3과정을 포함한다.

대표청구항 ▼

이진 탐색 트리를 구성하는 자료 구조를 생성하는 방법에 있어서,연속되는 키 값을 가지면서 동일한 정보를 갖는 복수의 노드를 하나의 구간노드로 표현하고, 상기 구간 노드는 상기 노드들 중 가장 작은 키 값을 저장하는 필드와, 구간의 가장 큰 키 값을 저장하는 필드와, 왼쪽 자식(child) 구간노드를 지시하는 포인터를 저장하는 필드와, 오른쪽 자식 구간노드를 지시하는 포인터를 저장하는 필드와, 노드가 저장하고 있는 정보 또는 노드 정보가 저장된 장소를 지시하는 포인터를 저장하는 필드로 구성하는 것을 특징으로 하는 구간 이진 탐색

이진 탐색 트리를 구성하는 자료 구조를 생성하는 방법에 있어서,연속되는 키 값을 가지면서 동일한 정보를 갖는 복수의 노드를 하나의 구간노드로 표현하고, 상기 구간 노드는 상기 노드들 중 가장 작은 키 값을 저장하는 필드와, 구간의 가장 큰 키 값을 저장하는 필드와, 왼쪽 자식(child) 구간노드를 지시하는 포인터를 저장하는 필드와, 오른쪽 자식 구간노드를 지시하는 포인터를 저장하는 필드와, 노드가 저장하고 있는 정보 또는 노드 정보가 저장된 장소를 지시하는 포인터를 저장하는 필드로 구성하는 것을 특징으로 하는 구간 이진 탐색 트리 자료 구조 생성방법.동일한 정보를 가지고 있는 연속된 구간에 포함된 복수의 노드를 표현하는 구간 노드를 생성하는 제1과정;상기 구간 노드에 의해 생성된 이진 탐색 트리에서 탐색대상이 되는 키가 현재 탐색중인 노드의 구간에 속하면, 상기 노드의 포인터를 상기 키의 포인터로 출력하는 제2과정;상기 키가 현재 탐색중인 노드의 구간에 속하지 않으면, 상기 키가 포함되는 구간이 검출될 때까지 상기 노드의 하위 서브 트리에 구성되는 노드들에 대해 상기 키에 대한 상기 제2과정을 수행하는 제3과정을 포함하는 것을 특징으로 하는 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법. 제 1 항에 있어서,상기 구간 노드는 구간의 작은 키 값을 저장하는 필드와, 구간의 가장 큰 키 값을 저장하는 필드와, 왼쪽 자식(child) 구간노드를 지시하는 포인터를 저장하는 필드(lc)와, 오른쪽 자식 노드를 지시하는 포인터를 저장하는 필드(rc)와, 노드가 저장하고 있는 정보 또는 노드 정보가 저장된 장소를 지시하는 포인터를 저장하는 필드로 구성됨을 특징으로 하는 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법. 제 3 항에 있어서,상기 제2탐색과정에서상기 탐색키가 상기 현재 탐색중인 노드의 가장 작은 키 값보다 작으면 상기 구간노드의 상기 필드(lc)에 저장된 포인터를 이용하여 왼쪽 서브 트리의 노드에 대해 제1탐색과정을 수행하고, 상기 탐색키가 상기 현재 탐색중인 노드의 가장 큰 키 값보다 크면 상기 구간노드의 상기 필드(rc)에 저장된 포인터를 이용하여 오른쪽 서브 트리의 노드에 대해 제1탐색과정을 수행하는 것을 특징으로 하는 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법. 제 2 항에 있어서,상기 제 1 탐색과정에서상기 현재 탐색중인 노드의 포인터가 null인가를 판단하여, 상기 노드의 포인터가 null이면 상기 탐색키의 포인터를 null 포인터로 출력하고 상기 구간 이진 탐색 트리 자료 구조에 대한 탐색 과정을 종료하는 과정을 더 포함하여 구성된 것을 특징으로 하는 구간 이진 탐색 트리 자료 구조에 대한 탐색 방법. 동일한 정보를 가지고 있는 연속된 구간에 포함된 복수의 노드를 표현하는 구간 노드를 생성하는 제1프로그램;상기 구간 노드에 의해 생성된 이진 탐색 트리에서 탐색대상이 되는 키가 현재 탐색중인 노드의 구간에 속하면, 상기 노드의 포인터를 상기 키의 포인터로 출력하는 제2프로그램; 및상기 키가 현재 탐색중인 노드의 구간에 속하지 않으면, 상기 키가 포함되는 구간이 검출될 때까지 상기 노드의 하위 서브 트리에 구성되는 노드들에 대해 상기 키에 대한 상기 제1프로그램을 수행하는 제3프로그램을 포함하는 구간 이진 탐색 트리 자료 구조에 대한 탐색 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.