AVL操作详细

//节点实体类

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace AVLTreeTool

{

    public class TreeNode<T,T2>

    {

        /// <summary>

        /// 前驱结点

        /// </summary>

        private TreeNode<T, T2> hNode;

        public TreeNode<T, T2> HNode

        {

            get { return hNode; }

            set { hNode = value; }

        }

        /// <summary>

        /// 左子树

        /// </summary>

        private TreeNode<T,T2> lNode;

        public TreeNode<T,T2> LNode

        {

            get { return lNode; }

            set { lNode = value; }

        }

        /// <summary>

        /// 右子树

        /// </summary>

        private TreeNode<T,T2> rNode;

        public TreeNode<T,T2> RNode

        {

            get { return rNode; }

            set { rNode = value; }

        }

        /// <summary>

        /// 平衡因子

        /// </summary>

        private int bal=0;

        public int Bal

        {

            get { return bal; }

            set { bal = value; }

        }

        /// <summary>

        /// 值

        /// </summary>

        private T value;

        public T Value

        {

            get { return this.value; }

            set { this.value = value; }

        }

        /// <summary>

        /// 值为value对应的选项列表

        /// </summary>

        private HashSet<T2> havalue;

        public HashSet<T2> Havalue

        {

            get { return havalue; }

            set { havalue = value; }

        }

    }

}

//AVL操作类

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace AVLTreeTool

