平衡二叉树

平衡二叉树又叫AVL树，首先它是一颗二叉搜索树，其次要求它的每个节点的左右子树高度差的绝对值不超过一。

平衡二叉树举例

平衡二叉树

分析平衡二叉树

平衡因子

将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子。

上图为例，根节点5的左子树高度为2，右子树高度为2，平衡因子（以后简称b）为2-2=0；处于平衡状态。
节点3的左子树高度为1，右子树高度为1，b=1-1=1；处于平衡状态

去掉节点4

可以看到去掉节点四的情况下，节点3的左子树高度为1，右子树高度为0，b=1-0=1；处于平衡状态。

插入节点1

插入节点1的情况下，节点3的左子树高度为2，右子树高度为0，b=2-0=2；处于非平衡状态，这个时候就需要进行平衡。

注意

如果一棵平衡二叉树在插入或者删除一个节点之后处于不平衡状态，那么经过一次调整之后一定会处于平衡状态

几种不平衡的情况

先定义Node节点

和上一次二叉搜索树的定义一样

    public class Node<T>
    {
        public T Data;
        public int Index;
        public Node<T> LeftChild;
        public Node<T> RightChild;
        public Node<T> Parent;

        public int Height;

        public bool Larger(int index)
        {
            if (Index == index)
                throw new Exception("index exist:" + index);
            return Index > index;
        }
    }

LL型平衡调整

LL型简单情况

上图是LL型的最简单情况，根节点是3，连续插入2和1之后，3处于不平衡状态，此时将2作为根节点，3作其右子树，1不动，处于平衡状态。

LL复杂情况

上图红圈处插入一个比1小的数，节点4处于不平衡状态，此时将2的右子树作为4的左子树。下面是LL平衡调整的代码

      private Node<T> LLRotate(Node<T> node)
      {
          var parent = node.Parent;
          var left = node.LeftChild;
          var leftRight = left.RightChild;

          node.Parent = left;
          left.Parent = parent;
          node.LeftChild = left.RightChild;
          left.RightChild = node;

          if (leftRight != null)
              leftRight.Parent = node;

          if (parent != null)
          {
              if (node.Index < parent.Index)
                  parent.LeftChild = left;
              else
                  parent.RightChild = left;
          }

          SetHeight(node);
          SetHeight(left);

          return left;
      }

RR型平衡调整

RR简单情况

上图是RR型的简单情况，根节点是3，连续插入4和5之后，3处于不平衡状态，此时将4作为根节点，3作其左子树，5不动，处于平衡状态。

RR复杂情况

RR复杂情况和LL差不多。将6的左子树赋值给3的右子树。下面是RR型平衡调整的代码

      private Node<T> RRRotate(Node<T> node)
      {
          var parent = node.Parent;
          var right = node.RightChild;
          var rightLeft = right.LeftChild;

          node.Parent = right;
          right.Parent = parent;
          node.RightChild = right.LeftChild;
          right.LeftChild = node;

          if (rightLeft != null) 
              rightLeft.Parent = node;

          if (parent != null)
          {
              if (node.Index < parent.Index)
                  parent.LeftChild = right;
              else
                  parent.RightChild = right;
          }

          SetHeight(node);
          SetHeight(right);

          return right;
      }

LR调整

LR简单情况

LR调整分为两步，先对节点2进行RR调整，在对节点4进行LL型调整，便可达到平衡。

RL调整

RL简单情况

和LR调整类似，分两步，先对节点4进行LL调整，在对节点2进行RR调整，达到平衡状态。

这两种的复杂情况我就不画了，有兴趣大家可以自己试试

平衡二叉树的插入和删除

说了这么多，终于要讲到关键性操作了，插入与删除。
先说一下基本思路，插入和二叉搜索树一样，小的找左子树，大的找右子树，一直找到一个为空的，把节点插入进去，然后从当前节点开始平衡。
删除分为几种情况
1、要删除的节点无子节点，直接删除当前节点。
2、有一个子节点，交换要删除节点和子节点的数据，删除子节点。
3、有两个子节点，判断当前节点左右子树哪个高，左边高，在左边找最大的，右边高，在右边找最小的，交换两个节点的数据，回到情况1。
删除完成之后总是从真正删除节点的父节点开始平衡。

下面是平衡二叉树的完整代码，关键部分都给出了注释，有问题请留言或者QQ412484723（初步测试代码是对的，可能也有问题）

