Балансировка двоичного дерева поиска

Question

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

public void balance(){ 
    if(isEmpty()){ 
     System.out.println("Empty Tree"); 
     return; 
    } 
    if(!isEmpty()){ 
     values = new Object[count()]; 
     index = 0; 
     createAscendingArray(root); 
     clear(); 
     balanceRecursive(0, index); 
        values = null; 
    } 


} 

private void createAscendingArray(TreeNode<E> current){ 
    if(current == null) 
     return; 
    if(current.getLeftNode() != null) 
     createAscendingArray(current.getLeftNode()); 
    else if(current.getRightNode() != null) 
     createAscendingArray(current.getRightNode()); 
    values[index] = current.getData(); 
    index++; 


} 

private void balanceRecursive(int low, int high){ 
    if(low == high) 
     return; 
    else if(low > high/2) 
     balanceRecursive(high/2, high); 
    else if(low < high/2) 
     balanceRecursive(low, high/2); 

    E insert = (E) values[(low + high)/2]; 
    insertItem(insert); 

} 

Чтобы добавить некоторую ясность, индекс является предопределенным частных ИНТ переменной, значения также предопределенный Object []. Корень - это узел в начале моего неуравновешенного дерева. Во-первых, я знаю, что мой массив добавляет значения в обратном порядке. Прямо сейчас я просто тестирую с добавлением 1, 2, 3, 4, 5, 6 к дереву, поэтому мой массив выходит с 654321. Я не уверен, как мне нужно добавить значения к мой массив, чтобы он добавлял их в правильное восходящее, а не в порядке убывания.

Теперь, когда я смотрю на свой код, я знаю, что метод balanceRecursive() никогда не будет работать для реализации верхней половины массива. Моя проблема в том, что я не знаю, как написать ее так, чтобы она была. Мне поручено сделать это с помощью рекурсии, о которой я не очень хорошо знаком. Я мог бы сделать это с помощью итерации, но это строго определено. Я должен использовать рекурсию.

Баланс должен работать как этот: алгоритм для баланса()

• Проверьте, если дерево пусто

о Если да, то печати «Пустое дерево»

о Возврат

• Если дерево не пуст

о Создать массив объектов размер индекса Set Tree

O до 0

O Заполняем массив со всеми значениями в возрастающем порядке (createAscendingArray())

о Clear Tree

о заселить Дерево из массива Object (balanceRecursive())

о Установить массив значений для нуль

(у меня есть методы, написанные уже за счёт() для подсчета количества узлов в моем дереве и ясно(), чтобы освободить дерево)

balanceRecursive() предполагается сделать следующее повторно заполняет дерево со значениями в элементе данных значений. Они должны быть добавлены в соответствующем порядке для создания сбалансированного дерева.

• Добавить средний элемент

• Это создает два субсчета массивы, левый и правый

• Добавить в середину этих подразделам массивов

• Это создает еще больше вложенных массивов

• Продолжайте добавлять середины вспомогательных массивов до тех пор, пока их не будет

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

EDIT:

Я изменил мою createAscendingArray() к следующему:

private void createAscendingArray(TreeNode<E> current){ 

    if(current == null) 
     return; 
    createAscendingArray(current.getLeftNode()); 
    values[index] = current.getData(); 
    index++; 
    createAscendingArray(current.getRightNode()); 



} 

Это должно функционировать как заказовМои траверсе BST я прав?

Answer 1

Во-первых, вам не нужно копировать старое дерево. Вы можете перебалансировать его на месте с помощью Stout-Warren algorithm, хотя, по общему признанию, это немного сложнее, чем просто чтение старого дерева, его очистка и создание нового.

Но, как на ваш фактический вопрос, функция рекурсии вы хотите

private void balanceRecursive(int low, int high){ 

    if(low == high) 
     return; 

    int midpoint = (low + high)/2; 

    E insert = (E) values[midpoint]; 
    insertItem(insert); 

    balanceRecursive(midpoint+1, high); 
    balanceRecursive(low, midpoint); 
} 

Как и в сторону, не использовать массив объектов для values, используйте List<E> так что вам не нужно, чтобы бросить для ввода E, когда вы читаете его.

Answer 2

Балансировка выполняется при вставке и удалении: см. Balancing Trees.