0

だから私は基本的に関数 avl を持っていますか? その実行は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) の実行時間を得ることができます。」というヒントが与えられました。... 一定時間で身長を伸ばす方法がわかりません。私のAVLを作るための提案はありますか？O(n^2) ではなく O(n) で実行しますか?

4

2 に答える 2

1

ツリーに高さを格納することが許可されていない場合は、ツリーの高さとそれが AVL ツリーであるかどうかを通知するワーカー関数を使用することで、再計算を回避できます。次に、各ノードが正確に 1 回調べられ、O(n) アルゴリズムが作成されます。次に、ワーカーの結果の高さ部分を忘れるラッパーからワーカーを呼び出します。もちろん、近道をする必要があります。そのため、一部のサブツリーがバランス条件に違反していると判断された場合は、それ以上のサブツリーをチェックしない#fで、偽の高さを返します。

于 2012-03-08T20:16:18.707 に答える
0

別のオプションは、すべてのノードに高さを格納することです。値は、そのノードをルートとするサブツリーの高さを表します。明らかに、このアプローチでは、サブツリーの高さを返すことは O(1) 操作になります。

つまり、ツリーを変更するすべての操作 (挿入、削除など) は、ツリーに構造上の変更があるたびに高さを最新の状態に保つ必要があります。

于 2012-03-08T20:35:12.580 に答える