밸런스 이진 트리 코딩

Question

안녕 얘들 아 나는 방금 이진 트리를 배웠고 내 질문에 최근에 질문을 받았다. 내 믿을 수 없을 정도로 나쁜 구현과 질문에 대한 이해 부족으로 인해이 문제를 해결할 방법을 모를뿐입니다. 제발 도와주세요 !!!

n 노드를 가진 이진 트리 T는 어떤 노드에 대해서도 T에서 두 개의 하위 트리의 높이 차이가 h> = 0 인 경우 인 경우 h-balance라고합니다. 정수. 빈 나무의 높이가 -1이라고 가정합니다. 각 노드 u에 세 개의 필드가 있다고 가정합니다. u.lc는 왼쪽의 자식을 가리키고 u.lc = NULL은 왼쪽이없는 경우 NULL 자식입니다. u.rc가 u의 오른쪽 자식을 가리키고 u.rc가 NULL 일 경우 NULL입니다. u.height는 u에 뿌리를 둔 나무의 높이로 설정해야합니다.

(a) 트리의 루트를 가리키는 r이 주어지면 u : height에 각 노드 u의 높이를 채우는 알고리즘 (또는 C/C++)의 의사 코드로 알고리즘을 설계하십시오.

(b) 각 노드 u의 높이가 u.height에 저장되었다고 가정하면 알고리즘이 에 쓰여져 T가 균형을 이루는지 확인합니다. (힌트 : (a)에서 고안된 알고리즘 수정)

Answer 1

이것은 의사 코드는 아니지만 약간의 도움이 될 것입니다.

a)는 잎의 높이가

• -1 내부 노드의 높이가 하나의 큰
• : 당신이 더 많은 공식적으로 그 조건을 명시하는 경우

  그것은 종종 문제가 명확하게 두 하위 트리의 높이의 최대 값보다 큽니다.

b)

• 잎은 H-균형
• 내부 노드는 H가 분산되어있는 경우 두 서브 트리가 H-균형 및 그 높이의 차이는 가장 인 경우에만 h.

두 가지 문제는 같은 패턴으로 나타납니다. 하나의 리프 케이스와 두 개의 하위 트리에 의존하는 케이스입니다.

void recurse(t) 
{ 
    if (t is a leaf, i.e. an empty tree) 
    { 
     handle the leaf case 
    } 
    else 
    { 
     do something that depends on 
      recurse(left subtree of t) 
     and 
      recurse(right subtree of t) 
    } 
} 

내가 운동으로 솔루션의 나머지 부분을 떠날거야 :

이 이진 트리에 재귀의 일반적인 형태입니다.

Answer 2

다음은 알고리즘입니다. 이어서

struct Node { 
    Node *l; // left child 
    Node *r; // right child 
    int h; // subtree height 
}; 

void CalcHeights(Node *n) 
{ 
    if(n != NULL) 
    { 
     CalcHeights(n->l); // calc height in subtrees 
     CalcHeights(n->r); 
     int hl = n->l ? n->l->h : -1; // read calculated heights 
     int hr = n->r ? n->r->h : -1; 

     n->h = (hl > hr ? hl : hr) + 1; // get the bigger one plus 1 
    } 
} 

bool TestBalanced(Node const *n, int h) 
{ 
    if(n != NULL) 
    { 
     if(! TestBalanced(n->l, h) || ! TestBalanced(n->r, h)) 
      return false;    // unbalanced subtree... 

     int hl = n->l ? n->l->h : -1; // get subtrees heights 
     int hr = n->r ? n->r->h : -1; 

     return abs(hl - hr) <= h; // test the difference against H 
    } 
    return true; // empty tree is balanced 
} 

다음과 같이 노드 구조 선언 가정