java - JAVA AVL树中平衡旋转的问题

Question

我正在编写一个保存对象的基本 AVL 树，我的代码中出现 Stackoverflow 错误(笑)，以递归树来获取当前节点的高度。我不认为我的高度代码实际上是问题，以至于我的旋转导致我的高度代码出现问题。

所以我所做的就是递归遍历节点的子节点，直到到达返回 0 的空节点，下一个/上一个调用(取决于您如何看待它)返回该调用的返回值的最大值node + 1 vs 无论对另一个子节点的调用最终是什么。当你看到它时，应该很清楚它是如何工作的。

旋转从适当的子节点创建一个临时节点，并更改该节点并将其设置为临时节点的子节点，并将父值设置为适当的节点。 (每个节点不仅有左右节点的引用还有父节点)

据我所知，插入方法工作正常，我的删除方法确实存在无限循环问题，但这是另一个问题了。

希望我已经提供了足够的信息，如果有什么我可以澄清的，请告诉我，这是我在这里的第一篇文章。但任何帮助都是值得赞赏的，这甚至让我的老师难住了。

感谢您花时间阅读这面文字墙。

import java.lang.Math;
/**
This is an AVL binary search tree class it uses a AVLNode to create an AVL Binary search tree.
 */


public class AVLTree {
        AVLNode root;
        Index empty;

        public AVLTree(){
            root = null;
        }

        public void insert(Object o, String ssNumber){
            if (root == null){
                root = new AVLNode(o);
                System.out.print("adding root");
            }
            else{
            AVLNode current = root;
            AVLNode node = new AVLNode(o);
            while (current != null){
                    if (((Comparable)current.getData()).compareTo(ssNumber) < 0){
                        if (current.getRight() != null){
                            current = current.getRight();
                        }
                        else{
                        //  System.out.println(((Index)(current.getData())).getSocial() +  " CURRENT DATA");
                            current.setRight(node);
                            current.getRight().setParent(current);
                        //  System.out.println("adding " + ((Index)o).getSocial() + "to the right of" + ((Index)(current.getData())).getSocial());
                            balanceTree(current);
                        //  if (current.getParent() != null)
                        //      System.out.println("the right child of " + (((Index)(current.getParent().getData())).getSocial()) + " is now " + (((Index)((current.getRight()).getData())).getSocial()) );
                            current=null;
                        }
                    }
                    else if (((Comparable)current.getData()).compareTo(ssNumber) > 0) {
                        if (current.getLeft()!= null){
                            current = current.getLeft();
                        }
                        else{
                        //  System.out.println(((Index)(current.getData())).getSocial() +  " CURRENT DATA");
                            current.setLeft(node);
                            current.getLeft().setParent(current);
                        //  System.out.println("adding " + ((Index)o).getSocial() + "to the left of" + ((Index)(current.getData())).getSocial());
                            balanceTree(current);
                        //  if (current.getParent() != null)
                        //      System.out.println("the left child of " + (((Index)(current.getParent().getData())).getSocial()) + " is now " + (((Index)((current.getLeft()).getData())).getSocial()) );
                            current=null;
                        }
                    }
            }
            }

        }
        public boolean delete(String ssNumber){
            AVLNode current = root;
            AVLNode parent = null;
            while (current.getData() != null){
                if (((Comparable)current.getData()).compareTo(ssNumber) > 0){
                    if(current.getLeft() != null){
                        parent = current;
                        current = current.getLeft();

                    }
                    else{
                        //System.out.print(((Index)(current.getData())).getSocial() + "not found");
                        return false;
                    }
                }
                else if (((Comparable)current.getData()).compareTo(ssNumber) < 0){
                    if (current.getRight()!=null){
                        parent = current;
                        current = current.getRight();
                    }
                    else{
                        //System.out.print(((Index)(current.getData())).getSocial() + "not found");
                        return false;
                    }
                }
                else{
                    if (current.getLeft() != null && current.getRight() != null){
                        AVLNode leftHighest = null;
                        AVLNode temp = current.getLeft();
                            while (temp.getRight() != null){
                                temp = temp.getRight();
                            }
                            leftHighest.setData(temp.getData());
                            temp.setData(current.getData());
                            current.setData(leftHighest.getData());
                            return delete(ssNumber);

                    }
                    if (current.getLeft() == null && current.getRight() != null){
                        if (parent == null){
                            root = current.getRight();
                        }
                        if (current == parent.getLeft()){
                            parent.setLeft(current.getRight());
                        }
                        else{
                            parent.setRight(current.getRight());
                        }
                    }
                    else if (current.getRight() == null && current.getLeft() != null){
                        if (parent == null){
                            root = current.getLeft();
                        }
                        if (current == parent.getLeft()){
                            parent.setLeft(current.getLeft());
                        }
                        else{
                            parent.setRight(current.getLeft());
                        }
                    }
                    else{
                        current.setData(null);
                        return true;
                        }
                    }
                }
        //System.out.print(((Index)(current.getData())).getSocial() + "not found");
        return false;
            }

