배열 가로 방향의 BST

Question

배열에서 다음과 같은 구현을했습니다.

32 
/\ 
2 -5 
    /\ 
    -331 399 

데이터는 한 번에 3 개의 색인으로 그룹화됩니다. index%3==0은 노드의 값이고 index%3==1은 왼쪽 노드 값의 인덱스이고 index%3==2은 오른쪽 노드 값의 인덱스입니다. 왼쪽 또는 오른쪽 인덱스 참조가 0이면 해당 방향의 노드가 없습니다.

이 트리의 깊이 (높이)를 찾으려고합니다. 재귀 적으로 작성했습니다.

height(node): 
    if node == null: 
     return 0 
    else: 
     return max(height(node.L), height(node.R)) + 1 

그러나 비 재귀적인 해결책을 찾고 싶습니다. 여기

내가 가진 일부 의사 인의 트리를 가정하는 것은

int i = 0; int left = 0; int right = 0; 
while (i != n){ 
if (a[i+1] != 0){ 
    left++; 
} 
else if (a[i+2] != 0){ 
    right++; 
} 
i = i + 3; 
} 

return max (left, right) + 1; 

내가이 잘 생각하지 않고 내가 제대로이 작업을 수행하는 방법을 알아내는 도움을 싶습니다 비어 있지 않습니다.

Answer 1

당신이 개선하고 싶은 행동을 우리가 이해할 수 있도록 재귀 문제가 무엇인지 말하지 않았습니다.

많은 솔루션이 있지만 거의 모든 솔루션이 재귀 솔루션보다 성능이 같거나 낮습니다. 실제로 최상의 솔루션은 트리를 만들 때해야 할 일입니다. 예를 들어 각 노드의 높이를 노드 당 네 번째 배열 인덱스에 저장할 수 있습니다. 그런 다음 매 4 번째 색인을 사소한 스캔하여 최대 높이를 찾습니다. 또한 노드에 부모 참조가 저장된 경우 키 확인 중에 계산할 필요가 없기 때문에 노드를 쉽게 만들 수 있습니다.

하나의 솔루션은 스택으로 재귀를 시뮬레이트하는 것이지만 재귀와 다를 바 없습니다.

다른 해결책은 각 노드를 거쳐 부모를 기준으로 키 높이를 결정하는 것이지만 특정 트래버 설 순서는 아닙니다. 그러나 계층 구조를 저장하는 보조 데이터 구조가없는이 구성 방법으로 인해 효율성이 떨어집니다. O (n^2). 문제는 풀 어레이 스캔 없이는 부모로부터 자식으로 이동할 수 없다는 것입니다. 그런 다음 선형 시간으로 수행 할 수 있습니다 (재귀 또한 선형 시간이므로 더 잘 수행되는지는 확실하지 않으며 메모리 관점에서 볼 때 훨씬 좋을 수도 있습니다).

개선하려는 효율성 유형을 정의 할 수 있습니까?

다음은 의사 각,하지만 쉽게없는 몇 가지 데이터 구조체에 따라 해요 :

"재귀 재귀없이"솔루션 :

int get_height(int * tree, int length) { 

    Stack stack; 

    int max_height = 0; 

    if (length == 0) { 
     return 0; 
    } 

    // push an "array" of the node index to process and the height of its parent. 
    // make this a struct and use that for real c code 
    stack.push(0,0); 

    while(!stack.empty()) { 
     int node_index, parent_height = stack.pop(); 

     int height = parent_height + 1; 
     if (height > max_height) { 
      max_height=height; 
     } 
     if (tree[node_index+1] != 0) 
      stack.push(tree[node_index+1], height); 
     if (tree[node_index+2] != 0) 
      stack.push(tree[node_index+2], height); 

    } 

    return max_height; 
} 

이제 작업 추가 메모리를 사용하지 않는 정말로 느린 솔루션에서,하지만 정말 나쁜 것입니다. 피보나치를 재귀 적으로 쓰는 것과 같습니다. 원래의 알고리즘은 각 노드를 통과하여 O (n^2)의 실행 시간에 대해 최악의 경우 O (n) 검사를 수행합니다 (실제로 원래 생각했던 것만 큼 나빴습니다)

편집 : 하위 노드가있는 모든 노드를 건너 뛰는 최적화입니다. 전화가 많이 끊기 때문에 이것은 매우 중요합니다.가장 좋은 경우는 트리가 실제로 링크 된 목록이고,이 경우 O (n) 시간에 실행됩니다. 최악의 경우는 완전히 균형 잡힌 트리입니다 - 로그 노드가 O (log (n)^2)에 대한 루트로 다시 체크하는 로그 리프 노드가 있습니다. 그다지 나쁘지는 않습니다

"정말 느리지 만 별도의 메모리"솔루션 (하지만 지금은 거의 너무 느려하지 업데이트) :

int get_height(int * tree, int length) { 
    int max_height = 0; 
    for (int i = 0; i < length; i+=3) { 

     // Optimization I added later 
     // if the node has children, it can't be the tallest node, so don't 
     // bother checking from here, as the child will be checked 
     if (tree[i+1] != 0 || tree[i+2] != 0) 
      continue; 

     int height = 0; 
     int index_pointing_at_me; 

     // while we haven't gotten back to the head of the tree, keep working up 
     while (index_pointing_at_me != 0) { 
      height += 1; 
      for (int j = 0; j < length; j+=3) { 
       if (tree[j+1] == tree[i] || 
        tree[j+2] == tree[i]) { 
        index_pointing_at_me = j; 
        break; 
       } 
      } 

     } 
     if (height > max_height) { 
      max_height = height; 
     } 

    } 

    return max_height; 
} 

이전 솔루션을 개선하지만, O (n)의 메모리를 사용 -이 부모가 어린이 전에 항상 가정 배열 (기술적으로 필요하지는 않겠지 만)

int get_height(int * tree, int length) { 

    if (length == 0) 
     return 0; 

    // two more nodes per node - one for which node is its parent, the other for its height 
    int * reverse_mapping = malloc((sizeof(int) * length/3) * 2) 
    reverse_mapping[1] = 1; // set height to 1 for first node 



    // make a mapping from each node to the node that points TO it. 
    // for example, for the first node 
    // a[0] = 32 
    // a[1] = 3 
    // a[2] = 6 
    // store that the node at 3 and 6 are both pointed to by node 0 (divide by 3 just saves space since only one value is needed) and that each child node is one taller than its parent 
    int max_height = 0; 
    for (int i = 0; i < length; i+=3) { 

     int current_height = reverse_mapping[(i/3)*2+1]; 
     if (current_height > max_height) 
      max_height = current_height; 

     reverse_mapping[(tree[i+1]/3)*2] = i; 
     reverse_mapping[(tree[i+1]/3)*2 + 1] = current_height + 1; 

     reverse_mapping[(tree[i+2]/3)*2] = i; 
     reverse_mapping[(tree[i+2]/3)*2 + 1] = current_height + 1; 

    } 
    return max_height 
}