вращение дерева avl

Question

Я пытаюсь создать дерево avl, которое обновляется каждый раз, когда дерево не сбалансировано.Вращения работают, но у меня есть ошибка, когда, например, если узел дерева 7, leftChild 6, leftchild из leftchild 5 становится узлом 6, leftchild 5, rightchild 7, и после балансировки я добавляю новый узел, узел сначала сравнивается7, а не с 6. Как я могу решить эту проблему?

Это основной класс:

import java.io.*;
import javax.swing.*;
import java.util.*;
import java.lang.*;

public class NewMain  implements Cloneable{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {

        File file = new File ("AVLTree.txt");
        ArrayList <TreeNode> array = new ArrayList ();
        Scanner kb = new Scanner (System.in);
        int num = 0;
        TreeNode root = new TreeNode ();
        do {
            System.out.print("              AVL Tree            \n\n\n\n");
            System.out.println("1. Create a new binary tree");
            System.out.println("2. Save Tree");
            System.out.println("3. Load Tree");
            System.out.println("4. Enter a new node in the tree");
            System.out.println("5. Show current AVL tree");
            System.out.println("6. Show inorder traversal");
            System.out.println("7. Search");
            System.out.println("8. Quit  \n\n\n\n\n\n\n");
            System.out.print("Enter a number: ");
            num = kb.nextInt ();
            if (num == 1){
                if (array.isEmpty ())
                {
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
                else
                {
                    array.clear();
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
            }
            if (num == 2) 
            {
                    FileOutputStream outFile = null;
                    ObjectOutputStream oos = null;
                    try 
                    {
                        outFile = new FileOutputStream(file);             
                        oos = new ObjectOutputStream(outFile);
                        for (TreeNode list : array) 
                        {                 
                            oos.writeObject(list);                                      
                        }
                        oos.close();
                    }
                    catch (Exception e) 
                    {
                        System.out.print("Save Not Successful!");
                    }
               }
            if (num == 3) 
            {
                if (file.exists()) 
                {
                    FileInputStream inFile = null;
                    ObjectInputStream ios = null;
                    try 
                    {
                        Object obj = null;
                        inFile = new FileInputStream(file); 
                        ios = new ObjectInputStream(inFile); 
                        while ((obj = ios.readObject()) != null) {              
                            if (obj instanceof TreeNode) 
                            { 
                                array.add((TreeNode) obj);
                            }
                        }
                        ios.close(); 
                    } 
                    catch(EOFException e)
                    {   
                    }
                    catch (Exception e) 
                    {
                        System.out.print("File was not found while loading");
                    }
                }
            }
            if (num == 4)
            {
                System.out.print ("Enter a new child node: ");
                int value = kb.nextInt ();              
                try 
                {
                    array.add(root.insert(value));  
                    root.balance();
                }
                catch (Exception e)
                {
                    System.out.print (e.getMessage());
                }

            }
            if (num == 5){
                System.out.print ("Pointer Number\t\tLeft\t\tNode\t\tRight\t\tLeft Height\t\tRight Height\n");
                for (int i=0; i<array.size();i++)
                {                     
                      System.out.print (i+"\t\t\t"+array.indexOf(array.get(i).getLeftChild())+"\t\t"+array.get(i).getValue()+"\t\t"+array.indexOf(array.get(i).getRightChild())+"\t\t"+array.get(i).getLeftHeight()+"\t\t\t"+array.get(i).getRightHeight()+"\n");
                }
            }
            if (num == 6)
            {
                System.out.print("Inorder traversal: ");
                System.out.println(root.InOrderTraversal());
                System.out.print("Postorder traversal: ");
                System.out.println(root.PostOrderTraversal());
                System.out.print("Preorder traversal: ");
                System.out.println(root.PreOrderTraversal());
            }
            if (num == 7)
            {
                System.out.print("Enter node to be searched: ");
                int node = kb.nextInt ();
                for (int i = 0; i<array.size();i++)
                {
                    if (node == array.get(i).getValue())
                    {
                        System.out.print ("Node is in index "+i+"\n");
                        break;
                    }
                    if (i == array.size()-1 && node != array.get(i).getValue())
                    {
                        System.out.print ("Node not found in the tree!"+"\n");
                        break;
                    }
                }

            }            
        }while (num != 8);
    }
}

Это из обычного класса Java:

import java.lang.StringBuilder;
import java.util.ArrayList;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.swing.*;
public class TreeNode implements Serializable, Cloneable
{
    public Integer value;
    public TreeNode leftChild;
    public TreeNode rightChild;

    public TreeNode()
    {
        this.value = null;
        this.leftChild = null;
        this.rightChild = null;
    }

    public TreeNode(int value)
    {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }

    public int getValue()
    {
        return this.value;
    }

    public void setValue(int value)
    {
        this.value = value;
    }

    public TreeNode getLeftChild()
    {
        return this.leftChild;
    }

