SHARE
TWEET

Untitled

a guest Nov 13th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package lesson3;
  2.  
  3. import kotlin.NotImplementedError;
  4. import org.jetbrains.annotations.NotNull;
  5. import org.jetbrains.annotations.Nullable;
  6.  
  7. import java.util.*;
  8.  
  9. // Attention: comparable supported but comparator is not
  10. public class BinaryTree<T extends Comparable<T>> extends AbstractSet<T> implements CheckableSortedSet<T> {
  11.  
  12.     private static class Node<T> {
  13.         final T value;
  14.  
  15.         Node<T> left = null;
  16.  
  17.         Node<T> right = null;
  18.  
  19.         Node(T value) {
  20.             this.value = value;
  21.         }
  22.     }
  23.  
  24.     private Node<T> root = null;
  25.  
  26.     private int size = 0;
  27.  
  28.     @Override
  29.     public boolean add(T t) {
  30.         Node<T> closest = find(t);
  31.         int comparison = closest == null ? -1 : t.compareTo(closest.value);
  32.         if (comparison == 0) {
  33.             return false;
  34.         }
  35.         Node<T> newNode = new Node<>(t);
  36.         if (closest == null) {
  37.             root = newNode;
  38.         }
  39.         else if (comparison < 0) {
  40.             assert closest.left == null;
  41.             closest.left = newNode;
  42.         }
  43.         else {
  44.             assert closest.right == null;
  45.             closest.right = newNode;
  46.         }
  47.         size++;
  48.         return true;
  49.     }
  50.  
  51.     public boolean checkInvariant() {
  52.         return root == null || checkInvariant(root);
  53.     }
  54.  
  55.     public int height() {
  56.         return height(root);
  57.     }
  58.  
  59.     private boolean checkInvariant(Node<T> node) {
  60.         Node<T> left = node.left;
  61.         if (left != null && (left.value.compareTo(node.value) >= 0 || !checkInvariant(left))) return false;
  62.         Node<T> right = node.right;
  63.         return right == null || right.value.compareTo(node.value) > 0 && checkInvariant(right);
  64.     }
  65.  
  66.     private int height(Node<T> node) {
  67.         if (node == null) return 0;
  68.         return 1 + Math.max(height(node.left), height(node.right));
  69.     }
  70.  
  71.     /**
  72.      * Удаление элемента в дереве
  73.      * Средняя
  74.      */
  75.     @Override
  76.     public boolean remove(Object o) {
  77.         if (find((T) o) == null) return false;  //  Делаем проверку на вхождение элемента в дерево
  78.         root = remove(root, new Node<>((T) o));
  79.         size--;  //  Уменьшаем количество элементов при успешном удалении
  80.         return true;
  81.     }  //  Вывод: Т=O(h), R=O(1), где h - высота бинарного дерева
  82.  
  83.     /**
  84.      * Вспомогательная функция
  85.      * Удаление элемента в поддереве
  86.      * Реализовано рекурсией
  87.      *
  88.      * Рассматривается 3 случая:
  89.      * 1) Удаляемый элемент находится в левом поддереве текущего поддерева
  90.      * 2) Удаляемый элемент находится в правом поддереве текущего поддерева
  91.      * 3) Удаляемый элемент является корнем поддерева
  92.      *
  93.      * В двух первых случаях рекурсивно удаляется элемент из нужного поддерева.
  94.      * Если удаляемый элемент является корнем текущего поддерева и имеет два узла,
  95.      * то нужно заменить его минимальным элементом из правого поддерева и рекурсивно
  96.      * удалить этот минимальный элемент из правого поддерева.
  97.      * Если удаляемый элемент имеет один узел, то он им и заменяется.
  98.      */
  99.     private Node<T> remove(Node<T> start, Node<T> removable) {
  100.         if (start == null) return null;
  101.         if (removable.value.compareTo(start.value) < 0) start.left = remove(start.left, removable);  //  Удаление слева
  102.         else if (removable.value.compareTo(start.value) > 0) start.right = remove(start.right, removable);  //  Удаление справа
  103.         else if (start.left != null && start.right != null) {  //  Удаление элемента при двух узлах с непустыми значениями
  104.             Node<T> node;  //  Используется переменная узла, так как value является final
  105.             node = new Node<>(minimum(start.right));  //  Поиск минимального элемента в правом поддереве (вспом. функ.)
  106.             node.left = start.left;
  107.             node.right = start.right;
  108.             start = node;
  109.             start.right = remove(start.right, start);
  110.         } else {
  111.             if (start.left != null) start = start.left;
  112.             else start = start.right;
  113.         }
  114.         return start;
  115.     }
  116.  
  117.     @Override
  118.     public boolean contains(Object o) {
  119.         @SuppressWarnings("unchecked")
  120.         T t = (T) o;
  121.         Node<T> closest = find(t);
  122.         return closest != null && t.compareTo(closest.value) == 0;
  123.     }
  124.  
  125.     private Node<T> find(T value) {
  126.         if (root == null) return null;
  127.         return find(root, value);
  128.     }
  129.  
  130.     private Node<T> find(Node<T> start, T value) {
  131.         int comparison = value.compareTo(start.value);
  132.         if (comparison == 0) {
  133.             return start;
  134.         }
  135.         else if (comparison < 0) {
  136.             if (start.left == null) return start;
  137.             return find(start.left, value);
  138.         }
  139.         else {
  140.             if (start.right == null) return start;
  141.             return find(start.right, value);
  142.         }
  143.     }
  144.  
  145.     public class BinaryTreeIterator implements Iterator<T> {
  146.  
  147.         private Node<T> node = null;  //  Текущий элемент в итераторе
  148.         private Stack<Node<T>> iterator = new Stack<>();
  149.  
  150.         private BinaryTreeIterator() {
  151.             if (root == null) return;
  152.             node = root;
  153.             while (true) {
  154.                 if (node.left != null) {
  155.                     iterator.push(node);
  156.                     node = node.left;
  157.                 }
  158.             }
  159.         }
  160.  
  161.         /**
  162.          * Вспомогательная функция
  163.          * Заполнение итератора для бинарного дерева в порядке увеличения значения
  164.          * Реализовано рекурсией
  165.          *
  166.          * Алгоритм:
  167.          * Ищем минимальное значение начиная с корня бинарного дерева рекурсией,
  168.          * то есть проверяем на null каждый левый элемент. Как только самый малый элемент найден,
  169.          * добавляем его в конец очереди. Далее начинается заполнение всеми последующими элементами.
  170.          * Проверяем правый элемент на null, так как мы находимся в самой левой ячейке левого поддерева,
  171.          * то цикл завершается и возвращается в предыдущий вызов, добавляется элемент в очередь
  172.          * и совершается проверка опять же на null справа, если справа есть элемент, то выполняется метод,
  173.          * добавляется элемент в очередь, в зависимости от правого элемента либо вызывается метод снова,
  174.          * либо возвращается в прошлый, и, таким образом, обходится всё дерево.
  175.          */
  176.         private void createIterator(Node<T> current) {
  177.             if (current.left != null) createIterator(current.left);
  178.             iterator.offer(current);
  179.             if (current.right != null) createIterator(current.right);
  180.         }  //  Вывод: Т=O(e), R=O(e), где e - количество элементов в дереве
  181.  
  182.         /**
  183.          * Проверка наличия следующего элемента
  184.          * Средняя
  185.          */
  186.         @Override
  187.         public boolean hasNext() {
  188.             return iterator.peek() != null;
  189.         }  //  Вывод: Т=O(e), R=O(1), где e - количество элементов в дереве
  190.  
  191.         /**
  192.          * Поиск следующего элемента
  193.          * Средняя
  194.          */
  195.         @Override
  196.         public T next() {
  197.             node = iterator.poll();
  198.             if (node == null) throw new NoSuchElementException();
  199.             return node.value;
  200.         }  //  Вывод: Т=O(e), R=O(1), где e - количество элементов в дереве
  201.  
  202.         /**
  203.          * Удаление следующего элемента
  204.          * Сложная
  205.          */
  206.         @Override
  207.         public void remove() {
  208.             BinaryTree.this.remove(node.value);
  209.         }  //  Вывод: Т=O(h), R=O(1), где h - высота бинарного дерева
  210.     }
  211.  
  212.     @NotNull
  213.     @Override
  214.     public Iterator<T> iterator() {
  215.         return new BinaryTreeIterator();
  216.     }
  217.  
  218.     @Override
  219.     public int size() {
  220.         return size;
  221.     }
  222.  
  223.     @Nullable
  224.     @Override
  225.     public Comparator<? super T> comparator() {
  226.         return null;
  227.     }
  228.  
  229.     /**
  230.      * Для этой задачи нет тестов (есть только заготовка subSetTest), но её тоже можно решить и их написать
  231.      * Очень сложная
  232.      */
  233.     @NotNull
  234.     @Override
  235.     public SortedSet<T> subSet(T fromElement, T toElement) {
  236.         return new SubBinaryTree(this, fromElement, toElement);
  237.     }  //  Вывод: Т=O(e), R=O(1), где e - количество элементов в дереве
  238.  
  239.     /**
  240.      * Найти множество всех элементов меньше заданного
  241.      * Сложная
  242.      */
  243.     @NotNull
  244.     @Override
  245.     public SortedSet<T> headSet(T toElement) {
  246.         return new SubBinaryTree(this, null, toElement);
  247.     }  //  Вывод: Т=O(e), R=O(1), где e - количество элементов в дереве
  248.  
  249.     /**
  250.      * Найти множество всех элементов больше или равных заданного
  251.      * Сложная
  252.      */
  253.     @NotNull
  254.     @Override
  255.     public SortedSet<T> tailSet(T fromElement) {
  256.         return new SubBinaryTree(this, fromElement, null);
  257.     }  //  Вывод: Т=O(e), R=O(1), где e - количество элементов в дереве
  258.  
  259.     @Override
  260.     public T first() {
  261.         if (root == null) throw new NoSuchElementException();
  262.         Node<T> current = root;
  263.         while (current.left != null) {
  264.             current = current.left;
  265.         }
  266.         return current.value;
  267.     }
  268.  
  269.     @Override
  270.     public T last() {
  271.         if (root == null) throw new NoSuchElementException();
  272.         Node<T> current = root;
  273.         while (current.right != null) {
  274.             current = current.right;
  275.         }
  276.         return current.value;
  277.     }
  278.  
  279.     /**
  280.      * Вспомогательная функция
  281.      * Нахождение минимального элемента в поддереве
  282.      */
  283.     public T minimum(Node<T> node) {
  284.         if (node == null) throw new NoSuchElementException();
  285.         Node<T> current = node;
  286.         while (current.left != null) {
  287.             current = current.left;
  288.         }
  289.         return current.value;
  290.     }
  291.  
  292.     /**
  293.      * Вспомогательная функция (нигде не используется)
  294.      * Нахождение максимального элемента в поддереве
  295.      */
  296.     public T maximum(Node<T> node) {
  297.         if (node == null) throw new NoSuchElementException();
  298.         Node<T> current = node;
  299.         while (current.right != null) {
  300.             current = current.right;
  301.         }
  302.         return current.value;
  303.     }
  304.  
  305.     /**
  306.      * Вложенный класс, реализующий поддерево, которое ограничено либо снизу,
  307.      * либо сверху, либо с двух сторон одновременно.
  308.      * Является классом-обёрткой, так как мы работаем с тем же самым бинарным деревом,
  309.      * а не новым его экземпляром.
  310.      *
  311.      * Переменные:
  312.      * binaryTree - бинарное дерево, с которым мы работаем
  313.      * fromElement - нижняя граница, которая ограничивает поддерево (элемент включается в дерево)
  314.      * toElement - верхняя граница, которая ограничивает поддерево (элемент не включается в дерево)
  315.      *
  316.      * Переопределены методы add(), contains() и size() из родительского класса.
  317.      */
  318.     class SubBinaryTree extends BinaryTree<T> {
  319.         private BinaryTree<T> binaryTree;
  320.         private final T fromElement;
  321.         private final T toElement;
  322.         private int size = 0;
  323.  
  324.         SubBinaryTree(BinaryTree<T> binaryTree, T fromElement, T toElement) {
  325.             this.binaryTree = binaryTree;
  326.             this.fromElement = fromElement;
  327.             this.toElement = toElement;
  328.         }
  329.  
  330.         @Override
  331.         public boolean add(T t) {
  332.             if (!inRange(t)) throw new IllegalArgumentException();
  333.             return binaryTree.add(t);
  334.         }
  335.  
  336.         @Override
  337.         public boolean contains(Object o) {
  338.             if (!inRange((T) o)) return false;
  339.             return binaryTree.contains(o);
  340.         }
  341.  
  342.         @Override
  343.         public boolean remove(Object o) {
  344.             if (!inRange((T) o)) return false;
  345.             return binaryTree.remove(o);
  346.         }
  347.  
  348.         @Override
  349.         public int size() {
  350.             int counter = 0;
  351.             for (T value : binaryTree) if (inRange(value)) counter++;
  352.             size = counter;
  353.             return size;
  354.         }
  355.  
  356.         /**
  357.          * Вспомогательная функция
  358.          * Проверка на вхождение в поддерево
  359.          * Реализовано при помощи проверки границ на null
  360.          *
  361.          * Алгоритм:
  362.          * Задаём две переменные comparisonBottom и comparisonTop,
  363.          * которые отвечают за сравнение по нижней границе и по верхней,
  364.          * присваиваем им 0 и -1 соответственно для того,
  365.          * чтобы при false в проверка на null не учитывалась граница поддерева,
  366.          * если нам это требуется (методы headSet() и tailSet()).
  367.          * Далее присваиваем значение сравнения через compareTo между элементом и границей
  368.          * в comparisonBottom и comparisonTop соответственно,
  369.          * если проверка на null равна true.
  370.          */
  371.         private boolean inRange(T t) {
  372.             int comparisonBottom = 0;
  373.             int comparisonTop = -1;
  374.             if (fromElement != null) comparisonBottom = t.compareTo(fromElement);
  375.             if (toElement != null) comparisonTop = t.compareTo(toElement);
  376.             return comparisonBottom >= 0 && comparisonTop < 0;
  377.         }
  378.     }
  379. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top