Java: Должен ли я выступать за генерики при реализации различных древовидных структур?

Я только что пришел this article, которые предлагают различные приемы с дженериками.Java: Должен ли я выступать за генерики при реализации различных древовидных структур?

Автор решил использовать следующее:

public class BinarySearchTree<T extends Comparable<? super T>> {

И я не понимаю. Почему автор решил использовать private Entry<T> root;

, а не только private Comparable root?

Какое конкретное преимущество может привести к созданию универсального узла дерева с помощью реализованного сопоставимого интерфейса? Мне нужно знать больше, чем сравнивать 2 элемента в таких структурах, как двоичное дерево поиска, дерево AVL, дерево Splay, дерево Red-Black и т. Д.?

источник

2010-10-22 Xorty

Вам нужно знать детей и структуру о дереве. Сопоставимый просто дает вам compareTo. Запись по крайней мере дает вам левого и правого ребенка, поэтому после ваших сравнений вы будете знать, как манипулировать структурой, чтобы сохранить дерево согласованным.

источник

2010-10-22 19:09:40

@SB Вы частично ответили на вопрос о Comparable, а как насчет дженериков? См. Мои комментарии к сообщению Kel;) – Xorty

Вам не нужно использовать Generics, но это хороший способ поддерживать безопасность типов и согласованность объектов в дереве. Вы всегда можете использовать стандартный класс Node, который возвращает Object, но если вы хотите, чтобы ваше дерево было многократно использовано для разных объектов, Generics отличные. Есть причина, по которой API коллекций перешел на использование Generics при введении - они добавляют безопасность и помогают разработчикам понять немного больше о том, что они могут и не могут сделать с классом. –

Ну, я не думал об использовании Object в качестве держателя данных для узла :) Я думал об использовании Comparable вместо этого :) Итак, узел имеет: данные (сравнимые), leftson (Node), rightson (Node) – Xorty

Он решил пойти на Entry<Comparable>, потому что Entry является дополнительным классом, представляющим узел в дереве. Скорее всего, запись определена аналогична той

class Entry<T extends Comparable<? super T>> { T value; Entry<T> leftAncestor; Entry<T> rightAncestor; }

И тогда двоичная структура дерева имеет корень дерева и методы, необходимые для использования его.

источник

2010-10-22 19:09:18 vstoyanov

Итак, основная идея - позволить мне вставить Comparable реализацию, но не смешивать яблоки с грушами? (Apple: Comparable, Pear: Comparable) – Xorty

Это основная идея Generics в этом примере. Идея использования 'Entry' вместо' Comparable' заключается в том, что так как структуры данных на основе узлов реализованы, когда у вас есть 'class' /' struct'. – vstoyanov

Насколько я понимаю, в этом примере показаны детали реализации двоичного дерева поиска. Записи деревьев должны быть не только сопоставимыми, но также включать информацию о дочерних объектах с левым правым и (если необходимо) родительском элементе.

источник

2010-10-22 19:10:04 Kel

Хорошо и почему он не расширяет интерфейс Comparable с другим интерфейсом узла? Он также может хранить сына влево/вправо. Можете ли вы придумать какую-либо конкретную причину использования дженериков здесь? – Xorty

Думаю, совместимый интерфейс также подходит здесь. Дженерики используются для хранения произвольных данных. – Kel

Но вы не будете использовать какой-либо из методов общих произвольных данных, если только вы не создадите очень обычную реализацию дерева, не так ли? – Xorty

Java: Должен ли я выступать за генерики при реализации различных древовидных структур?

ответ

Смежные вопросы