Skip to main content

09. Упорядоченное множество |

Важно

Этот блок в разработке, выполнять его не нужно

Упорядоченное множество строится на основе красно-чёрных деревьев. Дерево - это связный граф, в котором нет циклов.

mdl

Упорядоченное множество на красно-чёрном дереве при каждом добавлении нового элемента ищет, куда лучше всего его добавить так, чтобы поиск и вставка работали как можно быстрее.

Решение заключается в том, что первый элемент мы помещаем в корне дерева (на рисунке первым элементом было добавлено число 1313)

Все остальные мы помещаем либо в левой части дерева, либо в правой.

Слева хранятся все числа, меньшие корня, а справа - все большие. Причём такой подход применим и к подчинённым вершинам.

После того, как были сохранены числа 17 (справа, потому что больше корня) и 8 (слева, потому что меньше корня), новые элементы необходимо было сверять не только с корнем, но и с корнем правого или левого поддерева.

Например, число 25 помещается справа от 1717, а 1515 - слева. Таким образом сохраняются все значения.

Для наиболее оптимальной работы дерево необходимо перебалансировать. Т.е. находить вершину, которую можно сделать главным корнем так, что всё дерево будет иметь минимальное число уровней. Чем их больше, тем дороже операции над таким деревом.

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

Для этого достаточно просто идти от корня и искать момент, когда значение станет больше или меньше заданного (в зависимости от задачи), после чего останется только построить новое дерево на основе поддерева графа, которое мы нашли.

В рамках данного курса писать её будет не нужно. Строго говоря, окрашивать вершины мы тоже не будем. Поэтому дерево, на котором мы построим упорядоченное множество будет просто бинарным. В самой java используются красно-чёрные деревья.

Подробнее можно прочитать здесь и здесь

Задание​

TreeNode​

Чтобы построить бинарное дерево, необходимо написать класс элемента дерева TreeNode с полями:

  1. TreeNode left
  2. TreeNode right
  3. int value

Также необходимо написать конструкторы по аналогии с элементом очереди

MyTreeSet​

Трудоёмкость

Это задание рассчитано на два урока, за него будет выставлено две оценки

Требуется написать класс упорядоченного множества MyTreeSet целых чисел на бинарном дереве, элементы которого представлены объектами класса TreeNode

  1. Конструктор по умолчанию
  2. boolean add(int v) - добавляет элемент в множество, возвращает true, если такого элемента ещё не было
  3. int size() - возвращает размер множества
  4. void clear() - очистить множество
  5. int first() - возвращает первый (наименьший) элемент в данный момент в этом наборе.
  6. int last() - возвращает наибольший элемент в этом наборе
  7. boolean isEmpty() - возвращает true, если множество пустое и false - если нет
  8. int floor(E e) - возвращает наибольший элемент в этом наборе, меньший или равный заданному элементу, или Integer.MAX_VALUE, если такого элемента нет.
  9. int higher(int v) - возвращает наименьший элемент в этом наборе, строго больший, чем заданный элемент, или Integer.MIN_VALUE, если такого элемента нет.
  10. int pollFirst() - возвращает и удаляет первый (наименьший элемент)
  11. int pollLast() - возвращает и удаляет последний (наибольший элемент)
  12. MyTreeSet subSet(E fromElement, E toElement) - подмножество, элементы которого находятся в диапазоне от fromElement включительно, до toElement исключительно.

Все поля и методы должны иметь модификатор public