Бинарное дерево, быстрая реализация

в 12:04, , рубрики: java, Алгоритмы

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

Одно из таких заданий — создание класса-коллекции «бинарное дерево». Подробнее можно почитать тут. Более опытный программист при желании напишет лучше, здесь же простая реализация.

Итак, было решено использовать такую схему:

class BinaryTree{
   private static class BinaryTreeElement{
     public Comparable object;
     public BinaryTreeElement leftChild;
     public BinaryTreeElement rightChild;
  }
  private BinaryTreeElement root;
  public boolean isEmpty();
  public boolean add(Comparable o);
  public boolean delete(int number);
  public Object[] output();
  public Object[] toArray();
}

Interface Comparable{
  public int CompareTo(Object o);
  public int nextNumber();
  public int getNumber();
}

Обо всем по порядку. Класс BinaryTree содержит скрытый подкласс-узел дерева. Каждый узел бинарного дерева содержит левый и правый узел-потомок, а также хранимый объект. Объект реализует созданный интерфейс Comparable, который содержит методы, используемые для корректного размещения объектов в узлах дерева:

  1. Метод, получающий ответ на вопрос «как сравнивать объекты? Какой из них-текущий (this), или переданный методу, больше?»;
  2. Метод, определяющий алгоритм программы при попытке добавить элемент, номер которого совпадает с номером одного из ранее добавленных элементов;
  3. Метод, используемый для получения номера элемента для корректного добавления элемента в коллекцию.

Остальные два элемента класса BinaryTreeElement требуются для хранения узлов-потомков данного узла. Получается, что каждый узел является фракталом, что позволяет добавлять элементы в дерево пока не надоест или закончатся ресурсы компьютера.