        public int find(String ssNumber){
            AVLNode current = root;
            while (current.getData() != null){
                if (((Comparable)current.getData()).compareTo(ssNumber) > 0){
                    if(current.getLeft() != null){
                        current = current.getLeft();
                    }
                    else{
                        //System.out.print(((Index)(current.getData())).getSocial() + "not found");
                        return -1;
                    }
                }
                else if (((Comparable)current.getData()).compareTo(ssNumber) < 0){
                    if (current.getRight()!=null){
                        current = current.getRight();
                    }
                    else{
                        //System.out.print(((Index)(current.getData())).getSocial() + "not found");
                        return -1;
                    }
                }
                else{
                    return ((Index)(current.getData())).getArrayIndex();

                    }

            }
            return -1;
        }
        public void clear(){
            root = null;
        }

        //gets the height of the node's subtrees. Uses recursion to find the max height returns the highest value of each traversal adding 1 for each step.
        private int getHeight(AVLNode node){
            if (node == null){
                return 0;
            }
            else
            {
             //int x = getHeight( node.getLeft() );
             //int y = getHeight( node.getRight() );
             //return Math.max( x, y ) + 1;
          return Math.max(getHeight(node.getLeft()), getHeight(node.getRight())) + 1;
        }
        }
        //uses the value of getBalance to decide which type of rotation to undergo, and rotates the node by creating a temporary node from the proper child based on the type value.
        //the type value will be passed the balance.
        private AVLNode rotateNodes(AVLNode node, int type){
            AVLNode temp;
            //System.out.println("step C");
            if (type == -2){
                temp = node.getRight();
                temp.setParent(node.getParent());
                if (node.getParent() != null){
                    if (node == node.getParent().getLeft()){
                        temp.getParent().setLeft(temp);
                    }
                    else{
                        temp.getParent().setRight(temp);
                    }
                }
                node.setRight(temp.getLeft());
                if (node.getRight() != null){
                    node.getRight().setParent(node);
                }
                temp.setLeft(node);
                return temp;
            }
            else if (type == 2){
                temp = node.getLeft();
                temp.setParent(node.getParent());
                if (node.getParent() != null){
                    if (node == node.getParent().getLeft()){
                        temp.getParent().setLeft(temp);
                    }
                    else{
                        temp.getParent().setRight(temp);
                    }
                }
                node.setLeft(temp.getRight());
                if (node.getLeft() != null){
                    node.getLeft().setParent(node);
                }
                temp.setRight(node);
                node.setParent(temp);
                return temp;
            }
            else
                return node;
        }
        // Runs the methods necessary to balance a tree on each node until it reaches the root.
        private void balanceTree(AVLNode node){
            AVLNode temp;
            while (node != null){
                int balance = getHeight(node.getLeft()) - getHeight(node.getRight());
                if (balance == 2 || balance == -2){
                //System.out.println("step a");
                temp = rotateNodes(node, balance);
                //System.out.println("rotated");
                node.setData(temp.getData());
                node.setLeft(temp.getLeft());
                node.setRight(temp.getRight());
                node.setParent(temp.getParent());
                }
                else {
                //System.out.println("moving on");
                node = node.getParent();
                }
            }

        }
        //check balance
    }



    /**
This is an AVL node in a AVL binary tree it contains data and references to its two possible children and it's parent.
 */


public class AVLNode {
    private Object data;
    private AVLNode left;
    private AVLNode right;
    private AVLNode parent;

    public AVLNode(Object o){
        data = o;
        left = null;
        right = null;
        parent = null;
    }
    public AVLNode(){
        data = null;
        left = null;
        right = null;
        parent = null;
    }
    public Object getData(){
        return data;
    }
    public AVLNode getLeft(){
        return left;
    }
    public AVLNode getRight(){
        return right;
    }
    public void setData(Object index){
        data = index;
    }
    public void setLeft(AVLNode node){
        left = node;
    }
    public void setRight(AVLNode node){
        right = node;
    }
    public void setParent(AVLNode node){
        parent = node;
    }
    public AVLNode getParent(){
        return parent;
    }
}

    /**

The is a person class it holds 6 data fields about a person
 */


public class Person {
    private String lastName;
    private String firstName;
    private String socialSec;
    private String phoneNum;
    private char gender;
    private String date;

    public Person(String lastName, String firstName, String socialSec, String phoneNum, char gender, String date) {
    this.lastName = lastName;
    this.firstName = firstName;
    this.socialSec = socialSec;
    this.phoneNum = phoneNum;
    this.gender = gender;
    this.date = date;
    }

