Java - Баланс бинарного дерева с «Brute Force»

Question

Я пытаюсь написать метод в Java, который уравновешивает бинарное дерево, описываются следующим образом:

... написать заказовМой обход дерева , а затем использовать рекурсивный метод (подобно бинарному поиску), чтобы вставить средний элемент массива в качестве корня, а затем построить сбалансированные левые и правые поддеревья.

Однако я не понимаю, как это сделать. До сих пор я пробовал различные подходы, но ничего не сработало.

У меня также есть итератор inOrder, который возвращает ArrayList из всех элементов в дереве, так что он закрыт.

Это то, что я в настоящее время здание прочь:

public void rebalance() 
{ 
    Iterator<T> it = iteratorInOrder(); 
    List<T> list = new ArrayList<>(); 

    while (it.hasNext()) 
    { 
     list.add(it.next()); 
    } 
    balanceRecursive(); 
} 

private void balanceRecursive() 
{ 
    //something here 
} 

, а потом я просто это в конце добавить/удалить методы элемента:

if ((getHeight() - getMinHeight()) > 5) 
      rebalance(); 

Итак, как может Я об этом?

Answer 1

Если у вас есть List по общему положению, это станет относительно простым. sublist операция означает, что вам даже не нужно передавать индексы вокруг:

Node<T> buildBalancedTree(List<T> values) { 
    if (values.isEmpty()) { 
     return Node.NULL; 
    } else { 
     int middle = values.size()/2; 
     Node node = new Node(values.get(middle)); 
     node.setLeft(buildBalancedTree(values.subList(0, middle))); 
     node.setRight(buildBalancedTree(values.subList(middle + 1, values.size()))); 
     return node; 
    } 
} 

Я предполагаю, что у вас есть Node.NULL представить пустые суб-деревья, а не «нулевой», потому что вы должны :-)

Итак, ваш метод ребалансировки будет выглядеть примерно так:

root = buildBalancedTree(root.getListOfValuesInOrder()); 

Answer 2

В сбалансированном дереве правое и левое поддерево должно отличаться не более чем на 1 элемент. Учитывая отсортированный массив - как это сделано с помощью вашего inorder-traversal - это становится довольно простым. Основная идея заключалась бы в создании фактического дерева, которое равно тому, которое неявно пересекается двоичным поиском. Начните с среднего элемента массива как root, средний элемент подмассива слева от середины станет левым дочерним элементом, тем же шаблоном для правильного ребенка. Постройте поддеревья с левым дочерним элементом как root соответственно левой половиной массива, то же самое для правого поддерева.

//lower and upper are the INCLUSIVE bounds of the sublist, from which the tree should be built 
Node<T> buildRecursively(int lower , int upper , List<T> elements){ 
    //no more nodes can be produced on this path 
    if(lower > upper) 
     return null; 

    //build node from the middle-element of the elements 
    int middle = (lower + upper)/2; 
    Node<T> result = new Node<>(elements.get(middle)); 

    //build left and right child for the according pieces of the array/list 
    result.setLeftChild(buildRecursively(lower , middle - 1 , elements); 
    result.setRightChild(buildRecursively(middle + 1 , upper , elements); 

    return result; 
} 

//build entire tree: 
Node<T> root = buildRecursively(0 , elements.size() - 1 , elements); 

С фактическим массивом это будет выглядеть следующим образом:

   sorted ascending---------> 
         4 
       2    6 
      1  3   5  7 
indices:  0 1 2  3 4 5 6 

Answer 3

1. Построить узел с средним элементом массива в качестве значения.
2. Примените (1) к левой части массива рекурсивно и установите узел, сконструированный как левый дочерний узел корневого узла.
3. Примените (1) к правой части массива рекурсивно и установите узел, сконструированный как правый дочерний узел корневого узла.