Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 간격 트리


이 섹션에서는 간격 트리가 무엇인지 볼 것입니다. 이름에서 알 수 있듯이 간격 나무는 간격과 관련된 나무입니다. 따라서 간격 트리에 대해 논의하기 전에 기본 간격을 살펴보겠습니다.

간격은 기본적으로 범위입니다. 따라서 하나의 간격이 [a, b]로 작성되면 범위가 b에서 시작하여 b에서 끝나는 것을 나타냅니다.

이제 간격 [10, 20]이 있다고 가정합니다. 따라서 세 가지 범위 값이 있습니다. 첫 번째는 -∞에서 10, 10에서 20, 마지막으로 20에서 ∞

데이터 구조의 간격 트리

이제 [15, 25]에서 두 번째 간격을 생성한다고 가정합니다. 그래서 이것은 다음과 같을 것입니다 -

데이터 구조의 간격 트리

[18, 22]에서 다른 간격을 만들면 다음과 같습니다. -

데이터 구조의 간격 트리

따라서 다른 간격과 하위 간격이 있습니다. 아래와 같습니다.

간격 이름 간격 범위 하위 간격
간격 1 [10, 20] [10, 15], [15, 18], [18, 20]
간격 2 [15, 25] [15, 18], [18, 20], [20, 22], [22, 25]
간격 3 [18, 22] [18, 20], [20, 22]

이 정보에서 간격 트리를 만들 수 있습니다. 하위 간격은 하위 트리 안에 배치됩니다.

간격 트리에서 모든 리프 노드는 모든 기본 간격을 나타냅니다. 이 잎 위에 완전한 이진 트리를 빌드합니다.

데이터 구조의 간격 트리