    public String getLast(){
        return lastName;
    }
    public String getFirst(){
        return firstName;
    }
    public String getSocial(){
        return socialSec;
    }
    public void setSocial(String string){
        this.socialSec = string;
    }
    public String getPhone(){
        return phoneNum;
    }
    public char getGender(){
        return gender;
    }
    public String getDate(){
        return date;
    }
    public String toString(){
        return ("Lastname: " + lastName + "\nFirstname: " + firstName + "\nSocial Security " + socialSec +
            "\nPhone Number: " + phoneNum + "\ngender " + gender);
    }
}

    /**
This is an index object it will contain the data type used as reference the binary tree, the social, and the references location in the array
 */


public class Index implements Comparable {
    String social;
    int arrayIndex;

    public Index(String social, int arrayIndex) {
        this.social = social;
        this.arrayIndex = arrayIndex;

    }
    public String getSocial(){
        return social;
    }
    public void setSocial(String social){
        this.social = social;
    }
    public int getArrayIndex(){
        return arrayIndex;
    }
    public void setArrayIndex(int arrayIndex){
        this.arrayIndex = arrayIndex;
    }
    public int compareTo(Object o){
        return social.compareTo((String)o);
    }

}
Here is the data read in from datafile (this is fake info)

    Hattell Zara    568472178   9562266952  F   8/23/1985
    Poff    Naomi   070028388   1868991633  F   10/25/1967
    Jackson Finley  766879776   6317272316  M   8/28/1984
    Lark    Kasey   278473635   4953108522  F   9/19/1967
    Grifith Josh    223948515   5916186412  M   11/21/1964
    Grimsby Mitchel 057848901   4921537476  M   10/28/1969
    Heesicker   Samara  578308596   0089823308  F   7/27/1964
    Amos    Kasey   148842321   7949241129  F   2/10/1985
    Johnson Angeline    003513447   8828061677  F   4/21/1977
    Aldridge    John    418953690   5006720120  M   6/23/1968
    Mckibbon    Vasilios    523212165   0040010068  M   7/30/1972
    Woodhouse   Jacob   522626205   6985940430  M   7/31/1966
    Newell  Shante  022753752   8483983762  F   2/24/1978
    Ramer   Tyler   025694346   6123635287  M   9/14/1980
    Leatherman  Tige    297071697   1106435680  M   8/11/1981
    Johnston    Halle   263543220   3417907710  F   11/17/1960
    Aber    Myah    669617355   3276358736  F   12/10/1961
    Frizzle Archie  150388947   1472418810  M   8/5/1960
    Mcdivit Ashley  294735567   2017661755  M   11/3/1978
    Jackson Sophie  698928462   0185800213  F   3/18/1960
    Bechtel William 700321659   1376473348  M   11/30/1974
    Larimer Alessi  745219302   2445633750  F   12/12/1964
    Bodler  Amelie  424759320   2676866912  F   11/25/1961
    Niswander   Ebony   218384979   7468337166  F   12/3/1970
    Overlees    Minnesha    594664590   9411189605  F   8/5/1981
    Jones   Haley   692179128   9046757546  F   3/24/1968
    Weiner  Lee 111223333   2223334444  M   2/31/1978


    /*
    main class to create a Binary search tree
    */

    import java.io.*;
    import java.util.Scanner;
    import java.util.regex.*;
    import java.util.List;
    import java.util.ArrayList;

    public class AVLdatabase {

     public static void main(String[] args) {
        AVLTree anAVLTree = new AVLTree();
        File file = new File("datafile.txt");
        List<Person> dataArray = new ArrayList<Person>();
            try {
            Scanner scanner = new Scanner(file);
            //read lines and place the data into person objects
            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();
                Scanner lineScanner = new Scanner(line).useDelimiter("\t");
                while (lineScanner.hasNext()) {
                    Person record = new Person(lineScanner.next(),lineScanner.next(),lineScanner.next(),lineScanner.next(),(lineScanner.next()).charAt(0),lineScanner.next());
                    System.out.print(record.getLast() + " ");
                    System.out.print(record.getFirst() + " ");
                    System.out.print(record.getSocial() + " ");
                    System.out.println();
                    Index index = new Index(record.getSocial(), dataArray.size());
                    dataArray.add(record);
                    anAVLTree.insert(index, record.getSocial());
                    System.out.println("The array index is " + (dataArray.size()-1));
                }
            }
            }
            catch (IOException e) {
                    System.out.print("No File");
                }
     }
    }

Answer 1

你的高度代码看起来不错。我假设您的旋转代码导致您的叶子之一链接回内部节点。

例如:

   A
  / \
 B   C

可能会成为:

   B
  / \
 C   A
    / \
   B   C

A 仍然引用 B，B 引用 A，B 引用 B，B 引用 A，等等。当然，A -> B 将引用根 B，但我无法在这里想象。