using System;

namespace BTree
{
  public class Node<T>
  {
      public T Data;
      public int Index;
      public Node<T> LeftChild;
      public Node<T> RightChild;
      public Node<T> Parent;

      public int Height;

      public bool Larger(int index)
      {
          if (Index == index)
              throw new Exception("index exist:" + index);
          return Index > index;
      }
  }

  class BalanceTree<T>
  {
      private Node<T> Root;

      public void CreatBalanceTree(Node<T> data)
      {
          if (Root != null)
              throw new Exception("can't creat,root exist");

          Root = new Node<T>();
          Root = data;
      }


      private Node<T> LLRotate(Node<T> node)
      {
          var parent = node.Parent;
          var left = node.LeftChild;
          var leftRight = left.RightChild;

          node.Parent = left;
          left.Parent = parent;
          node.LeftChild = left.RightChild;
          left.RightChild = node;

          if (leftRight != null)
              leftRight.Parent = node;

          if (parent != null)
          {
              if (node.Index < parent.Index)
                  parent.LeftChild = left;
              else
                  parent.RightChild = left;
          }

          SetHeight(node);
          SetHeight(left);

          return left;
      }

      private Node<T> RRRotate(Node<T> node)
      {
          var parent = node.Parent;
          var right = node.RightChild;
          var rightLeft = right.LeftChild;

          node.Parent = right;
          right.Parent = parent;
          node.RightChild = right.LeftChild;
          right.LeftChild = node;

          if (rightLeft != null) 
              rightLeft.Parent = node;

          if (parent != null)
          {
              if (node.Index < parent.Index)
                  parent.LeftChild = right;
              else
                  parent.RightChild = right;
          }

          SetHeight(node);
          SetHeight(right);

          return right;
      }

      public Node<T> Insert(Node<T> node)
      {
          var curNode = InsertNode(node);

          curNode.Height = 1;
          Balance(node);

          return node;
      }

      /// <summary>
      /// 非递归平衡节点。跳出循环的条件有两个，第一个是遍历到根节点发现都平衡就跳出，第二个是发现有不平衡的节点，平衡之后跳出。
      /// </summary>
      /// <param name="node"></param>
      private void Balance(Node<T> node)
      {
          var curNode = node;

          while (true)
          {
              if (curNode.Parent == null)
              {
                  Root = curNode;
                  break;
              }

              SetHeight(curNode.Parent);

              var b = GetBanlace(curNode.Parent);

              if (MathF.Abs(b) < 2)
              {
                  curNode = curNode.Parent;
                  continue;
              }

              Node<T> finalNode = null;

              if (b > 1)
              {
                  var b1 = GetBanlace(curNode.Parent.LeftChild);

                  if (b1 >= 0)
                      finalNode = LLRotate(curNode.Parent);  //LL
                  else
                  {
                      var n = RRRotate(curNode.Parent.LeftChild);  //LR
                      finalNode = LLRotate(n.Parent);
                  }
              }

              if (b < -1)
              {
                  var b1 = GetBanlace(curNode.Parent.RightChild);

                  if (b1 <= 0)
                      finalNode = RRRotate(curNode.Parent);  //RR
                  else
                  {
                      var n = LLRotate(curNode.Parent.RightChild); //RL
                      finalNode = RRRotate(n.Parent);
                  }
              }

              if (finalNode != null)
              {
                  if (finalNode.Parent == null)
                      Root = finalNode;
                  break;
              }
          }
      }

      private Node<T> InsertNode(Node<T> node)
      {
          if (Root == null)
              throw new Exception("sort tree does't exist");

          Node<T> temp;

          temp = Root;
          while (true)
          {

              if (node.Larger(temp.Index))
              {
                  if (temp.RightChild == null)
                  {
                      temp.RightChild = node;
                      node.Parent = temp;
                      return node;
                  }
                  else
                  {
                      temp = temp.RightChild;
                  }
              }
              else
              {
                  if (temp.LeftChild == null)
                  {
                      temp.LeftChild = node;
                      node.Parent = temp;
                      return node;
                  }
                  else
                  {
                      temp = temp.LeftChild;
                  }
              }
          }
      }

