0
Im записывает базовое дерево AVL, в котором хранятся объекты, im, имеющие ошибку Stackoverflow (lol) в моем коде, чтобы рекурсивно пройти через дерево, чтобы получить высоту текущего узла. Я не думаю, что мой код высоты на самом деле является проблемой настолько, что мой поворот приводит к тому, что мой код возраста имеет проблему.Проблема с балансировкой вращения в дереве AVL JAVA
Итак, что я делаю, я рекурсирую через дочерние узлы узла, пока не достиг нулевого узла, который возвращает 0, следующий/предшествующий вызов (в зависимости от того, как вы его смотрите) возвращает максимум возврата вызова этот узел + 1 против любого вызова другого ребенка. Должно быть довольно ясно, как это работает, когда вы это видите.
Вращение создает временный узел из соответствующего дочернего элемента и изменяет узел и устанавливает его дочернему объекту временного узла и устанавливает родительские значения в соответствующие узлы. (Каждый узел имеет ссылку не только на левый и правый узлы, но и на родительский узел)
Метод вставки прекрасно работает, насколько я могу судить, у меня есть проблема с бесконечным циклом в моем методе удаления, но это другой вопрос в другое время.
Надеюсь, я дал достаточно информации, дайте мне знать, если есть что-то, что я могу прояснить, это мой первый пост здесь. но любая помощь приветствуется, у этого даже мой инструктор в тупике.
Спасибо, что даже потратили время, чтобы прочитать эту стену текста.
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");
}
}
}
Gisted: https://gist.github.com/988340255959eb1de8ba –