AVL 树模拟 最佳分配算法

AVL树：又称平衡二叉树。具有的特性：
                          1>左右子树的深度之差的绝对值小于等于1
                          2>左子树和右子树也是平衡树
              目的：提高查找效率，其平均查找长度为O(logn)
模拟思想：结合了伙伴算法的思想在初始化时，将内存区分成了2^n块，并且使用平衡二叉树进程组织（计算平衡因子）。  然后根据“左小右大”的原则进行查找，找到后将该节点移除并且对该该树进行调衡。对于移除的节点进行新的大小分割，并且根据剩余大小找到合适的插入位置。
                查找情况-----1、比该节点剩余内存大，向右子树查找。
                                    2、比该节点剩余内存小，向左子树查找
                                    3、比该节点剩余大小相等，则插入该节点所在的链。
结构体：

struct MM {
    int total;
    int address;
    int cur_size;
 };
 struct AVL_TREE {
     struct MM mem_id;
     char   bar;
     struct AVL_TREE * memLeft;
     struct AVL_TREE * memRight;
     struct AVL_TREE * next;
     struct AVL_TREE * parents;
 };

初始化：

void init_AVL_tree(struct AVL_TREE ** root, struct AVL_TREE *p)
{
    int mem[]={4,2,1,0,-1,-1,-1,3,-1,-1,7,6,5,-1,-1,-1,8,-1,9,-1,-1};
    static int   in;
    if(in < sizeof(mem))
    {
        if(mem[in]==-1)
        {    *root = NULL;
            in++;
        }
        else
            {
                *root = creat_one_node(mem[in++],p);
                p = *root;
                init_AVL_tree(&((*root)->memLeft),p);
                init_AVL_tree(&((*root)->memRight),p);
            }
    }
}
struct AVL_TREE *creat_one_node(int me,struct AVL_TREE *parents)
{
    struct    AVL_TREE * node = (struct AVL_TREE *)malloc(sizeof(struct AVL_TREE));
    node->mem_id.total = two_power_of(me);
    node->mem_id.cur_size = 0;
    node->mem_id.address = node->mem_id.total-1;
    node->bar= 0;
    node->memLeft = NULL;
    node->next = NULL;
    node->parents =parents;
    node->memRight =NULL;
    return node;
}

查找：

struct AVL_TREE * search_best_MM(struct AVL_TREE *root,int mm)
{
    struct AVL_TREE                     *p, *pre = NULL;

    printf("search_best_MM\n");
     p = root;
    while(p)
    {
        if(mm >((p->mem_id.total)-(p->mem_id.cur_size)))
            p = p->memRight;
        else if(mm < (p->mem_id.total-p->mem_id.cur_size))
        {
            pre = p;
            p = p->memLeft;
        }
        else
        {
            pre = p;
            break;
        }
    }
    return pre;
}

调衡：LL：
               

void balance_LL(struct AVL_TREE * tree,struct AVL_TREE **root)
{
    struct AVL_TREE             *next1;

    next1 = tree->memLeft;
    printf("LL\n");
    next1->parents = tree->parents;
    if(tree->parents) {
    if(tree->parents->memLeft == tree)
         tree->parents->memLeft = next1;
    else
       tree->parents->memRight = next1;
    } else
          (*root) = next1;

    tree->memLeft = next1->memRight;
    if(next1->memRight != NULL)
        next1->memRight->parents = tree;
    next1->memRight = tree;
    tree->parents = next1;

    tree->bar = '0';
    next1->bar ='0';
    change_bar(next1,1,LEFT);
}

 LR：
                    

void balance_LR(struct AVL_TREE *tree,struct AVL_TREE **root)
{
     struct AVL_TREE *next1, *next2;

    printf("LR\n");
    next1 = tree->memLeft;
    next2 = next1->memRight;
    next2->parents = tree->parents;
    printf("LR\n");
    if(tree->parents) {
      if(tree->parents->memLeft == tree)
           tree->parents->memLeft = next2;
       else
          tree->parents->memRight = next2;
    } else
            (*root) = next2;
    next1->memRight = next2->memLeft;
    if(next2->memLeft)
        next2->memLeft->parents = next1;
    tree->memLeft = next2->memRight;
   if(next2->memRight)
        next2->memRight->parents = tree;

    tree->bar = '0'-1;
    next1->bar = next2->bar = '0';
    next2->memRight = tree;
    tree->parents = next2;
    next2->memLeft = next1;
    next1->parents = next2;
    change_bar(next2,1,LEFT);
}

  RR：
              

void balance_RR(struct AVL_TREE * tree,struct AVL_TREE ** root)
{
    struct    AVL_TREE                *next1;

    printf("RR\n");
    next1 = tree->memRight;

    printf("RR\n");
    if(tree->parents)
       if(tree->parents->memLeft == tree)
            tree->parents->memLeft = next1;
        else
          tree->parents->memRight = next1;
    printf("RR\n");
    next1->parents = tree->parents;
    printf("RR\n");
     if(tree->parents == NULL)
            (*root) = next1;

    printf("RR\n");
    tree->memRight = next1->memLeft;
    if(next1->memLeft)
        next1->memLeft->parents = tree;
    next1->memLeft = tree;
    tree->parents = next1;

    next1->bar = '0';
    tree->bar = '0';
    change_bar(next1,1,RIGHT);

}

     RL：
           
  

void balance_RL(struct AVL_TREE * tree,struct AVL_TREE ** root)
{
    struct AVL_TREE                *next1, *next2;

    printf("RL\n");
    next1 = tree->memRight;
    next2 = tree->memLeft;

      if(tree->parents->memLeft == tree)
          tree->parents->memLeft = next2;
      else
          tree->parents->memRight = next2;
     next2->parents = tree->parents;
     if(tree->parents == NULL)
              (*root) = next2;
     tree->memRight = next2->memLeft;
     if(next2->memLeft)
         next2->memLeft->parents = tree;

     next1->memLeft = next2->memRight;
     if(next2->memRight)
         next2->memRight->parents = next1;

     next2->memRight = next1;
     next1->parents = next2;
     next2->memLeft = tree;
     tree->parents = next2;

     next2->bar='0';
     tree->bar ='1';
     next1->bar = '0';
     change_bar(next2,1,RIGHT);
}

下列是完整代码：（多个文件的整合）
  code.txt