Scheme에서 더 효율적인 런타임 - AVL의

Question

그래서 기본적으로 함수가 있습니까? 그 실행은 O (n^2)에 있습니다. 이것은 매회마다 재귀를하기 때문에 O (n) 함수 인 높이를 호출하기 때문입니다 (n은 트리의 노드 수임).

(define (height t) 
    (cond 
    [(empty? t) 0] 
    [else (+ 1 (max (height (BST-left t)) (height (BST-right t))))])) 

(define (avl? t) 
    (cond 
    [(empty? t) #t] 
    [else (and (avl? (BST-left t)) 
       (avl? (BST-right t)) 
       (>= 1 (abs (- (height (BST-left t)) 
          (height (BST-right t))))))])) 

내 문제는 내가 avl을 만들고 싶습니까? O (n) 시간에 실행하십시오. 나는 힌트를 얻었습니다 : "당신이 적용되는 BST의 크기에 관계없이 일정 시간 내에 높이 함수 호출을 제한하려고 노력해야합니다. 이런 식으로 모든 실행 시간에 O (n)을 얻을 수 있습니다." ... 내 높이를 일정한 시간에 어떻게 달릴 지 잘 모르겠습니다. 내 제안을하기위한 제안? O (n^2)가 아닌 O (n)에서 실행됩니까?

Answer 1

트리에 높이를 저장할 수없는 경우 트리의 높이를 알려주는 작업자 함수 (및)가 AVT 트리 인 경우이를 다시 계산하지 않아도됩니다. 그러면 각 노드는 정확히 한 번만보고 O (n) 알고리즘을가집니다. 그런 다음 작업자 결과의 높이 부분을 잊어 버린 래퍼에서 작업자를 호출합니다. 물론 단축키를 사용해야합니다. 따라서 일부 하위 트리가 균형 조건을 위반한다고 판단되면 하위 트리를 더 이상 확인하지 않아도되고 #f 및 가짜 키를 반환하십시오.

Answer 2

또 다른 옵션은 모든 노드에 높이를 저장하는 것입니다. 여기서 값은 해당 노드를 루트로하는 하위 트리의 높이를 나타냅니다. 분명히이 방법을 사용하면 하위 트리의 높이를 반환하는 것이 O (1) 연산이됩니다.

트리를 수정하는 모든 작업 (삽입, 삭제 등)은 트리에 구조적 변경이있을 때마다 높이를 최신 상태로 유지해야 함을 의미합니다.