Java полиморфное дерево двоичного поиска

Question

Как я могу реализовать полиморфное дерево двоичного поиска (которое использует EmptyTree и NonEmptyTree) без использования downcasting или проверки классов?

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 всегда будет указывать на ошибку при поиске элемента (либо путем возврата нуля, либо с помощью исключения), в то время как ваша реализация NonEmptyTree будет либо возвращать себя (если предоставленный ключ поиска соответствует), либо делегировать левые или правые поддеревья. Поскольку левое или правое поддерево всегда будет существовать (это будет либо NonEmptyTree, либо EmptyTree), класс «NonEmptyTree» может просто ссылаться на своих потомков через общий интерфейс и полагаться на тот факт, что тип среды выполнения будет работать правильно (Таким образом, при реализации алгоритма нет необходимости выполнять какое-либо приведение или проверку типов дочерних элементов).

Единственное место, где вам нужно знать тип среды выполнения, - это когда вы создаете дочерние элементы.