3-арное дерево java

          4
         / \
        3  6
       /  /  \
      2  5   7
                \
                 8

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
 
public class MainClass {
    public static void main(String[] args) {
        ThreeTree tree = new ThreeTree(0, 10);
        Integer[] array = {-3, -2, -1, 0, 1, 2, 3, 4, 5, 6};
 
        //добавляем массив Integer в дерево и выводим в консоль
        System.out.println("Add array:");
        tree.addAll(array);
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //меняем диапазон хранения и выводим
        System.out.println("Edit Range -5, 9:");
        tree.setRange(-5, 9);
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //добавляем по новой тотже массив Integer в дерево, только уже диапазон другой и выводим в консоль
        System.out.println("Add array again:");
        tree.addAll(array);
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //Проверяем наличие элементов в дереве
        System.out.println("Check is element to tree or is not:");
        System.out.printf("Tree have %d: %s;\n", 9, tree.contains(9));
        System.out.printf("Tree have %d: %s;\n", 1, tree.contains(1));
        System.out.printf("Tree have %d: %s;\n", null, tree.contains(null));
        System.out.printf("Tree have %d: %s;\n", 7, tree.contains(7));
        System.out.printf("Tree have %d: %s;\n", 3, tree.contains(3));
        System.out.println();
 
        //Добавляем элементы по одному и выводим на консоль для проверки
        System.out.println("Add elements:");
        tree.add(9);
        tree.add(7);
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //Проверяем удаление элементов и выводим дерево в консоль
        System.out.println("Delete elements:");
        tree.remove(1);
        tree.remove(-1);
        tree.remove(4);
        tree.remove(null);
        tree.remove(10);
        tree.remove(8);
        tree.remove(0);
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //Проверяем удаление всех элементов из дерева, которые есть в массиве
        System.out.println("Delete elements by array:");
        tree.removeAll(new Integer[]{-3, 5, 7, 2, -2, 8});
        System.out.printf("Tree info:\n   size = %d;\n   toString: %s;\n\n", tree.size(), tree.toString());
 
        //Проверяем работоспособность фореч для дерева.
        System.out.println("Foreach:");
        for (Integer value : tree) {
            System.out.println("Element tree: " + value);
        }
 
        //Проверяем работоспособность итератора дерева.
        System.out.println("\nIterator:");
        Iterator<Integer> iterator = tree.iterator();
        while (iterator.hasNext()) {
            System.out.println("Element tree: " + iterator.next());
        }
    }
}
 
/**
 * Интерфейс Tree. Содержит наборы методов для работы с Триарным деревом.
 * дерево хранит объекты типа Integer.
 * Tree не может иметь дубликатов.
 */
interface Tree {
    /**
     * Метод проверяет дерево на пустоту заполнения.
     * Если коллекция пуста, то возвращается true;
     * Если есть ходь 1 элемент - false;
     *
     * @return true или false;
     */
    boolean isEmpty();
 
    /**
     * Метод возвращает кол-во элементов в дереве.
     *
     * @return кол-во элементов;
     */
    int size();
 
    /**
     * Метод очищает всё дерево от элементов.
     */
    void clear();
 
    /**
     * Метод проверяет, имеется ли value в дереве.
     * Если имеется, то возвращает true;
     * Если нет - false;
     *
     * @param value - значение для проверки;
     * @return true или false;
     */
    boolean contains(Integer value);
 
    /**
     * Метод проверяет, содержаться ли все элементы array в дереве.
     * Если хоть 1 элемент из массива array не содержится, возвращает false;
     * Если содержаться все элементы - true;
     *
     * @param array - массив для проверки;
     * @return true или false;
     */
    boolean containsAll(Integer[] array);
 
    /**
     * Метод возвращает дерево в виде массива Object.
     *
     * @return массив типа Integer;
     */
    Integer[] toArray();
 
    /**
     * Метод добавляет в дерево новый элемент.
     *
     * @param value - значение для добавления;
     * @return - true - если удачно добавили или false;
     */
    boolean add(Integer value);
 
    /**
     * Метод добавляет массив array в дерево.
     *
     * @param array - массив для добавление в дерево;
     * @return true - если хоть 1 элемент добавлен или false;
     */
    boolean addAll(Integer[] array);
 
    /**
     * Метод удаляет значение value из дерева.
     *
     * @param value - значение для удаления;
     * @return true - если найдено значение и удалено или false;
     */
    boolean remove(Integer value);
 
    /**
     * Метод удаляет все значения из массива array в дереве.
     *
     * @param array - массив для удаления;
     * @return true - если хоть 1 элемент найден и удалён или false;
     */
    boolean removeAll(Integer[] array);
}
 
/**
 * Класс ThreeTree - триарное дерево.
 */
