데이터 구조의 높이 편향 좌파 트리

여기에서 높이 균형 좌파 나무(HBLT)가 무엇인지 살펴보겠습니다. 외부 노드라고 하는 특수 노드가 있는 바이너리 트리를 생각해 보세요. 각 빈 하위 트리를 대체합니다. 다른 모든 노드를 내부 노드라고 합니다. . 일부 외부 노드가 일부 이진 트리와 함께 추가되면 이를 확장된 이진 트리라고 합니다. .

이 트리의 잎 가장자리를 고려하지 않으면 그것이 실제 이진 트리입니다. 확장된 바이너리 트리입니다.

이제 s(x) 노드 x에서 하위 트리의 외부 노드까지의 최단 경로 길이입니다. x가 외부 노드인 경우 s(x) 값은 0입니다. x가 내부 노드인 경우 값은 -

min{𝑠(𝐿), 𝑠(𝑅)} + 1

여기서 L과 R은 x의 왼쪽과 오른쪽 자식입니다. 이제 주어진 트리의 s 값을 보자.

HBLT의 정의는 다음과 같습니다. 이진 트리는 모든 내부 노드에서 왼쪽 자식의 s 값이 오른쪽 자식의 s 값보다 크거나 같은 경우에만 높이 균형 좌파 트리(HBLT)입니다.

위의 트리는 HBLT가 아닙니다. 노드 a의 부모는 s(L) =0이고 s(R)은 1입니다. 단, 다른 모든 노드는 HBLT 규칙을 만족합니다. 따라서 해당 노드의 하위 트리를 왼쪽 및 오른쪽으로 사용하면 HBLT로 만듭니다.

일부 다른 정의는 -

• 최대 트리(최소 트리)는 각 노드의 값이 자식 노드보다 크거나 같은 트리입니다.

• 최대 HBLT는 HBLT이며 최대 트리이기도 하고 최소 HBLT는 HBLT이기도 하며 최소 트리이기도 합니다.