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

데이터 구조의 가중치 편향 좌파 트리


여기서 좌파 트리의 또 다른 변형을 볼 수 있습니다. 여기서 우리는 외부 노드에 대한 루트의 최단 경로 길이보다는 하위 트리의 노드 수를 고려할 것입니다. 여기서 노드 x의 가중치 w(x)를 루트 x가 있는 하위 트리의 내부 노드 수로 정의합니다. x가 외부 노드이면 가중치는 0입니다. x가 내부 노드이면 가중치는 자식의 가중치 합보다 하나 더 큽니다.

다음은 WBLT(Weight Biased Leftist Tree)의 예입니다. -

이진 트리가 다음과 같다고 가정 -

데이터 구조의 가중치 편향 좌파 트리

각 노드에 대해 w(x) 값을 계산하면 다음과 같습니다. -

데이터 구조의 가중치 편향 좌파 트리

이제 WBLT의 정의는 다음과 같습니다. -

이진 트리는 모든 내부 노드에서 왼쪽 자식의 w(x)가 오른쪽 자식의 w(x)보다 크거나 같은 경우에만 Weight Balanced Leftist Tree라고 합니다. 최대(최소) WBLT는 WBLT이기도 한 최대(최소) 트리입니다.