二叉树的实现

平衡二叉树的实现

       平衡二叉树需要树节点的左子树和右子树高度差不大于等于2，所有普通的二叉树在插入节点后，需要更新父节点的高度，同时递归父节点及其以上的树结构，更新节点高度，判断节点的左子树和右子树的高度差，如果等于2，则需要平衡当前节点（通过左旋，右旋操作），如果等于1，则继续更新当前节点的高度，递归它的父节点，直到节点为根节点。

节点的左旋操作和右旋操作在红黑树中已经实现，此处直接引用代码：

右旋：

1. node* rightRotate(node *target){
   
2.    node *left=target->left;
   
3.    node *grandNode=target->parent;
   
4.    if(grandNode!=NULL){
   
5.         left->parent=grandNode;
   
6.         if(target==grandNode->left)
   
7.              grandNode->left=left;
   
8.         else
   
9.              grandNode->right=left;
   
10.    }
    
11.    node *move=left->right;
    
12.    left->parent=target->parent;
    
13.    target->parent=left;
    
14.    left->right=target;
    
15.    target->left=move;
    
16.    if(move!=NULL)
    
17.        move->parent=target;
    
18.    if(target==root){
    
19.        root=left;
    
20.    }
    
21.    target->height=max(height(target->left),height(target->right))+1;
    
22.    left->height=max(height(left->left),height(left->right))+1;
    
23.    return left;
    
24. }

左旋：

1. node* leftRotate(node *target){
   
2.    node *right=target->right;
   
3.    node *grandNode=target->parent;
   
4.    if(grandNode!=NULL){
   
5.        right->parent=grandNode;
   
6.        if(target==grandNode->left)
   
7.             grandNode->left=right;
   
8.        else
   
9.             grandNode->right=right;
   
10.    }
    
11.    node *move=right->left;
    
12.    right->parent=target->parent;
    
13.    target->parent=right;
    
14.    right->left=target;
    
15.    target->right=move;
    
16.    if(move!=NULL)
    
17.       move->parent=target;
    
18.    if(target==root){
    
19.       root=right;
    
20.    }
    
21.    target->height=max(height(target->left),height(target->right))+1;
    
22.    right->height=max(height(right->left),height(right->right))+1;
    
23.    return right;
    
24. }

      这里需要注意的是，旋转操作会导致某些节点的高度产生变化，产生变化的节点就是初始的头节点和旋转后的头节点，这里需要重新设置这两个节点的高度（如图：右旋操作）

 

       这里4节点和2节点需要重新设置节点高度，由于4节点的高度依赖于2节点的高度，所以要先更新2节点高度，再更新4节点的高度

       删除节点操作在删除节点的两个子节点都不为空时需要选出节点的后继节点来替换删除节点的值。后继节点的代码引用红黑树中代码

1. node* succussor(node* target){
   
2.   node* t=target;
   
3.   if(target->right!=NULL){
   
4.      t=target->right;
   
5.      while(t->left!=NULL)
   
6.        t=t->left;
   
7.      return t;
   
8.   }
   
9.   while(t->parent!=NULL&&t->parent->right==t){
   
10.      t=t->parent;
    
11.   }
    
12.   return t->parent;
    
13. }

    平衡化二叉树的处理，有四种情况

1.左单旋

2.右单旋

3.先右单旋子节点，在左旋

4.先左单旋字节点，再右旋

前面两种情况在红黑树中已经讲解（纯粹左旋右旋），另外两种

这种情况下需要围绕1节点做左旋，但是3节点没有右孩子，需要3节点那个位置有右孩子，因为如果没有的话旋转过后还是节点高度差2，所以应该首先让3节点有右孩子，直接围绕3节点右单旋，然后转换到中间状态，然后再次左单旋即可。

转换情况和上面类似，同时需要注意，同时注意在第一步局部旋转的过程中也需要更新节点的高度。

插入节点代码：

1. 插入代码：
   
