| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3952 人关注过本帖, 1 人收藏
标题:avl树的新算法,欢迎测试并指出不足
只看楼主 加入收藏
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:0 
回复 19楼 GBH1
// 哪些变量定义语义不清,我给改过来。
//  删除操作函数已经修改好,简单测试了一下,没发现问题了,欢迎大家继续测试
//  因时间问题,代码仍未精简、完善, 见谅!
//  测试时可以输入字母a、b、c、d...代替输入月份

程序代码:
void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点!\n");
        return ;
    }
    if(strcmp(x.key, (*parent)->data.key) == 0){
        if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL))
        {    //情况1:无孩子 
            free(*parent);
            *parent = NULL;
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL))
        {    //情况2:无左孩子 
            temp = *parent;
            *parent = (*parent)->rightChild;
            free(temp);
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL))
        {    //情况3:无右孩子 
            temp = *parent;
            *parent = (*parent)->leftChild;
            free(temp);
             *unbalanced = TRUE;
        }else{    //情况4:有俩孩子 
            if((*parent)->leftChild->rightChild == NULL){//左孩无右孙 
                temp = *parent;
                *parent = (*parent)->leftChild;
                (*parent)->rightChild = temp->rightChild;
                free(temp);
                if((*parent)->bf == 0){
                    (*parent)->bf = -1;
                    *unbalanced == FALSE;
                }else if((*parent)->bf == 1){
                    (*parent)->bf = 0;
                     *unbalanced = FALSE;
                }else{
                    rightRotation(parent, unbalanced);
                }
            }else{    //左孩有右孙 
                leftMaxNode(parent, &(*parent)->leftChild, unbalanced);
                 if(*unbalanced){
                    if((*parent)->bf == -1){
                        rightRotation(parent, unbalanced);
                    }else if((*parent)->bf == 0){
                        (*parent)->bf = -1;
                        *unbalanced = FALSE;
                    }else if((*parent)->bf == 1){
                        (*parent)->bf = 0;
                        *unbalanced = FALSE;
                    } 
                }    
            }
        }
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlDelete(&(*parent)->leftChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == 1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = -1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == -1){
                rightRotation(parent, unbalanced);
            }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlDelete(&(*parent)->rightChild, x, unbalanced);
        if(*unbalanced)   
            if((*parent)->bf == -1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            }
    }
}

void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced)
{            /* 与左子树最大元交换,并删除结点 */
    if((*maxNode)->rightChild->rightChild == NULL){
        treePointer temp = *parent;
        
        *parent = (*maxNode)->rightChild;
        (*maxNode)->rightChild = (*maxNode)->rightChild->leftChild;
        (*parent)->leftChild = temp->leftChild;
        (*parent)->rightChild = temp->rightChild;
        (*parent)->bf = temp->bf;
        free(temp);
        temp = NULL;/*不知道为什么,这里必须给temp赋空值,虽然后再不用temp了*/ 
        if((*maxNode)->bf == 0){
            (*maxNode)->bf = -1;
            *unbalanced = FALSE;
        }else if((*maxNode)->bf == -1){
            (*maxNode)->bf == 0;
            *unbalanced = TRUE;
        }else if((*maxNode)->bf == 1){
            leftRotation(maxNode, unbalanced);
            (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
        }   
    }else{
        leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced);
        if(*unbalanced){
            if((*maxNode)->bf == -1){
                (*maxNode)->bf = 0;
                *unbalanced = FALSE;                
            }else if((*maxNode)->bf == 0){
                (*maxNode)->bf = 1;
                *unbalanced = FALSE;                
            }else  /* (*maxNode)->bf == 1 */ 
                leftRotation(maxNode, unbalanced);
        } 
    }
}


[此贴子已经被作者于2017-8-2 09:06编辑过]