class ThreeTree implements Tree, Iterable<Integer> {
    /**
     * Голова нашего дерева.
     */
    private Node root;
 
    /**
     * Разрешённый минимальный диапазон для хранения в дереве.
     */
    private int minRange;
 
    /**
     * Разрешённый максимальный диапазон для хранения в дереве.
     */
    private int maxRange;
 
    /**
     * Кол-во элеменов в дереве.
     */
    private int size;
 
    /**
     * Конструктор, принимающий на вход диапазон хранения эелентов от и до
     *
     * @param minRange - начальный диапазон включительно;
     * @param maxRange - конечный диапазон включительно;
     */
    public ThreeTree(int minRange, int maxRange) {
        this.minRange = minRange;
        this.maxRange = maxRange;
    }
 
    /**
     * Конструктор, принимающий на вход диапазон хранения эелентов от и до и массив элементов для добавления в дерево.
     *
     * @param array    - массив для добавление в дерево;
     * @param minRange - начальный диапазон включительно;
     * @param maxRange - конечный диапазон включительно;
     */
    public ThreeTree(Integer[] array, int minRange, int maxRange) {
        this(minRange, maxRange);
        addAll(array);
    }
 
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
 
    @Override
    public int size() {
        return this.size;
    }
 
    @Override
    public void clear() {
        this.root = null;
        this.size = 0;
    }
 
    @Override
    public boolean contains(Integer value) {
        boolean result;
        if (result = checkRange(value)) {
            Node element = getPlaceToWrite(value);
            result = element != null && value.equals(element.value);
        }
        return result;
    }
 
    @Override
    public boolean containsAll(Integer[] array) {
        boolean result;
        if (result = array != null) {
            for (Integer value : array) {
                if (!(result = contains(value))) {
                    break;
                }
            }
        }
        return result;
    }
 
    @Override
    public Integer[] toArray() {
        return getListElements(this.root, new ArrayList<>()).toArray(new Integer[0]);
    }
 
    /**
     * Метод возвращает число, в зависимости от сравнения 2-х элементов.
     * -1 - если хоть один из элементов равен null или если элемент для добавления не входит в диапазон разрешённого;
     * 0  - если 2 элемента равны между друг другом;
     * 1  - если следует записать в левую ветвь дерева;
     * 2  - если следует записать в центральную ветвь;
     * 3  - если следует записать в правую ветвь ;
     *
     * @param nowValue - элемент в голове дерева;
     * @param addValue - элемент, который хотим добавить;
     * @param minRange - минимальный разрешённый диапазон включительно;
     * @param maxRange - максимальный разрешённый диапазон включительно;
     * @return число от -1 до 3;
     */
    private int compareTree(Integer nowValue, Integer addValue, int minRange, int maxRange) {
        int result;
        if (nowValue == null || addValue == null || (addValue < minRange && addValue > maxRange)) {
            result = -1;
        } else if (nowValue.equals(addValue)) {
            result = 0;
        } else {
            int step = Math.abs(maxRange - minRange) / 3;
            if (addValue >= minRange && addValue <= minRange + step) {
                result = 1;
            } else if (addValue > minRange + step && addValue <= minRange + step * 2) {
                result = 2;
            } else {
                result = 3;
            }
        }
        return result;
    }
 
    /**
     * Метод проверяет, подходит ли значение требуемому диапазону.
     *
     * @param value - значение для проверки;
     * @return true - если значение не null и подходит диапазону или false;
     */
    private boolean checkRange(Integer value) {
        return value != null && value >= this.minRange && value <= this.maxRange;
    }
 
    /**
     * Получаем ветвь в дереве, куда следует записать элемент.
     *
     * @param value - значение для записи
     * @return null - если значение равно null или такой элемент уже есть в дереве или
     * элемент не подходит диапазону или возвращаем ссылку на место записи.
     */
    private Node getPlaceToWrite(Integer value) {
        Node place = null;
        if (value != null && checkRange(value)) {
            if (this.root == null) {
                this.root = new Node(null);
            }
            place = this.root;
            int min = this.minRange;
            int max = this.maxRange;
            while (place != null && place.value != null) {
                int intRes = compareTree(place.value, value, min, max);
                if (intRes > 0) {
                    int step = Math.abs(max - min) / 3;
                    if (intRes == 1) {
                        place = place.left = place.left == null ? new Node(null) : place.left;
                    } else if (intRes == 2) {
                        place = place.middle = place.middle == null ? new Node(null) : place.middle;
                    } else {
                        place = place.right = place.right == null ? new Node(null) : place.right;
                    }
                    min = min + step * (intRes - 1);
                    max = intRes == 3 ? maxRange : min + step * intRes;
                } else if (intRes == 0){
                    break;
                } else {
                    place = null;
                }
            }
        }
        return place;
    }
 
