java - Java多相二分探索木

Question

ダウンキャストやクラス チェックを使用せずに (EmptyTree と NonEmptyTree を使用する) ポリモーフィックな二分探索木を実装するにはどうすればよいですか?

Answer 1

次のような共通インターフェイスを作成します。

interface TreeNode<K, V> {
   TreeNode<K, V> find(K key)
}

次に、共通インターフェースを実装するクラスを提供します。

class EmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K key) {
      // ...
   }
}

class NonEmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K searchKey) {
      // ...
   }
}

EmptyTree の実装は、(null を返すか、例外をスローするかによって) アイテムの検索に失敗したことを常に示しますが、NonEmptyTree の実装は、(指定された検索キーが一致する場合) それ自体を返すか、左にデリゲートするか、または右のサブツリー。左または右のサブツリーが常に存在するため (NonEmptyTree または EmptyTree のいずれかになります)、「NonEmptyTree」クラスは、共通インターフェイスを介してその子を単純に参照し、ランタイム タイプが正しいことを行うという事実に依存できます。 (したがって、アルゴリズムの実装で子のキャストまたは型チェックを行う必要はありません)。

実行時の型を知る必要がある唯一の場所は、子を構築するときです。