二叉平衡树

二叉排序树可能出现的问题：左子树过高或右子树过高，为了解决这种情况采用二叉平衡树树

二叉平衡树：可以看成将二叉排序树高的一边子树“往上提了一下”，即将该边子树的第一个从上至下的第一个结点作为新的根节点

原来的根节点放到另一边补充矮的子树的高度了。

当然还有特殊情况：

如果当前结点的右子树的左子树的高度大于右子树的右子树高度，先对它的右子树进行右旋转，然后再对当前结点进行左旋转，或者左子树的左子树高度大于它的右子树高度，先对它的左子树进行左旋转，然后再对当前结点进行右旋转，即双边排序

其代码就是在二叉排序树的代码上加上了一些改进，贴上改进代码：

 //左旋转
        public void leftRotate()
        {
            //创建一个新结点，值为当前根节点的值
            Node newNode = new Node(value);
            //把新的结点的左子树设置为当前结点的左子树
            newNode.left = left;
            //把新的结点的左子树设置为当前结点的左子树
            newNode.right = right.left;
            //当前结点的值替换成右子结点的值
            value = right.value;
            //把当前结点的右子树设置成当前结点的右子结点的右子结点（跳过去）
            right = right.right;
            //把当前结点的左子结点设置成新结点
            left = newNode;
        }

        //右旋转
        public void rightRotata()
        {
            //创建一个新结点，值为当前根节点的值
            Node newNode = new Node(value);
            //把新的结点的右子树设置为当前结点的右子树
            newNode.right = right;
            //把新的结点的左子树设置为当前结点的右子树
            newNode.left = left.right;
            //当前结点的值替换成左子结点的值
            value = left.value;
            //把当前结点的左子树设置成当前结点的左子结点的左子结点（跳过去）
            left = left.left;
            //把当前结点的右子结点设置成新结点
            right = newNode;
        }

  public void add(Node node)
        {
            if (node == null)
            {
                return;
            }
            //判断传入的结点值和当前子树根结点的关系
            //当前结点的值大于传入的值
            if (node.value < this.value)
            {
                //如果左子树为空
                if (this.left == null)
                {
                    this.left = node;
                }
                else
                //如果左子树不为空
                {
                    //向左递归
                    this.left.add(node);
                }
            }
            else//传入的值大于等于当前结点的值
            {
                //右子树为空
                if (this.right == null)
                {
                    this.right = node;
                }
                //右子树不为空
                else
                {
                    //向右递归
                    this.right.add(node);
                }
            }
            //添加完一个结点后，（右子树高度-左子树高度）>1 左旋转
            if (rightHeight() - leftHeight() > 1)
            {
                //如果当前结点的右子树的左子树的高度大于右子树的右子树高度
                //先对它的右子树进行右旋转，然后再对当前结点进行左旋转
                if (right != null&&right.leftHeight()>right.rightHeight())
                {
                    //先对右子结点进行右旋转
                    right.rightRotata();
                    leftRotate();
                }
                else
                {
                    leftRotate();
                }
                return;
            }
            //添加完一个结点后，（左子树高度 - 右子树高度）> 1 右旋转
            if (leftHeight() - rightHeight() > 1)
            {
                //左子树的左子树高度大于它的右子树高度
                if (left != null && left.rightHeight() > leftHeight())
                {
                    //对当前结点的左节点进行左旋转
                    left.leftRotate();
                    //对当前结点进行右旋转
                    rightHeight();
                }
                else
                {
                    //直接右旋转
                    rightHeight();
                }
            }
        }