Class AVLBaum

java.lang.Object
  extended by VerweisBaum
      extended by SuchBaum
          extended by AVLBaum
All Implemented Interfaces:
Baum, Menge

public class AVLBaum
extends SuchBaum

Ein AVLBaum ist ein SuchBaum, bei dem alle Knoten ausgeglichen sind. Das heisst, fuer jeden seiner Knoten unterscheiden sich die Hoehen seiner beiden Teilbaeume maximal um eins.


Nested Class Summary
private static class AVLBaum.AVLKnoten
           
private static class AVLBaum.Status
           
 
Nested classes/interfaces inherited from class VerweisBaum
VerweisBaum.Knoten
 
Field Summary
 
Fields inherited from class VerweisBaum
wurzel
 
Constructor Summary
  AVLBaum()
           
private AVLBaum(AVLBaum.AVLKnoten k)
           
 
Method Summary
private  void balance1(AVLBaum.AVLKnoten k, AVLBaum.Status s)
           
private  void balance2(AVLBaum.AVLKnoten k, AVLBaum.Status s)
           
private  java.lang.Comparable del(AVLBaum.AVLKnoten k, AVLBaum.AVLKnoten v, AVLBaum.Status s)
           
 boolean delete(java.lang.Comparable x)
           
private  boolean deleteAVL(java.lang.Comparable x, AVLBaum.AVLKnoten k, AVLBaum.AVLKnoten v, AVLBaum.Status s)
           
 boolean insert(java.lang.Comparable x)
           
private  boolean insertAVL(java.lang.Comparable x, AVLBaum.AVLKnoten k, AVLBaum.AVLKnoten v, AVLBaum.Status s)
           
 Baum left()
           
 Baum right()
           
private  void rotateLL(AVLBaum.AVLKnoten k)
           
private  void rotateLR(AVLBaum.AVLKnoten k)
           
private  void rotateRL(AVLBaum.AVLKnoten k)
           
private  void rotateRR(AVLBaum.AVLKnoten k)
           
 java.lang.String toString()
           
 
Methods inherited from class SuchBaum
lookup
 
Methods inherited from class VerweisBaum
empty, value
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

AVLBaum

public AVLBaum()

AVLBaum

private AVLBaum(AVLBaum.AVLKnoten k)
Method Detail

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

left

public Baum left()
Specified by:
left in interface Baum
Overrides:
left in class VerweisBaum

right

public Baum right()
Specified by:
right in interface Baum
Overrides:
right in class VerweisBaum

insert

public boolean insert(java.lang.Comparable x)
Specified by:
insert in interface Menge
Overrides:
insert in class SuchBaum

insertAVL

private boolean insertAVL(java.lang.Comparable x,
                          AVLBaum.AVLKnoten k,
                          AVLBaum.AVLKnoten v,
                          AVLBaum.Status s)

rotateLL

private void rotateLL(AVLBaum.AVLKnoten k)

rotateLR

private void rotateLR(AVLBaum.AVLKnoten k)

rotateRR

private void rotateRR(AVLBaum.AVLKnoten k)

rotateRL

private void rotateRL(AVLBaum.AVLKnoten k)

delete

public boolean delete(java.lang.Comparable x)
Specified by:
delete in interface Menge
Overrides:
delete in class SuchBaum

deleteAVL

private boolean deleteAVL(java.lang.Comparable x,
                          AVLBaum.AVLKnoten k,
                          AVLBaum.AVLKnoten v,
                          AVLBaum.Status s)

del

private java.lang.Comparable del(AVLBaum.AVLKnoten k,
                                 AVLBaum.AVLKnoten v,
                                 AVLBaum.Status s)

balance1

private void balance1(AVLBaum.AVLKnoten k,
                      AVLBaum.Status s)

balance2

private void balance2(AVLBaum.AVLKnoten k,
                      AVLBaum.Status s)