平衡二叉树

本文简要的实现了平衡二叉树的插入、删除操作。为了更新节点的平衡度，新增了parent指针。

简介

这个平衡二叉树使用C语言实现的，因为写的匆忙，加上智商捉急，可能某些地方没有考虑周全，会有一点小bug，尚在排查中。本算法能基本的实现平衡二叉树的插入、删除操作，有关平衡二叉树的原理及实现，参考AVL树(一)之 图文解析 和 C语言的实现。这位博主讲解的非常详细！！虽然他给的代码中有一些错误，但从他的博文中，我受益良多，并且重写了这个AVL树，在此表示感谢 ^_ .

数据结构

这里的parent指针很重要，它可以在平衡二叉树删除算法的调整过程中，起着很大的作用。有一点需要注明的是，那位博主的删除算法有误，选用的数据结构也不太合理。。

typedef int DataType;

typedef struct Node {
         DataType value;
         int depth;      // 保存节点在树中的深度，没有孩子，深度为1，负责深度为左右孩子最大深度值加1
         struct Node * left;
         struct Node * right;
         struct Node * parent;
} Node, *Tree;

基本思想

插入过程
我就不想说了，无非LL、LR、RL、RR型的旋转操作。想在这里记录一下：

删除算法的过程

1、若该节点有左右孩子
那么就用它的后继孩子节点替换该节点。假如本来删除的节点为node,它的左右孩子均非空，这时就用它的后继节点successor作为要删除的节点，即将successor节点的值赋给node，再删掉successor节点，因为这样需要调整的节点会少。

2、若该节点只有1个或0个孩子
直接删掉它。

关于调整过程：
对删除节点的父节点开始调整，更新其depth，并且向根节点开始迭代。计算每个父节点的左右子树的平衡差diff_depth，若为2则启动调整算法。

调整算法

基于四个调整操作，即LL、LR、RL、RR旋转。具体怎么旋转，参见那篇博文，灰常详细。

平衡二叉树C实现

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct Node {
  DataType value;
  int depth;              // the position in this tree
  struct Node * left;
  struct Node * right;
  struct Node * parent;
} Node, *Tree;

int get_depth(Node * node) {
  if(node == NULL) {
    return 0;
  } else if(node->left == NULL && node ->right == NULL) {
    return 1;
  } else if(node->left == NULL && node->right != NULL) {
    return (node->right->depth + 1);
  } else if(node->left != NULL && node ->right == NULL) {
    return ( node->left->depth + 1 );
  } else {
    return (max( node->left->depth, node->right->depth ) + 1) ;
  }
}

int diff_depth( Tree T ) {
  if(T->left == NULL && T->right != NULL) {
    return T->right->depth;
  }
  else if(T->left != NULL && T->right == NULL) {
    return T->left->depth;
  }
  else if(T->left == NULL && T->right == NULL) {
    return 0;
  } else {
    if(T->left->depth > T->right->depth) {
      return T->left->depth - T->right->    depth;
    } else {
      return T->right->depth - T->left->depth;
    }
 }
}

int max(int a, int b) {
 return a > b ? a:b;
}

Node * get_node(Tree T, DataType value) {
  while(T != NULL) {
          if(value == T->value) {
            return T;
          }
          if(value > T->value) {
            T = T->right;
          } else {
            T = T->left;
          }
  }
  printf("get_node : not find this node < value : %d >\n", value );
  return NULL;
}

Node * get_successor(Tree T, Node * x) {
  if(x->right != NULL) {
      Node * p = x->right;
      while ( p->left != NULL ) {
              p = p->left;
      }
      return p;
  } else {
      Node * parent = x->parent;
      while ( parent != NULL && x->value > parent->value ) {
              parent = parent->parent;
      }
      return parent;
  }
}

Tree left_left_rotate(Tree T) {
  Node * node;

  node = T->left;
  node->parent = T->parent;
  T->left = node->right;
  T->parent = node;
  node->right = T;

  T->depth = get_depth( T );
  node->depth = get_depth( node );

  return node;    // new root node
}

Tree right_right_rotate(Tree T) {
  Node * node;

  node = T->right;
  node->parent = T->parent;
  T->right = node->left;
  T->parent = node;
  node->left = T;

  T->depth = get_depth( T );
  node->depth = get_depth( node );

  return node;    // new root node
}