    public void setLeftChild(TreeNode leftChild)
    {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild()
    {
        return this.rightChild;
    }

    public void setRightChild(TreeNode rightChild)
    {
        this.rightChild = rightChild;        
    }

    public int getLeftHeight()
    {
        if (this.leftChild == null)
        {
            return 0;
        }
        else
        {    
            return this.getLeftChild().getHeight() + 1;
        }

    }

    public int getRightHeight()
    {
        if (this.rightChild == null)
        {
            return 0;
        }
        else
        {
            return this.getRightChild().getHeight() + 1;
        }
    }

    public TreeNode insert(int value) throws Exception
    {
      if(this.value == null && this.leftChild == null && this.rightChild == null)
      {
            this.value = value;
            return this;
      }
        else
        {
            TreeNode node = new TreeNode (value);
            if(value < this.value)
            {
                if(this.getLeftChild() == null)
                {
                    this.setLeftChild (node);
                    return node;
                }
                else
                {
                    return this.getLeftChild().insert(value);
                }
            }
            else if(value > this.value)
            {
                if(this.getRightChild() == null)
                {
                    this.setRightChild(node);
                    return node;
                }

                else
                {
                    return this.getRightChild().insert(value);
                }

            }
            else 
            {
                return null;
            }
        } 

    }
    public TreeNode balance() throws Exception
    {
        if (Math.abs(this.getLeftHeight() - this.getRightHeight())==2)
        {
            if (this.rightChild == null)
            {
                if(this.leftChild.leftChild != null)
                { 
                    return this.LLRotation ();
                }
                if(this.leftChild.rightChild != null)
                { 
                    return this.LRRotation ();
                }
            }
            if (this.leftChild == null)
            {
                if (this.rightChild.rightChild != null)
                {
                    return this.RRRotation ();
                }
                if (this.rightChild.leftChild != null)
                {
                    return this.RLRotation ();
                }
            }
        }
        else
        {
            if (this.getLeftChild () != null)
            {
                return this.getLeftChild().balance();
            }
            if (this.getRightChild () != null)
            {
                return this.getRightChild().balance();
            }
        }
        return this;
    }
    public int getHeight ()
    {
        if (this.leftChild == null && this.rightChild == null)
        {
            return 0;
        }
        else
        {
            int leftH = 0;
            int rightH = 0;
            if (this.leftChild != null)
            {
                leftH++;
                leftH += this.getLeftChild().getHeight();
            }
            if (this.rightChild != null)
            {
                rightH++;
                rightH += this.getRightChild().getHeight();
            }
            return Math.max(leftH,rightH);
        }
    }

    public TreeNode LLRotation ()
    {
        TreeNode temp = this.leftChild;
        this.leftChild = null;
        temp.rightChild = this;
        return temp;
    }

    public TreeNode RRRotation ()
    {  
        TreeNode temp = this.rightChild;
        this.rightChild = temp.leftChild;
        try 
        {
            temp.leftChild = (TreeNode)this.clone();
        } 
        catch (CloneNotSupportedException ex) 
        {
        }
        this.value = temp.value;
        this.rightChild = temp.rightChild;
        this.leftChild = temp.leftChild;
        return temp;
    }

    public TreeNode LRRotation ()
    {
        this.leftChild = this.leftChild.RRRotation();
        return LLRotation();
    }

    public TreeNode RLRotation ()
    {
        this.rightChild = this.rightChild.RRRotation();
        return RRRotation();
    }

    public String InOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().InOrderTraversal());
            }
            sb.append(this.value).append(" ");

            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().InOrderTraversal());
            }
        }
        return sb.toString();
    }
    public String PostOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PostOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PostOrderTraversal());
            }
            sb.append(this.value).append(" ");
        }
        return sb.toString();
    }
    public String PreOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            sb.append(this.value).append(" ");
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PreOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PreOrderTraversal());
            }
        }
        return sb.toString();
    }
}

Answer 1

1. Код немного сложнее, чем должно быть. Я надеюсь, что здесь приведу более простую версию, которую вы сами можете правильно сбалансировать. Как, возможно, вам лучше сделать вращение / перебалансировку указателя внутри вставки. Не чувствую себя обязанным давать очки; это только половина ответа.

2. Только примечание: поле value может быть ìnt.

3. Определенно проще для рекурсивных алгоритмов, если объект "this" может быть нулевым. Это может быть достигнуто путем помещения всего дерева в один открытый класс, который внутренне использует класс TreeNode.

   public class Tree {
   
   private static class TreeNode {
       private int value;
       private TreeNode left;
       private TreeNode right;
   
       private TreeNode(int value, TreeNode left, TreeNode right) {
           this.value = value;
           this.left = left;
           this.right = right;
       }
   }
   
   private static class AlreadyExistsException extends Exception {
       private TreeNode node;
   
       private AlreadyExistsException(TreeNode node) {
           this.node = node;
       }
   
       public TreeNode getNode() {
           return node;
       }
   }
   
   private TreeNode root;
   private int size;
   
   public boolean insert(int value) {
       try {
           root = insertInto(root, value);
           ++size;
           return true;
       } catch (AlreadyExistsException e) {
           // Fine.
           return false;
       }
   }
   
   private TreeNode insertInto(TreeNode node, int value) throws AlreadyExistsException {
       if (node == null) {
           return new TreeNode(value, null, null);
       }
       if (value < node.value) {
           node.left = insertInto(node.left, value);
           return node;
       } else if (value > node.value) {
           node.right = insertInto(node.right, value);
           return node;
       } else {
           throw new AlreadyExistsException(node);
       }
   }
   }
   

   1. Поскольку вы видите балансировку непосредственно во время вставки, можно выполнить вставку с поворотом указателя в < и > (3 указателя: левый крайний левый лист или самый правый левый лист). Вернувшись из рекурсии, можно было бы собрать родителя крайнего правого листа слева и выполнить ротацию. Или в любой другой момент. Существует 3 варианта!

Answer 2

Возможно, потому что root все еще указывает на старый узел. Вы уверены, что хотите игнорировать возвращаемое значение balance () в отмеченной строке?

if (num == 4) {
    System.out.print ("Enter a new child node: ");
    int value = kb.nextInt ();              
    try {
        array.add(root.insert(value));  
        root.balance();  // look here
    } catch (Exception e) {
        System.out.print (e.getMessage());
    }
}

Кстати, дерево AVL, как описано в литературе, не рекурсивно рассматривает дерево целиком, чтобы найти баланс узла.