이 섹션에서는 간격 트리가 무엇인지 볼 것입니다. 이름에서 알 수 있듯이 간격 나무는 간격과 관련된 나무입니다. 따라서 간격 트리에 대해 논의하기 전에 기본 간격을 살펴보겠습니다.
간격은 기본적으로 범위입니다. 따라서 하나의 간격이 [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] |
이 정보에서 간격 트리를 만들 수 있습니다. 하위 간격은 하위 트리 안에 배치됩니다.
간격 트리에서 모든 리프 노드는 모든 기본 간격을 나타냅니다. 이 잎 위에 완전한 이진 트리를 빌드합니다.