Tree left_right_rotate(Tree T) {
  T->left = right_right_rotate( T->left );
  return left_left_rotate( T );
}

Tree right_left_rotate(Tree T) {
  T->right = left_left_rotate( T->right );
  return right_right_rotate( T );
}

Tree insert_fix_up(Node * node) {
  Node * father = node->parent;
  Node * temp_node = NULL;
  Node * root = NULL;

  if (father == NULL) return node ;
  if (father->parent == NULL) return father;
  while (father->parent != NULL) {
      if (diff_depth( father->parent ) == 2) {
          temp_node = father->parent->parent;
          if(father == father->parent->left) {
              if (node == node->parent->left) {
                  if ( temp_node == NULL ) left_left_rotate( father->parent );
                  else temp_node->left = left_left_rotate( father->parent );      // LL 调整
              } else {
                  if ( temp_node == NULL ) left_right_rotate( father->parent );
                  else temp_node->left = left_right_rotate( father->parent );             // LR 调整
              }
          }
          else {      // 在右子树中调整
              if ( node == node->parent->left ) {
                  if ( temp_node == NULL ) right_left_rotate( father->parent );
                  temp_node->right = right_left_rotate( father->parent );   // RL 调整
              }
              else {
                  if ( temp_node == NULL ) right_right_rotate( father->parent );
                  else temp_node->right = right_right_rotate( father->parent );   // RR 调整
              }
      }
      break;
    }
      father = father->parent;
      node = node->parent;
  }
  while ( temp_node != NULL ) {            //  更新调整后的深度
      temp_node->depth = get_depth( temp_node );
      temp_node = temp_node->parent;
  }
  root = node ;      // 从新插入的节点往上找root节点
  while( root->parent != NULL )
      root = root->parent;
  return root ;
}

Tree insert_node( Tree * T, DataType value )
{
        Node * parent = *T ;
        Node * node = NULL ;

        if( *T == NULL )
        {
                *T = ( Tree )malloc( sizeof( Node ) );

                if( *T == NULL )
                {
                        printf(" insert_node : error to create a node < value : %d >\n", value );

                        return *T ;
                }

                (*T)->left = NULL;
                (*T)->right = NULL;
                (*T)->depth = 1;
                (*T)->parent = NULL;
                (*T)->value = value;

                return *T ;
        }

        while( *T != NULL )
        {
                parent = *T;           // 得到要插入节点的父节点位置

                if ( value > (*T)->value ) *T = (*T)->right;

                else if ( value < (*T)->value ) *T = (*T)->left;

                else
                {
                        printf(" this Node: < value = %d > has existed!\n ", value );
                        return *T ;
                }
        }

        node = ( Node * )malloc( sizeof( Node ) );

        if( node == NULL )
        {
                printf(" insert_node : error to create a node < value : %d >\n", value );

                return *T ;
        }

        if ( value > parent->value )
        {
                parent->right = node;
        }
        else
        {
                parent->left = node;
        }

        node->left = NULL;
        node->right = NULL;
        node->parent = parent;
        node->depth = 1;
        node->value = value;

        while( parent != NULL )
        {
                parent->depth = get_depth( parent );
                parent = parent->parent;
        }


        *T = insert_fix_up( node );

        return *T ;
}

Tree delete_fix_up( Node * node )
{
        Node * child = NULL;

        if ( node->left != NULL )
        {
                child = node->left;

                if ( child->left != NULL )   // LL型调整
                {
                        return left_left_rotate( node );
                }
                else    // LR型调整
                {
                        return left_right_rotate( node );
                }
        }
        else
        {
                child = node->right;

                if ( child->left != NULL )   // RL型调整
                {
                        return right_left_rotate( node );
                }
                else    // RR型调整
                {
                        return right_right_rotate( node );
                }
        }
}

