이진 트리 속성 - 균형 조정

Question

이진 트리 속성을 이해하려고합니다. 그러나 나는 한가지 확실하지 않습니다.

def. 각 노드는 왼쪽 서브 트리의 내부 노드의 수와 오른쪽 서브 트리의 내부 노드의 수는 최대 1 차이가 있음을 보유하고있는 경우 이진 트리 균형

1. : 이진 나무의 상태

2. 임의의 두 잎이 diff 인 경우 이진 트리 균형이 조정됩니다. 의 깊이는 대부분 1입니다.

나는이 두 가지를 묻습니다. 나는 동등하다, 나는 Def를 의미한다. 1 정의 Def. 2와 viceversa? ... 그것은 나를위한 것 같습니다 ...하지만 누가 정확하게이 속성의 (비) 동등한 예를 나와 설명 할 수 있습니까?

감사합니다, 패트릭

Answer 1

아니, 두 사람은 해당되지 않습니다.

3 
/\ 
    2 7 
//\ 
1 5 8 
/\ \ 
    4 6 9 

그러나, 1

재산권 (1) 부동산 (2)를 의미 속성 (2)를 만족 트리가 아닌 속성입니다.

제안 :n 내부 노드 부동산 1 항에있어서 균형 이진 트리에서 모든 잎의 깊이에있다

• k
• k 또는 k+12^k <= n < 2^(k+1)-1 경우, 및 n = 2^k - 1 경우 깊이가 k+1 인 나뭇잎이 있습니다.

증명 :n = 1 = 2^1-1 들어

(내부 노드의 수에 의해 유도), 깊이 1 하나 또는 두 잎 (루트 깊이가 0이다)이있다.

n = 2를 들어, 하나 개의 하위 트리가 하나 개의 내부 노드를 가지고, 그 하위 트리에있는 모든 잎이 깊이 2에있는 다른 하위 트리가 비어 있거나 깊이에서 나뭇잎 1.

n >= 2을하자 균형 이진 트리를 고려 내부 노드가 n+1 인 특성 1에 따라.

n = 2*m이면 두 하위 트리 모두 내부 노드가 m이어야하며 깊이 속성은 유도 가설에 따라 유지됩니다.

n = 2*m+1이 홀수 인 경우 하나의 하위 트리에 m 개의 내부 노드가 있고 다른 하나의 노드에는 m+1이 있습니다.

1. 2^k <= m < 2^(k+1)-1 경우, m 내부 노드와 하위 트리 깊이 k+1에서 잎이, 그리고 아마도 유도 가설에 의해 깊이 k 출발합니다. m+1 내부 노드가있는 트리의 깊이는 k+1이고 가능한 경우 (m+1 < 2^(k+1)-1 인 경우) 깊이는 k입니다.

2. m = 2^k - 1 경우, m 내부 노드와 하위 트리 만 깊이 k에서 잎을 가지고 있으며, m+1 내부 노드와 하위 트리 깊이 k+1에서 가능성이 깊이 k에서 잎이있다.