Время поиска для дерева двоичного поиска
Вы можете использовать метод iterator () из интерфейса List:
@Override
public Iterator<Card> iterator() {
List<Card> newList = new ArrayList<>(this.cards); // copy to preserve original List order
Collections.reverse(newList);
return newList.iterator();
}
Таким образом, вам не нужно реализовывать интерфейс Iterator.
2 ответа
Для несамоуравновешивающегося дерева (возможный, но необычный для дерева поиска), худший случай является O (n), который является для вырожденного двоичного дерева (связанный список).
В этом случае, необходимо искать, в среднем, половину списка прежде, чем найти желаемый элемент.
Лучший случай является O (журнал 2 n) для отлично сбалансированного дерева, так как Вы сокращаете пространство поиска в половине для каждого древовидного уровня.
Средний случай является где-нибудь промежуточным те два и зависит полностью от данных :-)
, Так как Вы редко добираетесь для управления последовательностью, в которую данные вставляются в дерево, самоуравновешивающиеся деревья обычно предпочтительны с тех пор, в то время как они добавляют небольшое количество времени к каждой вставке или удалению, они значительно ускоряют поиск. Их худший случай настолько лучше, чем несбалансированные деревья.
8
_______/ \_______
/ \
4 12
__/ \__ __/ \__
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
В этом отлично сбалансированное дерево, Вы видите, что добираетесь 2 <глоток> n -1 узел для каждого n уровни. Это означает для 15 узлов, Вы никогда не должны искать больше чем четыре узла для нахождения его (например, для нахождения 13, Вы ищете 8, 12, 14 и 13). Это - то, куда журнал 2 число n прибывает из.
А вырожденное несбалансированное дерево, как уже указано, является связанным списком. Если бы Ваши данные прибыли в последовательность, и Вы вставили его в несбалансированное двоичное дерево, то Вы добрались бы:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+
|
+------------------------------------------+
|
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15
Для нахождения 13 в этом случае необходимо было бы искать 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 и 13, следовательно O (n).
Мог бы хотеть отметить этого как "домашнюю работу". Вот хорошая начальная точка: http://en.wikipedia.org/wiki/Binary_search_tree
В целом, балансировался , дерево двоичного поиска имеет поиск худшего случая O (зарегистрируйте n), лучший случай O (1) (когда требуемое значение является корнем) и средний случай O (регистрируют n) (листы содержат экспоненциально больше значений, чем их родители).
худший случай является самым интересным и легко замечен путем распознавания, что первый уровень двоичного дерева имеет 1 узел, второе имеет 2, третье имеет 4 и так далее. Таким образом количество узлов в двоичном дереве глубины n точно 2^n - 1 . Математическая инверсия показательной функции является логарифмом, таким образом: O (регистрируют n) .
несбалансированное дерево может быть настолько же плохим как связанный список и может иметь форму как следующее:
1
/ \
2
/ \
3
/ \
4
/ \
В этой ситуации, время выборки для наихудшего случая O (n) .