      public Node<T> FindNode(int index)
      {
          Node<T> node = null;

          var curNode = Root;

          while(true)
          {
              if(index==curNode.Index)
              {
                  node = curNode;
                  break;
              }

              if(index>curNode.Index)
              {
                  if (curNode.RightChild == null)
                      throw new Exception("can't find this node :" + index);

                  curNode = curNode.RightChild;
                  continue;
              }

              if (index < curNode.Index)
              {
                  if (curNode.LeftChild == null)
                      throw new Exception("can't find this node :" + index);

                  curNode = curNode.LeftChild;
                  continue;
              }
          }
          if (node == null)
              throw new Exception("can't find the node :" + index);

          return node;
      }

      public void DeleteNode(Node<T> node)
      {
          DeleteNodeByIndex(node.Index);
      }

      public void DeleteNodeByIndex(int index)
      {
          if (index == Root.Index)
              throw new Exception("can't delete root node");

          var curNode = FindNode(index);

          if (curNode.LeftChild == null && curNode.RightChild == null)//无子节点直接删除，
          {
              DeleteLeafNode(curNode);
          }

          if (curNode.LeftChild == null && curNode.RightChild != null)//有右子树，交换删除节点和其右子树的数据，删除右子树
          {
              var deleteNode = Swap(curNode, curNode.RightChild);
              DeleteLeafNode(deleteNode);
          }

          if (curNode.LeftChild != null && curNode.RightChild == null)//有左子树，交换删除节点和其左子树的数据，删除左子树
          {
              var deleteNode = Swap(curNode, curNode.LeftChild);
              DeleteLeafNode(deleteNode);
          }

          if (curNode.LeftChild != null && curNode.RightChild != null)//左右子树都存在
          {
              var b = GetBanlace(curNode);//判断当前节点的b

              if (b >= 0)
              {
                  var max = FindMax(curNode.LeftChild);//左边高，在左边找最大的

                  var swapNode = Swap(curNode, max);

                  if(swapNode.LeftChild!=null)
                  {
                      var deleteNode = Swap(curNode, swapNode);
                      DeleteLeafNode(deleteNode);
                  }
                  else
                  {
                      DeleteLeafNode(swapNode);
                  }
              }
              else
              {
                  var min = FindMin(curNode.RightChild);//右边高，在右边找最小的

                  var swapNode = Swap(curNode, min);

                  if (swapNode.RightChild != null)
                  {
                      var deleteNode = Swap(curNode, swapNode);
                      DeleteLeafNode(deleteNode);
                  }
                  else
                  {
                      DeleteLeafNode(swapNode);
                  }
              }
          }
      }

      /// <summary>
      /// 删除叶子节点，每次删除之后从父节点开始平衡
      /// </summary>
      /// <param name="node"></param>
      private void DeleteLeafNode(Node<T> node)
      {
          var parent = node.Parent;

          if (node == parent.LeftChild)
              parent.LeftChild = null;
          else
              parent.RightChild = null;
          
          SetHeight(parent);
          Balance(parent);
      }

      private Node<T> Swap(Node<T> node1,Node<T> node2)
      {
          var index = node2.Index;
          var data = node2.Data;

          node2.Index = node1.Index;
          node2.Data = node1.Data;

          node1.Index = index;
          node1.Data = data;

          return node2;
      }

      public Node<T> FindMin(Node<T> node)
      {
          var curNode = node;

          while(true)
          {
              if (curNode.LeftChild != null)
                  curNode = curNode.LeftChild;
              else
                  return curNode;
          }
      }

      public Node<T> FindMax(Node<T> node)
      {
          var curNode = node;

          while (true)
          {
              if (curNode.RightChild != null)
                  curNode = curNode.RightChild;
              else
                  return curNode;
          }
      }

      public Node<T> GetRoot()
      {
          return Root;
      }

      private int GetBanlace(Node<T> node)
      {
          return GetHeight(node.LeftChild) - GetHeight(node.RightChild);
      }

      private int GetHeight(Node<T> node)
      {
          return node == null ? 0 : node.Height;
      }

      private void SetHeight(Node<T> node)
      {
          node.Height = (int)MathF.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)) + 1;
      }

      private void InOrder(Node<T> root)
      {
          if (root != null)
          {
              Console.WriteLine(string.Format("index:{0},data:{1}", root.Index, root.Data));
              InOrder(root.LeftChild);
              InOrder(root.RightChild);
          }
      }
      public void InOrder()
      {
          InOrder(Root);
      }

  }
}