Java AVL Связанное дерево двоичного поиска - правильное обновление BalanceFactor - PullRequest
Новая
       83

Java AVL Связанное дерево двоичного поиска - правильное обновление BalanceFactor

0 голосов
/ 04 мая 2020

В настоящее время мне назначен проект java, который содержит в основном предварительно написанный проект связанного дерева двоичного поиска AVL. Мне дано заполнить файлы Node и Tree, и мои единственные задачи: 1. правильно написать метод ребалансировки (Node node), который определяет, какой тип из 4 вращений должен быть выполнен, и 2. Используя данные методы rotateleft / rotateright, обновить balanceFactor для управляемых узлов. Можно сказать, что BalanceFactor - это «высота ПРАВОГО дерева минус высота ЛЕВОГО дерева». Он будет отрицательным при взвешивании по левому краю и положительным при взвешивании по правому краю.

На данный момент я считаю, что у меня есть метод ребалансировки, но, возможно, это может быть root проблемы. 

    private boolean rebalance(AVLBinarySearchTreeNode<T> node)
   {
       if(this.isBalanced(node))                    //if tree is currently balanced
           return false;

       if(this.isLeftWeighted(node)) {              //left imbalance case   

           if(this.isRightWeighted(node.left)) {    //left-right imbalance rotation
               System.out.println("Performing LEFT- rotation around: " + this.nodeConfig(node.left));
               this.rotateLeft(node.left);
           }
           System.out.println("Performing RIGHT rotation around: " + this.nodeConfig(node));
           this.rotateRight(node);
       }
       else if(this.isRightWeighted(node)) {        //right imbalance case

           if(this.isLeftWeighted(node.right)) {    //right-left imbalance rotation
               System.out.println("Performing RIGHT- rotation around: " + this.nodeConfig(node.right));
               this.rotateRight(node.right);        
           }
           System.out.println("Performing LEFT rotation around: " + this.nodeConfig(node));
           this.rotateLeft(node);
       }

       if(node.parent==null)
           root=node;

       return true;
   }

Выше, кажется, работает правильно, однако, и я остаюсь с проблемой при вызове rotateLeft / rotateRight и обновлении балансаFactor сводной. 

    private void rotateLeft(AVLBinarySearchTreeNode<T> pivot)
   {

     AVLBinarySearchTreeNode<T> parent = pivot.parent;  //copies OLD parent

     AVLBinarySearchTreeNode<T> newPivot = pivot.right; //designates NEW pivot
     newPivot.parent = pivot.parent;                    //replaces CUR pivot's parent

     if (parent != null) {        // we are attached to a node in the path to the root
       if (pivot == parent.left)
         parent.left = newPivot;  // on the left
       else
         parent.right = newPivot; // on the right
     } 
     else {                         // or we are at root of the tree
       this.root = newPivot;

     }

     pivot.right = newPivot.left;

     if (pivot.right != null) {
        pivot.right.parent = pivot;
        //pivot.balanceFactor+=1;   //adding a right node
     }

     newPivot.left = pivot;
     pivot.parent = newPivot;

     //------------------WORK-------------------------------
     pivot.balanceFactor = (pivot.balanceFactor-2);//<< 
     if(newPivot!=null)
         newPivot.balanceFactor -=1;

     //pivot.height = max(height(t.left), height(t.right)) + 1;

     //newPivot.height = max(height(y.left), height(y.right)) + 1;
   }

Они прекрасно работают и при добавлении новые узлы в дереве, но, похоже, происходит сбой при удалении (узел Node) (метод remove также предварительно написан и вызывает удаление баланса после удаления необходимого узла) вызывается, когда рядом с root узлом. Это вывод, число рядом с узлом является фактором баланса. Если числа нет, коэффициент баланса, который равен HELD, скорее всего, равен 0, даже если BalanceFactor ДОЛЖЕН быть чем-то другим. Единственный код, который мне необходимо изменить, это pivot.BalanceFactor = ... 

Removing 'c' tree is:
              :d:1              
        I-------X-------I       
       :c:             :f:      
                    I---X---I   
                   :e:     :g:  
Element 'c' found
post-remove
              :d:2              
                L-------I       
                       :f:      
                    I---X---I   
                   :e:     :g:  
Performing LEFT rotation around: null:=d:2:<null,f
realigned
                  -1:f:                 
          I---------X---------I         
         :d:                 :g:        
          L----I                        
              :e:

Как видно на приведенном выше дисплее, это состояния дерева. Также кажется, что операции были выполнены правильно, ОДНАКО, как вы можете видеть с узлом: d: его конечное состояние НЕ имеет +1 коэффициент баланса. Это проблема, которую я хотел бы решить.

В каком ОДНОМ случае pivot.balanceFactor не имеет + = / - = 2? Когда это только + = / - = 1?

Спасибо и дайте мне знать, если я опущу что-либо, что мешает понять проблему. Напоминание, balanceFactor, rotateLeft / rotateRight, remove - все написано заранее, единственные цели, которые у меня есть: 1. написать метод ребалансировки и 2. обновить BalanceFactors ВНУТРИ rotateLeft / rotateRight.

...