AVL ツリーの時間複雑さの分析

AVL ツリーの高さは O(log n) であるため、search、insert、および AVLTree の >delete メソッドは O(log n) です。 AVLTree の search、insert、および delete メソッドの時間計算量は、ツリーの高さによって異なります。木の高さは O(log n) であることが証明できます。

G(h) が高さ h の AVL ツリー内のノードの最小数を表すものとします。明らかに、G(1) は 1、G(2) は 2 です。高さ h >= 3 の AVL ツリー内のノードの最小数には、2 つの最小サブツリーが必要です。1 つは高さ h - 1 で、もう 1 つは高さ h です。 - 2. したがって、

G(h) = G(h - 1) + G(h - 2) + 1

インデックス i のフィボナッチ数は漸化関係 F(i) = F(i - 1) + F(i - 2) を使用して記述できることを思い出してください。したがって、関数 G(h) は本質的に F(i) と同じです。それは証明できます

h ここで、n はツリー内のノードの数です。したがって、AVL ツリーの高さは O(log n) です。

search、insert、および delete メソッドには、ツリー内のパスに沿ったノードのみが含まれます。 updateHeight メソッドと balanceFactor メソッドは、パス内の各ノードに対して一定時間で実行されます。 balancePath メソッドは、パス内のノードに対して一定時間で実行されます。したがって、search、insert、および delete メソッドの時間計算量は O(log n) です。

以上がAVL ツリーの時間複雑さの分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。