AVL ツリーのクラスの設計

AVL ツリーは二分探索木であるため、AVLTree は BST のサブクラスとして設計されています。 AVL ツリーはバイナリ ツリーであるため、以下の図に示すように、AVLTree クラスを定義して BST クラスを拡張できます。 BST クラスと TreeNode クラスはセクション

で定義されました。

ツリーのバランスをとるには、各ノードの高さを知る必要があります。便宜上、各ノードの高さを AVLTreeNode に保存し、AVLTreeNode を BST.TreeNode のサブクラスとして定義します。 TreeNode は BST の静的内部クラスとして定義されていることに注意してください。 AVLTreeNode は、AVLTree の静的内部クラスとして定義されます。 TreeNode には、element、left、および right というデータ フィールドが含まれており、これらは AVLTreeNode によって継承されます。したがって、以下の図に示すように、AVLTreeNode には 4 つのデータ フィールドが含まれます。

BST クラスの createNewNode() メソッドは TreeNode オブジェクトを作成します。このメソッドは AVLTree クラスでオーバーライドされ、AVLTreeNode を作成します。 BST クラスの createNewNode() メソッドの戻り値の型は TreeNode ですが、createNewNode() の戻り値の型は同じであることに注意してください。 > AVLTree クラスのメソッドは AVLTreeNode です。 AVLTreeNode は TreeNode のサブクラスであるため、これで問題ありません。

AVLTree での要素の検索は、通常のバイナリ ツリーでの検索と同じであるため、BST クラスで定義されている search メソッドも機能します。 AVLTree の場合。

insert メソッドと delete メソッドは、要素を挿入および削除し、必要に応じて再バランス操作を実行してツリーのバランスを確保するためにオーバーライドされます。

以上がAVL ツリーのクラスの設計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。