Class AVLBaum

java.lang.Object
  VerweisBaum
      SuchBaum
          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 class

AVLBaum.Status

Field Summary

Fields inherited from class VerweisBaum

wurzel

Constructor Summary

AVLBaum()

Method Summary

private void	balance1(AVLKnoten k, AVLBaum.Status s)
private void	balance2(AVLKnoten k, AVLBaum.Status s)
private java.lang.Comparable	del(AVLKnoten k, AVLKnoten v, AVLBaum.Status s)
boolean	delete(java.lang.Comparable x)
private boolean	deleteAVL(java.lang.Comparable x, AVLKnoten k, AVLKnoten v, AVLBaum.Status s)
boolean	insert(java.lang.Comparable x)
private boolean	insertAVL(java.lang.Comparable x, AVLKnoten k, AVLKnoten v, AVLBaum.Status s)
static void	printAVLBaum(Baum b, int tiefe)
private void	rotateLL(AVLKnoten k)
private void	rotateLR(AVLKnoten k)
private void	rotateRL(AVLKnoten k)
private void	rotateRR(AVLKnoten k)

Methods inherited from class SuchBaum

lookup

Methods inherited from class VerweisBaum

empty, left, right, value

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface Menge

empty

Constructor Detail

AVLBaum

public AVLBaum()

Method Detail

printAVLBaum

public static void printAVLBaum(Baum b,
                                int tiefe)

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,
                          AVLKnoten k,
                          AVLKnoten v,
                          AVLBaum.Status s)

rotateLL

private void rotateLL(AVLKnoten k)

rotateLR

private void rotateLR(AVLKnoten k)

rotateRR

private void rotateRR(AVLKnoten k)

rotateRL

private void rotateRL(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,
                          AVLKnoten k,
                          AVLKnoten v,
                          AVLBaum.Status s)

del

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

balance1

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

balance2

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