Что не так с моим методом баланса в моем BinarySearchTree? (Джава) - PullRequest
Новая
       30

Что не так с моим методом баланса в моем BinarySearchTree? (Джава)

0 голосов
/ 30 апреля 2019

Я создал метод, который должен сбалансировать BinarySearchTree.

Инструкции заключались в том, что метод баланса должен обновлять дерево так, чтобы оно было сбалансированным, а это означает, что наибольшая разница между высотами поддеревьев составляет не более 1.

Со следующим процессом:

• Получить массив отсортированных значений в дереве (у нас есть метод, который может это сделать)

• Назначить корень дерева для результата вспомогательного метода buildTreeUtil (описанного ниже)

• Вызвать assignFirst, чтобы обновить «первый» атрибут дерева

Вспомогательный метод buildTreeUtil (E [], int, int, BSTNode parent) перестраивает дерево, используя отсортированный список значений. Поскольку у него есть этот отсортированный список, ему не нужно искать, куда вставлять новые значения, поэтому он не вызывает (и не должен) вызывать метод add. Вместо этого он выборочно получает значения из отсортированного списка значений при добавлении новых узлов. Его алгоритм выглядит следующим образом:

• Если параметр «start» больше, чем параметр «end», рекурсия должна остановиться

• Создать новый узел, хранящий средний элемент в списке

• Назначить левую ссылку нового узла на рекурсивный вызов, используя левую половину списка

• Назначить правую ссылку нового узла рекурсивному вызову, используя правую половину списка

Вот следующий код: 

public void balance()
{
    this.root = buildTreeUtil(toArray(), 0, size(), first);
    assignFirst();
}

private BSTNode<E> buildTreeUtil(E[] values, int start, int end, BSTNode<E> parent)
{
    if(start > end)
    {
        return null;
    }
    int mid = (start + end)/2;
    BSTNode<E> node = new BSTNode<E>(values[mid]);

    node.left = buildTreeUtil(values, start, mid - 1, parent.left);

    node.right = buildTreeUtil(values, mid + 1, end, parent.right);

    return node;
}

private void assignFirst()
{
    if (root.left != null)
    {
        first.left = first;
    }
    else
        {
        first = root;
    }
}
@SuppressWarnings("unchecked")
public E[] toArray()
{
    ArrayList<E> aList = new ArrayList<E>();
    E[] arr = (E[]) new Comparable[this.numElements];
    toArray(this.root, aList);
    return aList.toArray(arr);
}

private void toArray(BSTNode<E> node, List<E> aList)
{
    if (node != null)
    {
        toArray(node.left, aList);
        aList.add(node.data);
        toArray(node.right, aList);
    }
}

Это всего лишь остальная часть моего кода, поэтому есть некоторая полезная справочная информация. 

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
    this.root = null;
    this.numElements = 0;
}
public class Iterator
{
    private BSTNode<E> currentNode;

    public Iterator()
    {
        currentNode = first;
    }

    public boolean hasNext()
    {
        return currentNode != null;
    }

    public E next()
    {
        E value = currentNode.data;
        currentNode = currentNode.next;
        return value;
    }
}
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;
    public BSTNode<E> parent;
    public BSTNode<E> next;

    public BSTNode(E data)
    {
        this(data, null, null, null, null);
    }

    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
    {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.next = next;
    }
  }
}

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

...