Data Structure and Algorithm (C # Implementation) Series --- Avltree (1)
Using system;
Using system.collections;
Namespace Datastructure
{
///
/// Avltree's summary description. ----- Balance binary look tree
///
Public Class Avltree: BST
{
Protected int Height; // The high definition of the empty tree is -1;
// Construct an empty binary look tree
Public avltree (): base ()
{
//
// TODO: Add constructor logic here
//
HEIGHT = -1;
}
Public avltree (Object _obj): Base (_OBJ)
{
HEIGHT = 0;
}
/ / -------------------------------------------------------------------------------------------- ------------------
Protected Override Object getemptyInstance (uint _degree)
{Return new avltree ();
/ / -------------------------------------------------------------------------------------------- ------------------
protected int BalanceFactor ()
{
IF (this.isempty ())
Return 0;
Return (AVLTREE) THIS.LEFT). HEIGHT - ((Avltree) this.right. Heart;
}
// Adjust the height
Protected void adjustheight () {this.height = math.max ((avltree) this.right) .height, ((avltree) .right) .height) 1;}
// Four rotation modes when balance
protected void llroid ()
{
IF (this.isempty ())
Throw new Exception ("My: Invalid Operation!");
AVLTREE AVLB = New Avltree (THISKEY);
Avlb.attachsubtree (1, (avltree) THIS [0] [1]);
Avlb.attachsubtree (2, (avltree) THIS [1]);
THIS.KEY = this [0].
THIS [0] = this [0] [0];
THIS [1] = AVLB;
// Adjust the height of the two nodes
(AVLTREE). "This.right) .adjustheight ();
THIS.ADJUSTHEIGHT ();
}
protected void lrotation ()
{
IF (this.isempty ())
Throw new Exception ("My: Invalid Operation!");
(AVLTREE) THIS.LEFT) .rtrotation ();
THIS.llotation ();
}
protected void rrrotation ()
{
IF (this.isempty ())
Throw new Exception ("My: Invalid Operation!");
AVLTREE AVLB = New Avltree (THISKEY);
Avlb.attachsubtree (1, (avltree) THIS [0]);
AVLB.AttachSubtree (2, (avltree) THIS [1] [0]);
//avla.attachsubtree(1,avlb);
//this=avla; hey=this[1].key;
THIS [0] = AVLB;
THIS [1] = this [1] [1];
// Adjust the height of the two nodes
(Avltree) .left) .adjustheight ();
THIS.ADJUSTHEIGHT ();
}
protected void rlrotation ()
{
IF (this.isempty ())
Throw new Exception ("My: Invalid Operation!");
(AVLTREE) this.right) .llrotation ();
this.rrrotation ();
}
