avltree.cs

Data Structures and Algorithms with Object-Oriented Design Patterns in C# 这本书的范例代码dll自己反编译的source

namespace Opus6
{
    using System;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: AVLTree.cs,v 1.4 2001/10/28 19:50:08 brpreiss Exp $")]
    public class AVLTree : BinarySearchTree
    {
        public AVLTree()
        {
            this.height = -1;
        }

        protected void AdjustHeight()
        {
            if (this.IsEmpty)
            {
                this.height = -1;
            }
            else
            {
                this.height = 1 + Math.Max(this.Left.Height, this.Right.Height);
            }
        }

        public override void AttachKey(object obj)
        {
            if (!this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            base.key = obj;
            base.left = new AVLTree();
            base.right = new AVLTree();
            this.height = 0;
        }

        protected override void Balance()
        {
            this.AdjustHeight();
            if (this.BalanceFactor > 1)
            {
                if (this.Left.BalanceFactor > 0)
                {
                    this.LLRotation();
                }
                else
                {
                    this.LRRotation();
                }
            }
            else if (this.BalanceFactor < -1)
            {
                if (this.Right.BalanceFactor < 0)
                {
                    this.RRRotation();
                }
                else
                {
                    this.RLRotation();
                }
            }
        }

        public override object DetachKey()
        {
            this.height = -1;
            return base.DetachKey();
        }

        protected void LLRotation()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            AVLTree tree1 = this.Right;
            base.right = base.left;
            base.left = this.Right.left;
            this.Right.left = this.Right.right;
            this.Right.right = tree1;
            object obj1 = base.key;
            base.key = this.Right.key;
            this.Right.key = obj1;
            this.Right.AdjustHeight();
            this.AdjustHeight();
        }

        protected void LRRotation()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            this.Left.RRRotation();
            this.LLRotation();
        }

        public static void Main()
        {
            SearchTree tree1 = new AVLTree();
            BinarySearchTree.TestSearchTree(tree1);
        }

        protected void RLRotation()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            this.Right.LLRotation();
            this.RRRotation();
        }

        protected void RRRotation()
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            AVLTree tree1 = this.Left;
            base.left = base.right;
            base.right = this.Left.right;
            this.Left.right = this.Left.left;
            this.Left.left = tree1;
            object obj1 = base.key;
            base.key = this.Left.key;
            this.Left.key = obj1;
            this.Left.AdjustHeight();
            this.AdjustHeight();
        }


        protected int BalanceFactor
        {
            get
            {
                if (this.IsEmpty)
                {
                    return 0;
                }
                return (this.Left.Height - this.Right.Height);
            }
        }

        public override int Height
        {
            get
            {
                return this.height;
            }
        }

        public AVLTree Left
        {
            get
            {
                return (AVLTree) base.Left;
            }
        }

        public AVLTree Right
        {
            get
            {
                return (AVLTree) base.Right;
            }
        }


        protected int height;
    }
}