    @Override
    public boolean add(Integer value) {
        boolean result;
        Node place = getPlaceToWrite(value);
        if (result = place != null && !value.equals(place.value)) {
            place.value = value;
            this.size++;
        }
        return result;
    }
 
    @Override
    public boolean addAll(Integer[] array) {
        boolean result;
        if (result = array != null) {
            for (Integer value : array) {
                if (add(value)) {
                    result = true;
                }
            }
        }
        return result;
    }
 
    /**
     * Получаем значения от головы root из дерева в коллекцию ArrayList.
     *
     * @param root - откуда начинаем возврат элементов;
     * @param list - коллекция ArrayList, куда будем записывать элементы;
     * @return колеекцию с нужными значениями;
     */
    private List<Integer> getListElements(Node root, List<Integer> list) {
        if (root != null) {
            list.add(root.value);
            list = getListElements(root.left, list);
            list = getListElements(root.middle, list);
            list = getListElements(root.right, list);
        }
        return list;
    }
 
    /**
     * Получаем предыдущий элемент дерева, до элемента со значением value.
     *
     * @param value - значение для поиска;
     * @return - предыдущий элемент или null - если не найден такой элемент или дерево пусто или value = null;
     */
    private Node getPrevElement(Integer value) {
        Node result = null;
        if (value != null && checkRange(value) && !isEmpty()) {
            Node temp = this.root;
            Node prev = null;
            int min = this.minRange;
            int max = this.maxRange;
            while (temp != null && temp.value != null) {
                int compare = compareTree(temp.value, value, min, max);
                if (compare == 0) {
                    result = prev;
                    break;
                } else if (compare == -1) {
                    result = null;
                    break;
                } else {
                    int step = Math.abs(max - min) / 3;
                    prev = temp;
                    if (compare == 1) {
                        temp = temp.left;
                    } else if (compare == 2) {
                        temp = temp.middle;
                    } else {
                        temp = temp.right;
                    }
                    min = min + step * (compare - 1);
                    max = compare == 3 ? maxRange : min + step * compare;
                }
            }
        }
        return result;
    }
 
    @Override
    public boolean remove(Integer value) {
        boolean result = false;
        if (value != null) {
            Node prev = getPrevElement(value);
            List<Integer> list = null;
            if (prev == null) {
                if (this.root != null && value.equals(this.root.value)) {
                    list = getListElements(this.root, new ArrayList<>());
                    this.root = null;
                }
            } else {
                list = getListElements(prev, new ArrayList<>());
                list.remove(prev.value);
                prev.left = null;
                prev.right = null;
                prev.middle = null;
            }
            if (result = list != null) {
                this.size -= list.size();
                list.remove(value);
                addAll(list.toArray(new Integer[0]));
            }
        }
        return result;
    }
 
    @Override
    public boolean removeAll(Integer[] array) {
        boolean result = false;
        if (result = array != null) {
            for (Integer value : array) {
                if (remove(value)) {
                    result = true;
                }
            }
        }
        return result;
    }
 
    @Override
    public String toString() {
        return getListElements(this.root, new ArrayList<>()).toString();
    }
 
    @Override
    public Iterator<Integer> iterator() {
        return getListElements(this.root, new ArrayList<>()).iterator();
    }
 
    /**
     * Метод устанавливает новый диапазон и перезаписывает все данные.
     *
     * @param minRange - минимальное разрешённое значение включительно;
     * @param maxRange - максимальное разрешённое значение включительно;
     */
    public void setRange(int minRange, int maxRange) {
        if (minRange != this.minRange || maxRange != this.maxRange) {
            this.minRange = minRange;
            this.maxRange = maxRange;
            Integer[] array = toArray();
            clear();
            addAll(array);
        }
    }
 
    /**
     * Класс Node - вид хранения данных в дереве.
     */
    private class Node {
        /**
         * Ссылка на левую ветвь дерева.
         */
        Node left;
 
        /**
         * Ссылка на центральную ветвь дерева.
         */
        Node middle;
 
        /**
         * Ссылка на правую ветвь дерева.
         */
        Node right;
 
        /**
         * Значение, которое храним в дереве.
         */
        Integer value;
 
        /**
         * Конструктор с параметром "значение".
         *
         * @param value - значение;
         */
        public Node(Integer value) {
            this.value = value;
        }
    }
}

 private class Node {
        /**
         * Ссылка на левую ветвь дерева.
         */
        Node left;
 
        /**
         * Ссылка на центральную ветвь дерева.
         */
        Node middle;
 
        /**
         * Ссылка на правую ветвь дерева.
         */
        Node right;
 
        /**
         * Значение, которое храним в дереве.
         */
        Integer value;
 
        /**
         * Конструктор с параметром "значение".
         *
         * @param value - значение;
         */
        public Node(Integer value) {
            this.value = value;
        }
    }