Теперь перейдем непосредственно к классу BinaryTree. Этот класс содержит корневой узел root и методы для работы с ним и его потомками. Методы подробно описаны ниже.

  1. Чтобы не кидать в пользователя исключения при попытке получить элементы дерева, было бы неплохо создать метод, определяющий, есть ли в данном дереве элементы. К тому же, он совсем простой:
    public boolean isEmpty(){
            return root==null;
        }
  2. Зачем нужна коллекция, в которую невозможно добавить элементы? Поэтому реализуем метод add().

    Этот метод должен правильно определять место элемента в бинарном дереве, следовательно, нужно иметь возможность получения номера элемента. Чтобы не ограничивать возможности этой коллекции всего одним классом, с которым она сможет работать, и был создан интерфейс Comparable.

    Каждый элемент дерева-это фрактал, значит, рекурсивная функция в данной ситуации подойдет идеально. Однако при реализации рекурсивного метода, этот метод должен иметь элемент, считающийся локально (только в этом методе) корнем. При его вызове он определяет, в какую сторону шагать (если добавляемый элемент больше корневого-вправо, меньше-влево) и передает соответствующего потомка себе же рекурсивно. При этом пользователь не имеет доступа непосредственно к узлам, => не может определить начальную точку-локальный корень для данного метода, поэтому здесь реализовано два метода — приватный и доступный пользователю, который просто вызывает приватный метод, передавая ему корень дерева.
    Если добавляемый элемент имеет номер, который совпадает с номером ранее добавленного элемента, вызывается метод для смены номера нового элемента, затем генерируется исключение. Исключение используется для возврата в вызывающий (public) метод для того, чтобы сбросить рекурсию и искать место для элемента с начала списка.

    public boolean add(Comparable o){
            while(true) {
                try {
                    root = add(o, root);
                    break;
                }catch(ArrayStoreException e){
                    continue;
                }
            }
            return true;
        }
    
    private BinaryTreeElement add(Comparable o,BinaryTreeElement element){
            if(element==null){
                element=new BinaryTreeElement();
                element.object=o;
                return element;
            }
            else {
                //номер элементов не должен совпадать
                while(o.CompareTo(element.object) == 0) {
                    o.nextNumber();
                    //исключение используется для сброса стека (рекурсия) и сортировки элемента по его новому номеру с начала дерева
                    throw new ArrayStoreException();
                }
                if (o.CompareTo(element.object) > 0) {
                    //добавить справа
                    element.rightChild = add(o, element.rightChild);
                    return element;
                } else {
                    //добавить слева
                    element.leftChild = add(o, element.leftChild);
                    return element;
                }
            }
        }

  3. Затем следует добавить возможность удаления элементов из коллекции. Данная функция не представляет сложности, если у удаляемого элемента нет дочерних узлов, тогда можно не заботиться об их сохранности и уничтожить элемент. В противном случае я сохраняю ветку-потомка удаляемого элемента, удаляю требуемый элемент и рекурсивно добавляю элементы из сохраненной ветки в коллекцию методом add(BinaryTreeElement element,boolean b).

    Так как объект-это ссылочный тип данных, нельзя просто изменить в null текущий объект, вместо этого родитель должен удалить ссылку на элемент, поэтому код кажется сложным.
    Тактика удаления узла, имеющего потомков-поиск минимального элемента в его правом потомке (правом поддереве) и замена удаляемого элемента на найденный. Для поиска минимального элемента в определенном поддереве служит метод deleteMinChild()

    public Comparable delete(int number)throws NullPointerException {
            if (root == null) throw new NullPointerException();
            //объект, данные которого будут предоставлены в отчете об удалении
            Comparable object;
            //рекурсивный метод работает с детьми заданной точки, следовательно будет лучше вынести раьоту с корнем а данный метод
            if (root.object.getNumber() == number) {
                object = root.object;
                if (root.leftChild == null) {
                    if (root.rightChild == null) root = null;
                    else root = root.rightChild;
                }
                else {
                    if (root.rightChild == null) {
                        if (root.leftChild == null) root = null;
                        else root = root.leftChild;
                    }
                    else {
                        if (root.leftChild != null && root.rightChild != null) {
                            try {
                                BinaryTreeElement element=deleteMinChild(root.rightChild);
                                root.object = element.object;
                                add(element,false);
                            }catch(NullPointerException e){
                                //это значит, что левой ветки у правого узла нет, и он сам минимальный
                                root.rightChild.leftChild=root.leftChild;
                                root=root.rightChild;
                            }
                        }
                    }
                }
                return object;
            }
            object=delete(number, root);
            return object;
        }
    
        private BinaryTreeElement deleteMinChild(BinaryTreeElement element){
            if(element.leftChild.leftChild==null){
                BinaryTreeElement find=element.leftChild;
                element.leftChild=null;
                return find;
            }
            return deleteMinChild(element.leftChild);
        }
    
        private Comparable delete(int number, BinaryTreeElement element) throws NullPointerException{
            //это возвращаемый объект
            Comparable result=null;
    
            //необходимо идти вправо
            if(element.object.getNumber() < number) {
                //если правый потомок подходит
                if (element.rightChild.object.getNumber() == number) {
                    //правый узел-искомый элемент
                    result = element.rightChild.object;
    
                    //если у узла-потомка нет дочерних узлов, его требуется удалить
                    if (element.rightChild.leftChild == null && element.rightChild.rightChild == null) element.rightChild = null;
                    else {
                        if(element.rightChild.leftChild!=null && element.rightChild.rightChild!=null){
                            try {
                                BinaryTreeElement newElement = deleteMinChild(element.rightChild.rightChild);
                                element.rightChild.object=newElement.object;
                                add(newElement,false);
                            }catch(NullPointerException e){
                                //это значит, что в левой ветке правого узла элемента нет элементов и он сам минимальный
                                element.rightChild.rightChild.leftChild=element.rightChild.leftChild;
                                element.rightChild=element.rightChild.rightChild;
                            }
                        }
                        else {
                            if (element.rightChild.leftChild == null) element.rightChild = element.rightChild.rightChild;
                            else {
                                if (element.rightChild.rightChild == null)
                                    element.rightChild = element.rightChild.leftChild;
                            }
                        }
                    }
                }
                else{
                    result=delete(number,element.rightChild);
                }
            }
            //необходимо идти влево
            else {
                if (element.leftChild.object.getNumber() == number) {
                    //левый узел-искомый элемент
                    result = element.leftChild.object;
    
                    //если у узла-потомка нет дочерних узлов, его требуется удалить
                    if (element.leftChild.leftChild == null && element.leftChild.rightChild == null) element.leftChild = null;
                    else {
                        if (element.leftChild.leftChild!=null && element.leftChild.rightChild!=null){
                            try{
                                BinaryTreeElement newElement = deleteMinChild(element.leftChild.rightChild);
                                element.leftChild.object=newElement.object;
                                add(newElement,false);
    
                            }catch(NullPointerException e){
                                //это значит, что в левой ветке правого узла элемента нет элементов и он сам минимальный
                                element.leftChild.rightChild.leftChild=element.leftChild.leftChild;
                                element.leftChild=element.leftChild.rightChild;
                            }
                        }
                        else{
                            if(element.leftChild.rightChild==null) element.leftChild=element.leftChild.leftChild;
                            else{
                                if(element.leftChild.leftChild==null) element.leftChild=element.leftChild.rightChild;
                            }
                        }
                    }
                }
                else{
                    result=delete(number,element.leftChild);
                }
            }
            return result;
        }
  4. Для красивого вывода содержимого дерева реализуется метод output(). Данный метод просматривает бинарное дерево и выводит все его элементы, начиная с минимального, причем по отступа можно отследить вложенность узлов. Таких методов также два-видимый пользователю и приватный:
    public Object[] output(){
            if(root!=null)
                return output(root);
            return new String[]{"Бинарное дерево не содержит элементов"};
        }
    
        private Object[] output(BinaryTreeElement element) {
            ArrayList<String> result = new ArrayList<>();
            if (element.leftChild != null) {
                Object[] temp = output(element.leftChild);
                for (int i = 0; i < temp.length; i++) {
                    result.add("    "+ temp[i]);
                }
            }
            result.add(element.object.toString());
            if (element.rightChild != null) {
                Object[] temp = output(element.rightChild);
                for (int i = 0; i < temp.length; i++) {
                    result.add("    " + temp[i]);
                }
            }
            return result.toArray();
        }
  5. Предусмотрена возможность получения содержимого бинарного дерева в виде массива, элементы которого отсортированы от меньших (с меньшим номером) к большим. Метод генерирует исключение NullPointerException, если в коллекции нет элементов, поэтому перед его вызовом рекомендуется использовать метод isEmpty(). Этот метод очень похож на метод output(), однако возвращает не строковое описание объектов, а сами объекты.
    public Object[] toArray(){
            if(root==null) throw new NullPointerException();
            return toArray(root);
        }
    
        private Object[] toArray(BinaryTreeElement element){
            ArrayList<Comparable> result=new ArrayList<>();
            if (element.leftChild != null) {
                Object[] temp = toArray(element.leftChild);
                for (int i = 0; i < temp.length; i++) {
                    Comparable object=(Comparable)temp[i];
                    result.add(object);
                }
            }
            result.add(element.object);
            if (element.rightChild != null) {
                Object[] temp = toArray(element.rightChild);
                for (int i = 0; i < temp.length; i++) {
                    Comparable object=(Comparable)temp[i];
                    result.add(object);
                }
            }
            return result.toArray();
        }

Полный код разработанного класса, класса, реализующего интерфейс Comparable и программа, добавляющая элементы этого класса в коллекцию, тут.

Понимаю, что реализация слабовата, предложения по улучшению разработанного класса приветствуются.

Автор: Nerd0_0

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js