0
Im écrire un arbre AVL de base qui contient des objets, im ayant une erreur Stackoverflow (lol) dans mon code pour recurse à travers l'arbre pour obtenir la hauteur du nœud actuel. Je ne pense pas que mon code de hauteur est vraiment le problème tellement que ma rotation provoque mon code de hauteur pour avoir le problème.Problème avec l'équilibrage d'une rotation dans un arbre AVL JAVA
Donc ce que je fais est je recurse à travers les enfants du noeud jusqu'à ce que j'atteigne un noeud nul qui renvoie 0, l'appel suivant/précédent (selon comment vous le regardez) renvoie le maximum de renvoyer l'appel ce nœud + 1 vs quel que soit l'appel sur l'autre enfant finit par être. Il devrait être assez clair comment cela fonctionne quand vous le voyez. La rotation crée un noeud temporaire à partir de l'enfant approprié et modifie le noeud et le définit sur l'enfant du noeud temporaire et définit les valeurs parentes sur les noeuds appropriés. (Chaque nœud a une référence non seulement à un nœud gauche et à droite, mais le nœud parent)
La méthode d'insertion fonctionne très bien autant que je peux dire, j'ai un problème avec une boucle infinie dans ma méthode de suppression, mais c'est une autre question pour une autre fois.
Espérons que j'ai donné assez d'informations, laissez-moi savoir s'il y a quelque chose que je peux clarifier c'est mon premier article ici. mais toute aide est appréciée, celle-ci a même mon instructeur perplexe.
Merci d'avoir pris le temps de lire ce mur de texte.
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 –