{

    public class AVLTreeOPer

    {

        private  TreeNode<int, string> _root;

        private int p;//记录_root的节点个数。

        #region

        /// <summary>

        /// 根据最大价格（maxid）和最小价格（minid）获取货物名称列表

        /// </summary>

        /// <param name="minid"></param>

        /// <param name="maxid"></param>

        /// <returns></returns>

        public Dictionary<int, List<string>> findTreeNodeByRange(int minid, int maxid)

        {

            return new Dictionary<int, List<string>>();

        }

        /// <summary>

        /// 根据价格获取货物名称列表

        /// </summary>

        /// <param name="Id"></param>

        /// <returns></returns>

        public List<string> findTreeNodeById(int Id)

        {

            if (null != _root)

            {

                TreeNode<int, string> potNode = _root;

                int potvalue = _root.Value;

                TreeNode<int, string> lnode = _root.LNode;

                TreeNode<int, string> rnode = _root.RNode;

                HashSet<string> rets = _root.Havalue;

                while (Id != potvalue)

                {

                    if (Id < potvalue)

                    {

                        if (null != lnode.Value)

                        {

                            potvalue = lnode.Value;

                            lnode = lnode.LNode;

                            rnode = lnode.RNode;

                            rets = lnode.Havalue;

                        }

                        else

                            break;

                    }

                    else

                    {

                        if (null != rnode.Value)

                        {

                            potvalue = rnode.Value;

                            lnode = rnode.LNode;

                            rnode = rnode.RNode;

                            rets = rnode.Havalue;

                        }

                        else

                            break;

                    }

                }

                if (potvalue == Id)

                    return rets.ToList();

                else

                    return new List<string>();

            }

            else

                return new List<string>();

        }

        /// <summary>

        /// 判断改价格是否存在（存在返回true，不存在返回false）

        /// </summary>

        /// <param name="Id"></param>

        /// <returns></returns>

        public bool isExsist(int Id)

        {

            if (null != _root)

            {

                int potvalue = _root.Value;

                TreeNode<int, string> lnode = _root.LNode;

                TreeNode<int, string> rnode = _root.RNode;

                HashSet<string> rets = _root.Havalue;

                while (Id != potvalue)

                {

                    if (Id < potvalue)

                    {

                        if (null != lnode)

                        {

                            potvalue = lnode.Value;

                            lnode = lnode.LNode;

                            rnode = lnode.RNode;

                            rets = lnode.Havalue;

                        }

                        else

                            break;

                    }

                    else

                    {

                        if (null != rnode)

                        {

                            potvalue = rnode.Value;

                            lnode = rnode.LNode;

                            rnode = rnode.RNode;

                            rets = rnode.Havalue;

                        }

                        else

                            break;

                    }

                }

                if (potvalue == Id)

                    return true;

                else

                    return false;

            }

            else

                return false;

        }

        #endregion

        /// <summary>

        /// 查找最接近的value值的节点

        /// </summary>

        /// <param name="value"></param>

        /// <returns></returns>

        public TreeNode<int, string> FindTreeNodeByValue(int value)

        {

            if (null != _root)

            {

                TreeNode<int, string> potNode = _root;

                while (value != potNode.Value)

                {

                    if (value < potNode.Value)

                    {

                        if (potNode.LNode != null)

                            potNode = potNode.LNode;

                        else

                            break;

                    }

                    else

                    {

                        if (potNode.RNode != null)

                            potNode = potNode.RNode;

                        else

                            break;

                    }

                }

                return potNode;

            }

            return null;

        }

        //根据叶子节点回溯得到最小的不平衡祖先节点

        /// <summary>

        /// 根据叶子节点回溯得到最小的不平衡祖先节点

        /// </summary>

        /// <param name="node"></param>

        /// <returns></returns>

        public TreeNode<int, string> FindTreeNodeByNode(TreeNode<int, string> node)

        {

            if (node == null)

                return null;

            TreeNode<int, string> hnode = node;

            while (hnode.Bal == 0)

            {

                if (hnode != null && hnode.HNode!=null)

                    hnode = hnode.HNode;

                else

                    break;

            }

            return hnode;

        }

        //回溯到最小不平衡点修改各个祖先的平衡因子

        /// <summary>

        /// 回溯到最小不平衡点修改各个祖先的平衡因子

        /// </summary>

        /// <param name="hn"></param>

        /// <param name="potn"></param>

        /// <param name="bacn"></param>

        /// <param name="value"></param>

        /// <param name="name"></param>

        public void AddNodeBackOper(TreeNode<int, string> hn, TreeNode<int, string> potn, int value, string name)

        {

            try

            {

                TreeNode<int, string> newNode = new TreeNode<int, string>();

                newNode.Value = value;

                newNode.Havalue = new HashSet<string>();

                newNode.Havalue.Add(name);

                newNode.Bal = 0;

                newNode.HNode = potn;

                if (value < potn.Value)

                    potn.LNode = newNode;

                else

                    potn.RNode = newNode;

                TreeNode<int, string> baNode = newNode;

                if (value < hn.Value)

                {

                    while (baNode.Value < hn.Value)

                    {

                        if (baNode.Value < baNode.HNode.Value)

                            baNode.HNode.Bal = baNode.HNode.Bal + 1;

                        else

                            baNode.HNode.Bal = baNode.HNode.Bal - 1;

                        baNode = baNode.HNode;

                    }

                }

                else

                {

                    while (baNode.Value > hn.Value)

                    {

                        if (baNode.Value < baNode.HNode.Value)

                            baNode.HNode.Bal = baNode.HNode.Bal + 1;

                        else

                            baNode.HNode.Bal = baNode.HNode.Bal - 1;

                        baNode = baNode.HNode;

                    }

                }

            }

            catch

            {

            }

        }

        //根据value和name添加节点

        /// <summary>

        /// 根据value和name添加节点

        /// </summary>

        /// <param name="value"></param>

        /// <param name="name"></param>

        public void AddNode(int value,string name)

        {

            try

            {

                TreeNode<int, string> potNode = FindTreeNodeByValue(value);//查找最接近的value值的节点

                TreeNode<int, string> hNode = FindTreeNodeByNode(potNode);//根据叶子节点回溯得到最近的不平衡祖先节点

                if (potNode != null)       //存在最接近value值的节点说明_root不是一棵空树

                {

                    TreeNode<int, string> hhNode = hNode.HNode;//最小不平衡点的父节点。

                    if (potNode.Value == value)                //存在相同value值的节点则将新的name值存入该value值对应的hash列表

                    {

                        if (!potNode.Havalue.Contains(name))

                            potNode.Havalue.Add(name);

                    }

                    else

                    {

                        TreeNode<int, string> newnode = new TreeNode<int, string>();

                        if (hNode.Bal == -1)//最近不平衡祖先节点的右子树高于左子树。

                        {

                            if (value < hNode.Value)//插入值小于不平衡祖先节点的值插入左子树无需平衡调整，只需修改各级祖先的平衡因子

                            {

                                AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子

                                return;

                            }

                            else

                            {

                                if (value > hNode.RNode.Value)//插入值大于不平衡点的右儿子的值

                                    newnode = rrAdjustment(hNode);  //rr调整

                                else//value<hNode.RNode.Value    插入值小于不平衡点的右儿子的值   

                                    newnode = rlAdjustment(hNode, value, name);//rl调整

                                hNode = newnode;            //将返回的平衡节点替换不平衡节点

                            }

                        }

                        else if (hNode.Bal == 1)//最近不平衡祖先节点的左子树高于右子树。

                        {

                            if (value > hNode.Value)//插入值大于不平衡祖先节点的值插入右子树无需平衡调整，只需修改各级祖先的平衡因子

                            {

                                AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子

                                return;

                            }

                            else

                            {

                                if (value < hNode.LNode.Value)//LL 调整

                                    newnode = llAdjustment(hNode);

                                else//value > hNode.LNode.Value//LR调整

                                    newnode = lrAdjustment(hNode, value, name);

                                hNode = newnode;

                            }

                        }

                        AddNodeBackOper(hNode, potNode, value, name);//回溯到最小不平衡点修改各个祖先的平衡因子

                        if (hhNode == null)//最近不平衡点的父节点不存在说明最近不平衡点就是根节点

                            _root = hNode;

                        else               //将最近不平衡点的父节点关联平衡调整后的子节点

                        {

                            hNode.HNode = hhNode;

                            if (hhNode.Value > hNode.Value)

                                hhNode.LNode = hNode;

                            else

                                hhNode.RNode = hNode;

                        }

                    }

                }

                else//不存在最接近value值的节点说明_root树是一棵空树

                {

                    TreeNode<int, string> newnode = new TreeNode<int, string>();

                    newnode.Bal = 0;

                    newnode.Value = value;

                    HashSet<string> has = new HashSet<string>();

                    has.Add(name);

                    newnode.Havalue = has;

                    _root = newnode;

                }

            }

            catch

            {

            }

        }

        //右右调整

        /// <summary>

        /// 右右调整

        /// </summary>

        public TreeNode<int,string> rrAdjustment(TreeNode<int, string> hnode)

        {

            try

            {

                TreeNode<int, string> AH = hnode.HNode;

                TreeNode<int, string> A = hnode;

                TreeNode<int, string> B = hnode.RNode;

                TreeNode<int, string> AL = hnode.LNode;

                TreeNode<int, string> BL = hnode.RNode.LNode;

                A.RNode = BL;

                B.LNode = A;

                B.HNode = AH;

                A.HNode = B;

                A.Bal = 0;

                B.Bal = 1;

                return B;

            }

            catch

            {

                return new TreeNode<int,string>();

            }

        }

        //左左调整

        /// <summary>

        /// 左左调整

        /// </summary>

        public TreeNode<int,string> llAdjustment(TreeNode<int,string> hnode)

        {

            try

            {

                TreeNode<int, string> BH = hnode.HNode;

                TreeNode<int, string> B = hnode;

                TreeNode<int, string> A = hnode.LNode;

                TreeNode<int, string> AR = hnode.LNode.RNode;

                TreeNode<int, string> BR = hnode.RNode;

                B.LNode = AR;

                A.RNode = B;

                A.HNode = BH;

                B.HNode = A;

                B.Bal = 0;

                A.Bal = -1;

                return A;

            }

            catch

            {

                return new TreeNode<int, string>();

            }

        }

        //左右调整

        /// <summary>

        /// 左右调整

        /// </summary>

        /// <param name="hnode">//传入的最近不平衡点</param>

        /// <param name="value">新节点的key值</param>

        /// <param name="name">新节点的key值新增的对应的hash列表值</param>

        /// <returns></returns>

        public TreeNode<int, string> lrAdjustment(TreeNode<int, string> hnode,int value,string name)

        {

            try

            {

                TreeNode<int, string> CH = hnode.HNode;

                TreeNode<int, string> C = hnode;//最近不平衡点

                TreeNode<int, string> A = hnode.LNode;//最近不平衡点的左子树

                TreeNode<int, string> B = hnode.LNode.RNode;//最近不平衡点的左子树的右子树

                if (B != null)     //最近不平衡点的左子树的右子树不为空

                {

                    TreeNode<int, string> BL = B.LNode;

                    TreeNode<int, string> BR = B.RNode;

                    if (BL != null)

                    {

                        A.RNode = BL;

                        BL.HNode = A;

                    }

                    if (BR != null)

                    {

                        C.LNode = BR;

                        BR.HNode = C;

                    }

                }

                else               //最近不平衡点的左子树的右子树为空 则将新的节点值作为不平衡节点的右子树

                {

                    B = new TreeNode<int, string>();

                    B.Value = value;

                    HashSet<string> has = new HashSet<string>();

                    has.Add(name);

                    B.Havalue = has;

                }

                C.LNode = B.RNode;

                A.RNode = B.LNode;

                B.LNode = A;

                B.RNode = C;

                A.HNode = B;

                C.HNode = B;

                int dif = value - B.Value > 0 ? 1 : (value - B.Value<0 ? -1 : 0) ;

                switch (dif)

                {

                    case 1:

                        C.Bal = 0;A.Bal = 1;break;

                    case -1:

                        C.Bal = -1;A.Bal = 0;break;

                    default:

                        C.Bal = 0;A.Bal = 0;break;

                }

                return B;

            }

            catch

            {

                return new TreeNode<int, string>();

            }

        }

        //右左调整

        /// <summary>

        /// 右左调整

        /// </summary>

        public TreeNode<int, string> rlAdjustment(TreeNode<int, string> hnode,int value,string name)

        {

            try

            {

                TreeNode<int, string> CH = hnode.HNode;//最近不平衡节点的父节点

                TreeNode<int, string> C = hnode;       //最近不平衡节点

                TreeNode<int, string> A = hnode.RNode;  //最近不平衡节点的右子树

                TreeNode<int, string> B = hnode.RNode.LNode;//最近不平衡节点的右儿子的左子树

                if (B != null)

                {

                    TreeNode<int, string> BL = B.LNode;

                    TreeNode<int, string> BR = B.RNode;

                    if (BR != null)

                    {

                        A.LNode = BR;

                        BR.HNode = A;

                    }

                    if (BL != null)

                    {

                        C.RNode = BL;

                        BL.HNode = C;

                    }

                }

                else

                {

                    B = new TreeNode<int, string>();

                    B.Value = value;

                    HashSet<string> has = new HashSet<string>();

                    has.Add(name);

                    B.Havalue = has;

                }

                C.RNode = B.LNode;

                A.LNode = B.RNode;

                B.LNode = C;

                B.RNode = A;

                A.HNode = B;

                C.HNode = B;

                int dif = value - B.Value > 0 ? 1 : (value - B.Value < 0 ? -1 : 0);

                switch (dif)

                {

                    case 1:

                        C.Bal = 0;A.Bal=-1;break;

                    case -1:

                        C.Bal = 1;A.Bal=0;break;

                    default:

                        C.Bal = 0;A.Bal=0;break;

                }

                return B;

            }

            catch

            {

                return new TreeNode<int, string>();

            }

        }

        public void  ReadAVLTreeOper()

        {

        }

        #region//草稿

        /// <summary>

        /// 向平衡二叉树添加结点。

        /// </summary>

        /// <param name="Id"></param>

        /// <param name="name"></param>

        public void Add(int Id, string name)

        {

            if (null != _root)

            {

                TreeNode<int, string> potNode = _root;

                TreeNode<int, string> hnode = null;

                TreeNode<int, string> baNode = null;

                while (Id != potNode.Value)

                {

                    if (Id < potNode.Value)

                    {

                        if (potNode.LNode!=null)

                            potNode = potNode.LNode;

                        else

                            break;

                    }

                    else

                    {

                        if (potNode.RNode!=null)

                            potNode = potNode.RNode;

                        else

                            break;

                    }

                }

                if (potNode.Value == Id)

                {

                    if (!potNode.Havalue.Contains(name))

                        potNode.Havalue.Add(name);

                }

                else//没有找到值为Id的下层节点。

                {

                    while (hnode.Bal == 0)

                    {

                        if (null != hnode.HNode)

                            hnode = hnode.HNode;

                        else

                            break;

                    }

                    if (hnode!= null)

                    {

                        TreeNode<int, string> newNode = new TreeNode<int, string>();

                        newNode.Value = Id;

                        newNode.Bal = 0;

                        newNode.Havalue = new HashSet<string>();

                        newNode.Havalue.Add(name);

                        newNode.HNode = potNode;

                        if (hnode.Bal == -1)

                        {

                            if (Id < hnode.Value)

                            {

                                if (Id >potNode.Value)

                                    potNode.RNode = newNode;

                                else

                                    potNode.LNode = newNode;

                                baNode = newNode;

                                while (baNode.Value<hnode.Value)

                                {

                                    if (baNode.Value < baNode.HNode.Value)

                                        baNode.HNode.Bal = baNode.HNode.Bal + 1;

                                    else

                                        baNode.HNode.Bal = baNode.HNode.Bal - 1;

                                    baNode = baNode.HNode;

                                } 

                            }

                            else

                            {

                                if (Id > hnode.RNode.Value)//rr调整

                                {

                                    TreeNode<int, string> AH = hnode.HNode;

                                    TreeNode<int, string> A = hnode;

                                    TreeNode<int,string> B=hnode.RNode;

                                    TreeNode<int, string> AL = hnode.LNode;

                                    TreeNode<int, string> BL = hnode.RNode.LNode;

                                    TreeNode<int, string> BR = hnode.RNode.RNode;

                                    A.RNode = BL;

                                    A.HNode = B;

                                    B.HNode = AH;

                                    B.LNode = A;

                                    if (B.Value < AH.Value)

                                        AH.LNode = B;

                                    else

                                        AH.RNode = B;

                                }

                                else //（Id <hnode.RNode.Value）rl调整

                                {

                                }

                            }

                        }

                        else//hnode.Bal == 1

                        {

                            if (Id > hnode.Value)

                            {

                                if (Id > potNode.Value)

                                    potNode.RNode = newNode;

                                else

                                    potNode.LNode = newNode;

                                baNode = newNode;

                                while (baNode.Value > hnode.Value)

                                {

                                    if (baNode.Value < baNode.HNode.Value)

                                        baNode.HNode.Bal = baNode.HNode.Bal + 1;

                                    else

                                        baNode.HNode.Bal = baNode.HNode.Bal - 1;

                                    baNode = baNode.HNode;

                                } 

                            }

                            else

                            {

                                if (Id > hnode.LNode.Value)//lr调整

                                {

                                }

                                else //（Id <hnode.LNode.Value）ll调整

                                {

                                }

                            }

                        }

                    }

                }

            }

        }

        #endregion

    }

}

//AvL测试入口

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using AVLTreeTool;

namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {

            AddNodes();

            AddNode();

            //test();

        }

        public static void AddNode()

        {

            AVLTreeOPer client = new AVLTreeOPer();

            client.AddNode(9,"hujiapeng");

        }

        public static void AddNodes()

        {

            AVLTreeOPer client = new AVLTreeOPer();

            Random ra = new Random();

            for (int i = 30; i >= 0; i--)

            {

                int rdt = ra.Next(100);

                client.AddNode(rdt, "hujiapeng" + rdt);

                //client.AddNode(i, "hujiapeng" + i);

                if (i == 1)

                {

                    continue;

                }

            }

        }

    }

}

转载于:https://www.cnblogs.com/hujiapeng2012/archive/2012/07/06/2579611.html