AVL ツリーのクラスの設計

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

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

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

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

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