2. void insert(node *parent,int data){
   
3.      if(parent->value>data){
   
4.          if(parent->left==NULL){
   
5.              node *result=(node *)malloc(sizeof(node));
   
6.              result->value=data;
   
7.              result->parent=parent;
   
8.              parent->left=result;
   
9.              result->height=1; //新节点高度都是1
   
10. 
    
11.          }else{
    
12.               insert(parent->left,data);
    
13.               if(height(parent->left)-height(parent->right)==2){
    
14.                     if(data<parent->left->value){
    
15.                          parent=rightRotate(parent);   //case2 右单旋
    
16.                       }else{
    
17.                          leftRotate(parent->left);     //case4 左单旋，右单旋
    
18.                          parent=rightRotate(parent);
    
19. 
    
20.                       }
    
21.                }
    
22.            }
    
23.      }else{
    
24.           if(parent->right==NULL){
    
25.               node *result=(node *)malloc(sizeof(node));
    
26.               result->value=data;
    
27.               result->parent=parent;
    
28.               parent->right=result;
    
29.               result->height=1;
    
30.           }else{
    
31.               insert(parent->right,data);
    
32.               if(height(parent->right)-height(parent->left)==2){
    
33.                      if(data>parent->right->value){
    
34.                            parent=leftRotate(parent);   //case1 左单旋
    
35.                       }else{
    
36.                            rightRotate(parent->right);  //case3 右单旋 左单旋
    
37.                            parent=leftRotate(parent);
    
38.                         }
    
39.                 }
    
40.          }
    
41.       }
    
42.      parent->height=max(height(parent->left),height(parent->right))+1; 
43.         //在递归过程中更新影响节点的高度
    
44. }

在这个递归插入过程中最重要的就是最后一句，作用是在递归过程中，可以认为是更新的节点影响了当前递归过程中的parent节点，要更新该节点的高度，同时外面的递归过程又会以parent节点为基础，更新当前递归函数中的parent节点的高度。

节点删除操作：

二叉树节点的删除操作，参见红黑树中的二叉树节点删除原理：

代码：

1. void delete(int data){
   
2.    node* target=findNode(data);
   
3.    if(target==NULL)
   
4.       return;
   
5.    node* p;
   
6.    if(target->left!=NULL&&target->right!=NULL){ //有两个子节点，寻找代替节点
   
7.      node* replace=succussor(target);
   
8.      target->value=replace->value;
   
9.      node* child=replace->right;
   
10.      p=replace->parent;
    
11.      if(p!=NULL&&p->left==replace)
    
12.         p->left=child;
    
13.      else if(p!=NULL&&p->right==replace)
    
14.         p->right=child;
    
15.    }else{                                       //有一个子节点，直接删除
    
16.      node* t=target->left==NULL?target->right:target->left;
    
17.      if(target->parent==NULL)
    
18.        root=t;
    
19.      p=target->parent;
    
20.      if(p!=NULL&&p->left==target)
    
21.        p->left=t;
    
22.      else if(p!=NULL&&p->right==target)
    
23.        p->right=t;
    
24. 
    
25.    }
    
26.    if(p!=NULL)                                   //影响了节点的高度，需要更新节点高度
    
27.      deleteAdjust(p);
    
28.  }

     二叉树节点的删除会导致原本parent节点左右子树高度的变化，这个变化会影响到父节点及其以上的数据结构，首先更新父节点的高度，同时递归计算左右子树的高度差如果大于等于2，就根据平衡的那几个case执行旋转操作，继续递归该节点的父节点，直到根节点结束。

节点高度调整代码：

1. void deleteAdjust(node* target){
   
2.    while(target!=NULL){
   
3.      target->height=max(height(target->left),height(target->right))+1; //首先更新节点的高度
   
4.      if(height(target->right)-height(target->left)==2){
   
5.         if(target->right->right==NULL){
   
6.             rightRotate(target->right);                               //case3
   
7.         }
   
8.         target=leftRotate(target);                                     //case1
   
9.      }else if(height(target->left)-height(target->right)==2){
   
10.         if(target->left->left==NULL){
    
11.             leftRotate(target->left);                                  //case4
    
12.         }
    
13.         target=rightRotate(target);                                    //case2
    
14.      }
    
15.      target=target->parent;                                             //递归父节点
    
16.    }
    
17.  }