Tree delete_node( Tree * T, DataType value )
{
        Node * node = NULL;
        Node * delete_node = NULL;
        Node * father = NULL;

        if ( *T == NULL )
        {
                printf("Tree is NULL !!\n");
                return NULL;
        }

        node = get_node( *T, value );

        if ( node->left != NULL && node->right != NULL )
        {
                delete_node = get_successor( *T, node );     // 用被删的后继节点取代要删的节点

                node->value = delete_node->value;

                if ( delete_node->parent == node )    //后继节点就是它的右孩子，因为它的右子树没有左孩子
                {
                        if ( delete_node->right != NULL )
                        {
                                node->right = delete_node->right;
                                delete_node->right->parent = node;
                        }
                        else
                        {
                                node->right = NULL;
                        }

                        //node->depth = get_depth( node );
                }
                else      // 右子树有左孩子,一定是叶子节点，直接删掉
                {
                        delete_node->parent->left = NULL;
                }
        }
        else       //  要删除的节点只要一个字节点，或者没有字节点的情况
        {
                delete_node = node;
                father = delete_node->parent;

                if ( father != NULL )
                {
                        if ( father->left == delete_node )     // 在父节点的左子树上
                        {
                                if ( delete_node->left != NULL )   // 被删节点有左孩子
                                {
                                        father->left = delete_node->left;
                                        delete_node->left->parent = father;
                                }
                                else if ( delete_node->right != NULL )
                                {
                                        father->left = delete_node->right;
                                        delete_node->right->parent = father;
                                }
                                else
                                {
                                        father->left = NULL;
                                }
                        }
                        else     // 在父节点的右子树上
                        {
                                if ( delete_node->left != NULL )
                                {
                                        father->right = delete_node->left;
                                        delete_node->left->parent = father;
                                }
                                else if ( delete_node->right != NULL )
                                {
                                        father->right = delete_node->right;
                                        delete_node->right->parent = father;
                                }
                                else
                                {
                                        father->right = NULL;
                                }
                        }
                }
                else   // delete_node的父节点位NULL，说明此时删除的是根节点，又因为delete_node == node说明此时根节点只有一个子节点
                {
                        if ( delete_node->left != NULL )
                        {
                                *T = delete_node->left;
                        }
                        else if ( delete_node->right != NULL )
                        {
                                *T = delete_node->right;
                        }
                        else
                        {
                                *T = NULL;
                        }

                        goto end;
                }
        }


        father = delete_node->parent;    // 从这里开始，需要重新计算深度

        while( father != NULL )
        {
                *T = father;
                father->depth = get_depth( father );

                if ( diff_depth( father ) == 2 )
                {
                        Node * temp = father->parent;

                        if ( temp != NULL )
                        {
                                if ( temp->left == father )
                                {
                                        temp->left = delete_fix_up( father );
                                }
                                else
                                {
                                        temp->right = delete_fix_up( father );
                                }

                                father = temp;    // 继续向上调整
                                continue;
                        }
                        else
                        {
                                *T = delete_fix_up( father );   // 已调整到最上层
                                break;
                        }
                }

                father = father->parent;
        }

end:
        free( delete_node );

        return *T;
}

void mid_traversal( Tree T )
{
        if( T != NULL )
        {
                mid_traversal( T->left );

                printf(" value : %d , depth : %d \n", T->value, T->depth );

                mid_traversal( T->right );
        }
}

int main()
{
        Tree T = NULL;

        insert_node( &T, 3 );
        insert_node( &T, 2 );
        insert_node( &T, 1 );
        insert_node( &T, 4 );
        insert_node( &T, 5 );
        insert_node( &T, 6 );
        insert_node( &T, 7 );

        printf("------------orignal binary tree : --------\n");
        mid_traversal( T );
#if 1
        printf("\n-------delete node < value : %d >\n", 7 );
        delete_node( &T, 7 );
        mid_traversal( T );

        printf("\n-------delete node < value : %d >\n", 6 );
        delete_node( &T, 6 );
        mid_traversal( T );

        printf("\n-------delete node < value : %d >\n", 5 );
        delete_node( &T, 5 );
        mid_traversal( T );

        printf("\n-------delete node < value : %d >\n", 4 );
        delete_node( &T, 4 );
        mid_traversal( T );

        printf("\n-------delete node < value : %d >\n", 3 );
        delete_node( &T, 3 );
        mid_traversal( T );

        printf("\n-------delete node < value : %d >\n", 2 );
        delete_node( &T, 2 );
        mid_traversal( T );

#endif
        printf("\n------------ over -------------------\n");

        return 0;
}

运行结果

总结

理论与实践结合真的很重要，从书本上看这些算法没什么难的，自己动手写了一遍却被虐成了狗，同时也深深的敬佩提出这些算法的大牛们，佩服遇到问题时这么巧妙、这么机智的解决。

还有一点是，在于指针打交道的过程中，遇到段错误真是再平常也不过了。GDB真是一个你用了就会爱上它的好东西，解决段错误真是一大利器 ^_ 。