一切都在学习、尝试、摸索中
2017-08-02 08:34
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:0 
回复 21楼 marlow
//这种算法平衡因子的调整在删除函数中显得非常麻烦,avl树也比红黑树更难对付一些。
//上面的代码存在不少问题,这次努力做了修改,并把更完善一些的代码贴上,但恐怕某些地方还存在问题,实在没有精力去测试了。。。
//注释可能不够,等有空再补上
程序代码:
void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点!\n");
        return ;
    }
    if(strcmp(x.key, (*parent)->data.key) == 0){
        if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL))
        {    //情况1:无孩子 
            free(*parent);
            *parent = NULL;
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL))
        {    //情况2:无左孩子 
            temp = *parent;
            *parent = (*parent)->rightChild;
            free(temp);
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL))
        {    //情况3:无右孩子 
            temp = *parent;
            *parent = (*parent)->leftChild;
            free(temp);
             *unbalanced = TRUE;
        }else{    //情况4:有俩孩子 
            if((*parent)->leftChild->rightChild == NULL){//左孩无右孙 
                temp = *parent;
                *parent = (*parent)->leftChild;
                (*parent)->rightChild = temp->rightChild;
                free(temp);
                if((*parent)->bf == 0){
                    (*parent)->bf = -1;
                //    *unbalanced == FALSE;     未改变*unbalanced值
                }else if((*parent)->bf == 1){
                    (*parent)->bf = 0;
                     *unbalanced = TRUE;
                }else if((*parent)->bf == -1){
                    rightRotation(parent, unbalanced);
                    *unbalanced = TRUE; /* 旋转之后树变矮了,所以变得不平衡 */
                }
            }else{    //左孩有右孙 
        /* 只要左子树总体层高没变化,那么它返回去的时候就应当看作是平衡的 */
                int prebf = (*parent)->leftChild->bf;
                leftMaxNode(parent, &(*parent)->leftChild, unbalanced);
                if(prebf != 0 && prebf != (*parent)->leftChild->bf)
                    *unbalanced = TRUE;
                else
                    *unbalanced = FALSE;
                if(*unbalanced){
                    if((*parent)->bf == -1){
                        rightRotation(parent, unbalanced);
                    //    *unbalanced = TRUE;  未改变*unbalanced值
                    }else if((*parent)->bf == 0){
                        (*parent)->bf = -1;
                        *unbalanced = FALSE;
                    }else if((*parent)->bf == 1){
                        (*parent)->bf = 0;
                    //    *unbalanced = TRUE;     未改变*unbalanced值
                    } 
                }    
            }
        }
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlDelete(&(*parent)->leftChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == 1){
                (*parent)->bf = 0;
            //    *unbalanced = TRUE;   未改变*unbalanced值 
            }else if((*parent)->bf == 0){
                (*parent)->bf = -1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == -1){
                rightRotation(parent, unbalanced);
            //    *unbalanced = TRUE;         未改变*unbalanced值
            }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlDelete(&(*parent)->rightChild, x, unbalanced);
        if(*unbalanced)   
            if((*parent)->bf == -1){
                (*parent)->bf = 0;
            //    *unbalanced = TRUE;     未改变*unbalanced值
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
                *unbalanced = FALSE;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            //    *unbalanced = TRUE;     未改变*unbalanced值
            }
    }
}

void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced)
{            /* 与左子树最大元交换,并删除结点 */
    if((*maxNode)->rightChild->rightChild == NULL){ 
        treePointer temp = *parent;
         
        *parent = (*maxNode)->rightChild;
        (*maxNode)->rightChild = (*maxNode)->rightChild->leftChild;
        (*parent)->leftChild = temp->leftChild;
        (*parent)->rightChild = temp->rightChild;
        (*parent)->bf = temp->bf;
        if((*maxNode)->bf == 0){
            (*maxNode)->bf = 1;
            *unbalanced = FALSE;     //未改变*unbalanced值
        }else if((*maxNode)->bf == -1){
            (*maxNode)->bf == 0;
            *unbalanced = TRUE;     
        }else if((*maxNode)->bf == 1){
            short int i = (*maxNode)->leftChild->bf;
            
            leftRotation(maxNode, unbalanced);
            if(i == 0){  //若子结点bf为0,说明有两个孩子,bf调整异于插入算法 
                (*maxNode)->bf = 1;
                (*maxNode)->leftChild->bf = 1;
            }
            (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
            preprintree(*maxNode);
        }   
        free(temp); 
        temp = NULL;/*还没搞懂,为什么只能放在最后free()*/ 
    }else{ 
        leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced);
        if(*unbalanced){
            if((*maxNode)->bf == -1){
                (*maxNode)->bf = 0;
            //    *unbalanced = TRUE;         未改变*unbalanced值        
            }else if((*maxNode)->bf == 0){
                (*maxNode)->bf = 1;
                *unbalanced = FALSE;                
            }else if((*maxNode)->bf == 1) 
                leftRotation(maxNode, unbalanced);
            //    *unbalanced = TRUE;  未改变*unbalanced值
                (*parent)->leftChild = *maxNode; /*这行代码容易被忽略    */ 
        } 
    }
}

一切都在学习、尝试、摸索中
2017-08-11 23:16
快速回复:avl树的新算法,欢迎测试并指出不足
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017163 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved