Binært AVL tre
Oppgavebeskrivelse
Oppgåva bygger vidare på oppgåva frå forrige veke der du skulle teikne ut eit binærtre, så fyrste del av oppgåva har du alt gjort.
Du skal her lage ein applikasjon som lar brukaren legge inn tal, og ta ut tal, av eit binært søketre. For kvar endring skal treet teiknast ut på skjermen.
- Lag dine eigne BinærNode og BinærtSøkeTre klasser, gjerne etter mønster frå Weiss sine klasser.
- Lag ein applikasjon med fylgjande grensesnitt: Eit tekstfelt der brukar kan
skrive inn
ny verdi som skal inn i treet, og label foran. Eit tekstfelt der brukar
kan skrive
inn verdi som skal slettast frå treet, og label foran. Ein EXIT-knapp, og
eit
ikkje-redigerbart tekstfelt for feilmeldingar. Kan gjerne ha ein "demo" knapp som legg inn ein del faste verdiar i treet. - Når brukar skriv i ny-verdi feltet og trykkar ENTER, skal verdien inn i treet. Når brukar skriv verdi i slettefeltet og trykkar ENTER, skal verdien slettast frå treet. For kvar endring av treet skal det teiknast ut grafisk, slik som i figur 19.1 - 19.4. Ved feil - skriv feilmelding i feilmeldingsfeltet.
- Legg gjerne inn din eigen insert-metode frå oppgåvene over, for å sjå om den fungerer.
- Legg inn AVL-metodane i binærtreklassa di, slik at treet held seg balansert ved innsetting. Node-objekta bør da vedlikehalde ein høgde-variabel.
- Treet vil ikkje halde seg balansert ved sletting. Modifiser slette-metoden slik at den fyrst slettar ubalansert, deretter sjekkar om treet er i balanse. Om det ikkje er i balanse rettast det opp ved å legge alle nodane over i ny trestruktur. Sidan innsetting held treet balansert, vil dette nye treet vere i balanse. Meld frå i feilmeldingsfeltet dersom denne opprettinga vert utført.
Testprogram
import tre.*;
/**
* Testprogram.java
* Oppretter ett tomt tre, starter GUI og sender inn treet
*
* Oblig 6
* Hilde Vestøl: 106288
* Mads Collier Ringdal: 103370
*/
public class Testprogram {
static public void main(String[] args) {
BinaryAVLTree<Integer> tree = new BinaryAVLTree<Integer>();
GUITree theTree = new GUITree(tree);
theTree.setVisible(true);
}
}
GUI
package tre;
/**
* BinaryAVLNode.java
* En klasse for selve noden
*
* Oblig 6
* Hilde Vestøl: 106288
* Mads Collier Ringdal: 103370
*/
public class BinaryAVLNode<AnyType> {
protected int height;
protected AnyType element;
protected BinaryAVLNode<AnyType> leftChild;
protected BinaryAVLNode<AnyType> rightChild;
public BinaryAVLNode(AnyType element) {
this(element, null, null);
}
public BinaryAVLNode(AnyType element, BinaryAVLNode leftChild, BinaryAVLNode rightChild) {
this.element = element;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.height = 0;
}
public AnyType getNodeValue() {
return element;
}
public BinaryAVLNode<AnyType> getLeftNode() {
return leftChild;
}
public BinaryAVLNode<AnyType> getRightNode() {
return rightChild;
}
}
/**
* BinaryAVLNode.java
* En klasse for selve noden
*
* Oblig 6
* Hilde Vestøl: 106288
* Mads Collier Ringdal: 103370
*/
public class BinaryAVLNode<AnyType> {
protected int height;
protected AnyType element;
protected BinaryAVLNode<AnyType> leftChild;
protected BinaryAVLNode<AnyType> rightChild;
public BinaryAVLNode(AnyType element) {
this(element, null, null);
}
public BinaryAVLNode(AnyType element, BinaryAVLNode leftChild, BinaryAVLNode rightChild) {
this.element = element;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.height = 0;
}
public AnyType getNodeValue() {
return element;
}
public BinaryAVLNode<AnyType> getLeftNode() {
return leftChild;
}
public BinaryAVLNode<AnyType> getRightNode() {
return rightChild;
}
}
BinaryAVLTree
package tre;
/**
* BinaryAVLTree.java
* Treklassen med AVL balansering av treet.
*
* Oblig 6
* Hilde Vestøl: 106288
* Mads Collier Ringdal: 103370
*/
public class BinaryAVLTree<AnyType extends Comparable<? super AnyType>>{
private BinaryAVLNode<AnyType> rootNode;
/**
* Konstruktør uten paramtere, setter kun rotnoden til null.
*/
public BinaryAVLTree() {
rootNode = null;
}
/**
* Konstruktør som tar et variabelt antall argumenter
*/
public BinaryAVLTree(AnyType ... args){
this();
for (AnyType element : args)
insert(element);
}
/**
* En public metode for å få tak i rotnoden utenfra
*/
public BinaryAVLNode<AnyType> getRootNode() {
return rootNode;
}
/**
* Setter inn i treet
* @param AnyType element er objektet/elementet som skal settes inn i treet
* @throws DuplicateItemException hvis element allerede eksisterer i treet
*/
public void insert(AnyType element) {
rootNode = insert(element, rootNode);
}
/**
* En privat metode for å sette inn i treet
* @param AnyType element er objektet/elementet som skal settes inn i treet
* @param BinaryAVLNode rotnoden til treet/subtreet
* @return den nye noden
* @throws DuplicateItemException hvis element allerede finnes i treet
*/
private BinaryAVLNode<AnyType> insert(AnyType element, BinaryAVLNode<AnyType> node) {
if (node == null) {
node = new BinaryAVLNode<AnyType>(element);
} else if (element.compareTo(node.element) < 0) {
node.leftChild = insert(element, node.leftChild);
if (height(node.leftChild) - height(node.rightChild) == 2) {
if (element.compareTo(node.leftChild.element) < 0) {
node = rotateWithLeftChild(node);
} else {
node = doubleWithLeftChild(node);
}
}
} else if (element.compareTo(node.element) > 0) {
node.rightChild = insert(element, node.rightChild);
if (height(node.rightChild) - height(node.leftChild) == 2) {
if (element.compareTo(node.rightChild.element) > 0 ){
node = rotateWithRightChild(node);
} else {
node = doubleWithRightChild(node);
}
}
} else {
throw new DuplicateItemException("Elementet finnes allerede i treet");
}
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
return node;
}
/**
* Sletter/fjerner fra treet ved å lage ett nytt tre og utnytte at insert balanserer treet
* @param AnyType element er objektet/elementet som skal fjernes fra treet
* @throws ItemNotFoundException hvis elementet ikke finnes i treet
*/
public void remove(AnyType element) {
//Sjekker om det kun er rotnoden igjen.. i så fall settes denne til null
if (rootNode.leftChild == null && rootNode.rightChild == null) {
rootNode = null;
return;
}
rootNode = remove(element, rootNode);
//Hvis treet ikke er i balanse så settes verdiene inn i ett nytt
//insert metoden passer på at alt er i balanse..
if (!balance(rootNode) ){
BinaryAVLTree<AnyType> newTree = new BinaryAVLTree<AnyType>();
makeNewTree(this.rootNode, newTree);
this.rootNode = newTree.rootNode;
}
}
/**
* Sjekker om treet er i balanse.
* @param BinaryAVLNode<AnyType> node som er treets/subtreets rotnode
* @return true/false om det er i balanse eller ikke.
*/
private boolean balance(BinaryAVLNode<AnyType> node) {
if (height(node.leftChild) - height(node.rightChild) == 2) {
return false;
} else if (height(node.rightChild) - height(node.leftChild) == 2) {
return false;
}
//hvis node har både høyre og venstre barn
if (node.leftChild != null && node.rightChild != null) {
boolean left = balance(node.leftChild);
if (!left)
return false;
return balance(node.rightChild);
}
//hvis ikke sjekkes det høyre, eller venstre
if (node.leftChild != null) {
return balance(node.leftChild);
}
if (node.rightChild != null) {
return balance(node.rightChild);
}
return true;
}
/**
* En privat metode som kopierer hele treet inn i et nytt tre.
* Tar seg nytte av insert-metoden sin automatisk balansering.
* @param BinaryAVLNode<AnyType> oldNode som er det gamle treets node
* @param BinaryAVLTree<AnyType> newTree som er det nye tree
*/
private void makeNewTree(BinaryAVLNode<AnyType> oldNode, BinaryAVLTree<AnyType> newTree) {
newTree.insert(oldNode.element);
if (oldNode.leftChild != null) {
makeNewTree(oldNode.leftChild, newTree);
}
if (oldNode.rightChild != null) {
makeNewTree(oldNode.rightChild, newTree);
}
}
/**
* En privat metode for å fjerne/slette fra treet
* @param AnyType element er objektet/elementet som skal fjernes fra treet
* @param BinaryAVLNode rotnoden til treet/subtreet
* @return den nye noden
* @throws ItemNotFoundException hvis elementet ikke finnes i treet
*/
private BinaryAVLNode<AnyType> remove(AnyType element, BinaryAVLNode<AnyType> node) {
if (node == null) {
throw new ItemNotFoundException();
}
if (element.compareTo(node.element) < 0) {
node.leftChild = remove(element, node.leftChild);
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
} else if (element.compareTo(node.element) > 0) {
node.rightChild = remove(element, node.rightChild);
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
} else if (node.leftChild != null && node.rightChild != null) {
node.element = findMin(node.rightChild);
node.rightChild = removeMin(node.rightChild);
} else {
node = (node.leftChild != null) ? node.leftChild : node.rightChild;
}
return node;
}
/**
* Intern metode som sletter det minste elementet fra et subtre
* @param node som er treet/subtreets rotnode
* @return den nye node
* @throws ItemNotFoundException node er tom.
*/
protected BinaryAVLNode<AnyType> removeMin( BinaryAVLNode<AnyType> node )
{
if( node == null ) {
throw new ItemNotFoundException( );
} else if( node.leftChild != null ) {
node.leftChild = removeMin( node.leftChild );
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
return node;
} else {
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
return node.rightChild;
}
}
/**
* Finner det minste elementet i treet
* @param BinaryAVLNode<AnyType> node er treet/subtreets rotnode
* @return det minste elementet
*/
public AnyType findMin(BinaryAVLNode<AnyType> node) {
if (rootNode == null) {
return null;
}
while (node.leftChild != null) {
node = node.leftChild;
}
return node.element;
}
/**
* Gir høyden på treet/subtreet
* @param BinaryAVLNode<AnyType> node rotnoden til treet/subtreet
* @returns høyden til noden
*/
private int height(BinaryAVLNode<AnyType> node) {
return node == null ? -1 : node.height;
}
/**
* Roterer den binære noden med sitt venstre barn
* @param BinaryAVLNode<AnyType> node
* @return den nye rotnoden
*/
private BinaryAVLNode<AnyType> rotateWithLeftChild(BinaryAVLNode<AnyType> node) {
BinaryAVLNode<AnyType> newRoot = node.leftChild;
node.leftChild = newRoot.rightChild;
newRoot.rightChild = node;
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
newRoot.height = Math.max(height(newRoot.leftChild), newRoot.height) + 1;
return newRoot;
}
/**
* Roterer den binære noden med sitt høyre barn
* @param BinaryAVLNode<AnyType> node
* @return den nye rotnoden
*/
private BinaryAVLNode<AnyType> rotateWithRightChild(BinaryAVLNode<AnyType> node) {
BinaryAVLNode<AnyType> newRoot = node.rightChild;
node.rightChild = newRoot.leftChild;
newRoot.leftChild = node;
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
newRoot.height = Math.max(height(newRoot.leftChild), newRoot.height) + 1;
return newRoot;
}
/**
* Dobbelt roterer den binære noden:
* - først roteres dens venstre barn med sitt høyre barn
* - deretter seg selv med sitt venstre barn
* @param BinaryAVLNode<AnyType> node er noden som skal roteres dobbelt
* @return den nye rotnoden (etter at høyden er oppdatert)
*/
private BinaryAVLNode<AnyType> doubleWithLeftChild(BinaryAVLNode<AnyType> node) {
node.leftChild = rotateWithRightChild(node.leftChild);
return rotateWithLeftChild(node);
}
/**
* Dobbelt roterer den binære noden:
* - først roteres dens høyre barn med sitt venstre barn
* - deretter seg selv med sitt høyre barn
* @param BinaryAVLNode<AnyType> node er noden som skal roteres dobbelt
* @return den nye rotnoden (etter at høyden er oppdatert)
*/
private BinaryAVLNode<AnyType> doubleWithRightChild(BinaryAVLNode<AnyType> node) {
node.rightChild = rotateWithLeftChild(node.rightChild);
return rotateWithRightChild(node);
}
}
/**
* BinaryAVLTree.java
* Treklassen med AVL balansering av treet.
*
* Oblig 6
* Hilde Vestøl: 106288
* Mads Collier Ringdal: 103370
*/
public class BinaryAVLTree<AnyType extends Comparable<? super AnyType>>{
private BinaryAVLNode<AnyType> rootNode;
/**
* Konstruktør uten paramtere, setter kun rotnoden til null.
*/
public BinaryAVLTree() {
rootNode = null;
}
/**
* Konstruktør som tar et variabelt antall argumenter
*/
public BinaryAVLTree(AnyType ... args){
this();
for (AnyType element : args)
insert(element);
}
/**
* En public metode for å få tak i rotnoden utenfra
*/
public BinaryAVLNode<AnyType> getRootNode() {
return rootNode;
}
/**
* Setter inn i treet
* @param AnyType element er objektet/elementet som skal settes inn i treet
* @throws DuplicateItemException hvis element allerede eksisterer i treet
*/
public void insert(AnyType element) {
rootNode = insert(element, rootNode);
}
/**
* En privat metode for å sette inn i treet
* @param AnyType element er objektet/elementet som skal settes inn i treet
* @param BinaryAVLNode rotnoden til treet/subtreet
* @return den nye noden
* @throws DuplicateItemException hvis element allerede finnes i treet
*/
private BinaryAVLNode<AnyType> insert(AnyType element, BinaryAVLNode<AnyType> node) {
if (node == null) {
node = new BinaryAVLNode<AnyType>(element);
} else if (element.compareTo(node.element) < 0) {
node.leftChild = insert(element, node.leftChild);
if (height(node.leftChild) - height(node.rightChild) == 2) {
if (element.compareTo(node.leftChild.element) < 0) {
node = rotateWithLeftChild(node);
} else {
node = doubleWithLeftChild(node);
}
}
} else if (element.compareTo(node.element) > 0) {
node.rightChild = insert(element, node.rightChild);
if (height(node.rightChild) - height(node.leftChild) == 2) {
if (element.compareTo(node.rightChild.element) > 0 ){
node = rotateWithRightChild(node);
} else {
node = doubleWithRightChild(node);
}
}
} else {
throw new DuplicateItemException("Elementet finnes allerede i treet");
}
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
return node;
}
/**
* Sletter/fjerner fra treet ved å lage ett nytt tre og utnytte at insert balanserer treet
* @param AnyType element er objektet/elementet som skal fjernes fra treet
* @throws ItemNotFoundException hvis elementet ikke finnes i treet
*/
public void remove(AnyType element) {
//Sjekker om det kun er rotnoden igjen.. i så fall settes denne til null
if (rootNode.leftChild == null && rootNode.rightChild == null) {
rootNode = null;
return;
}
rootNode = remove(element, rootNode);
//Hvis treet ikke er i balanse så settes verdiene inn i ett nytt
//insert metoden passer på at alt er i balanse..
if (!balance(rootNode) ){
BinaryAVLTree<AnyType> newTree = new BinaryAVLTree<AnyType>();
makeNewTree(this.rootNode, newTree);
this.rootNode = newTree.rootNode;
}
}
/**
* Sjekker om treet er i balanse.
* @param BinaryAVLNode<AnyType> node som er treets/subtreets rotnode
* @return true/false om det er i balanse eller ikke.
*/
private boolean balance(BinaryAVLNode<AnyType> node) {
if (height(node.leftChild) - height(node.rightChild) == 2) {
return false;
} else if (height(node.rightChild) - height(node.leftChild) == 2) {
return false;
}
//hvis node har både høyre og venstre barn
if (node.leftChild != null && node.rightChild != null) {
boolean left = balance(node.leftChild);
if (!left)
return false;
return balance(node.rightChild);
}
//hvis ikke sjekkes det høyre, eller venstre
if (node.leftChild != null) {
return balance(node.leftChild);
}
if (node.rightChild != null) {
return balance(node.rightChild);
}
return true;
}
/**
* En privat metode som kopierer hele treet inn i et nytt tre.
* Tar seg nytte av insert-metoden sin automatisk balansering.
* @param BinaryAVLNode<AnyType> oldNode som er det gamle treets node
* @param BinaryAVLTree<AnyType> newTree som er det nye tree
*/
private void makeNewTree(BinaryAVLNode<AnyType> oldNode, BinaryAVLTree<AnyType> newTree) {
newTree.insert(oldNode.element);
if (oldNode.leftChild != null) {
makeNewTree(oldNode.leftChild, newTree);
}
if (oldNode.rightChild != null) {
makeNewTree(oldNode.rightChild, newTree);
}
}
/**
* En privat metode for å fjerne/slette fra treet
* @param AnyType element er objektet/elementet som skal fjernes fra treet
* @param BinaryAVLNode rotnoden til treet/subtreet
* @return den nye noden
* @throws ItemNotFoundException hvis elementet ikke finnes i treet
*/
private BinaryAVLNode<AnyType> remove(AnyType element, BinaryAVLNode<AnyType> node) {
if (node == null) {
throw new ItemNotFoundException();
}
if (element.compareTo(node.element) < 0) {
node.leftChild = remove(element, node.leftChild);
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
} else if (element.compareTo(node.element) > 0) {
node.rightChild = remove(element, node.rightChild);
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
} else if (node.leftChild != null && node.rightChild != null) {
node.element = findMin(node.rightChild);
node.rightChild = removeMin(node.rightChild);
} else {
node = (node.leftChild != null) ? node.leftChild : node.rightChild;
}
return node;
}
/**
* Intern metode som sletter det minste elementet fra et subtre
* @param node som er treet/subtreets rotnode
* @return den nye node
* @throws ItemNotFoundException node er tom.
*/
protected BinaryAVLNode<AnyType> removeMin( BinaryAVLNode<AnyType> node )
{
if( node == null ) {
throw new ItemNotFoundException( );
} else if( node.leftChild != null ) {
node.leftChild = removeMin( node.leftChild );
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
return node;
} else {
node.height = Math.max( height(node.leftChild), height(node.rightChild) ) + 1;
return node.rightChild;
}
}
/**
* Finner det minste elementet i treet
* @param BinaryAVLNode<AnyType> node er treet/subtreets rotnode
* @return det minste elementet
*/
public AnyType findMin(BinaryAVLNode<AnyType> node) {
if (rootNode == null) {
return null;
}
while (node.leftChild != null) {
node = node.leftChild;
}
return node.element;
}
/**
* Gir høyden på treet/subtreet
* @param BinaryAVLNode<AnyType> node rotnoden til treet/subtreet
* @returns høyden til noden
*/
private int height(BinaryAVLNode<AnyType> node) {
return node == null ? -1 : node.height;
}
/**
* Roterer den binære noden med sitt venstre barn
* @param BinaryAVLNode<AnyType> node
* @return den nye rotnoden
*/
private BinaryAVLNode<AnyType> rotateWithLeftChild(BinaryAVLNode<AnyType> node) {
BinaryAVLNode<AnyType> newRoot = node.leftChild;
node.leftChild = newRoot.rightChild;
newRoot.rightChild = node;
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
newRoot.height = Math.max(height(newRoot.leftChild), newRoot.height) + 1;
return newRoot;
}
/**
* Roterer den binære noden med sitt høyre barn
* @param BinaryAVLNode<AnyType> node
* @return den nye rotnoden
*/
private BinaryAVLNode<AnyType> rotateWithRightChild(BinaryAVLNode<AnyType> node) {
BinaryAVLNode<AnyType> newRoot = node.rightChild;
node.rightChild = newRoot.leftChild;
newRoot.leftChild = node;
node.height = Math.max(height(node.leftChild), height(node.rightChild) ) + 1;
newRoot.height = Math.max(height(newRoot.leftChild), newRoot.height) + 1;
return newRoot;
}
/**
* Dobbelt roterer den binære noden:
* - først roteres dens venstre barn med sitt høyre barn
* - deretter seg selv med sitt venstre barn
* @param BinaryAVLNode<AnyType> node er noden som skal roteres dobbelt
* @return den nye rotnoden (etter at høyden er oppdatert)
*/
private BinaryAVLNode<AnyType> doubleWithLeftChild(BinaryAVLNode<AnyType> node) {
node.leftChild = rotateWithRightChild(node.leftChild);
return rotateWithLeftChild(node);
}
/**
* Dobbelt roterer den binære noden:
* - først roteres dens høyre barn med sitt venstre barn
* - deretter seg selv med sitt høyre barn
* @param BinaryAVLNode<AnyType> node er noden som skal roteres dobbelt
* @return den nye rotnoden (etter at høyden er oppdatert)
*/
private BinaryAVLNode<AnyType> doubleWithRightChild(BinaryAVLNode<AnyType> node) {
node.rightChild = rotateWithLeftChild(node.rightChild);
return rotateWithRightChild(node);
}
}
