欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

红黑树系列之旋转

程序员文章站 2022-10-17 23:00:12
(1)概述          二叉树是使用非常广泛的数据结构,但如果是常规的插入,会导致二叉树的高...
(1)概述
         二叉树是使用非常广泛的数据结构,但如果是常规的插入,会导致二叉树的高度过高和出现整棵树不平衡的情况。红黑树是一种平衡二叉树,c++stl中的set,map及其扩展容器内部的数据结构都是红黑树。
(2)左旋转
         比如说,需要把x旋转为y的左结点。整个算法的思路非常清晰:从上至下,先得到y指针,讲x的右指针指向y的左结点,然后利用parent函数得到x的父亲结点,如果为null,则y为新的根,如果不为null,则根据x是其父亲的左孩子还是右孩子,将指针指向y。最后将y的左指针指向x,完成旋转。值得注意的是,算法是具有顺序的逻辑步骤,不能够调换顺序,如果改变赋值的顺序会造成内存失去指针指向,出现内存错误。
       代码:注:parent为求父亲结点的函数,root是始终指向根结点内存区域的指针。
[cpp]
//左旋转,假设x->pright!=null 
void left_rotate(node *head,node *x)//head是根结点,x是待左旋转的结点 

    if(x->pright!=null) 
    { 
        node *y=x->pright; 
        if(y->pleft!=null) 
            x->pright=y->pleft; 
        node *px=parent(x,head); 
        if(px==null)//如果x是根结点,那么就把y置为根结点 
            root=y; 
        else if(px->pleft==x) 
            px->pleft=y; 
        else 
            px->pright=y; 
        y->pleft=x; 
    } 
    else 
        printf("item为%ld的结点不能够进行左旋转!",x->item); 

 
(3)右旋转
        方法与左旋转基本相同,只是方向相反,不再赘述其过程。
        代码:
[cpp]
//右旋转,假设y->pleft!=null    
void right_rotate(node *head,node *y)//head是根结点,y是待右旋转的结点 

    if(y->pleft!=null) 
    { 
        node *x=y->pleft; 
        if(x->pright!=null) 
            y->pleft=x->pright; 
        node *py=parent(y,head); 
        if(py==null) 
            root=x; 
        else if(py->pleft==y) 
            py->pleft=x; 
        else 
            py->pright=x; 
        x->pright=y; 
    } 
    else 
        printf("item为%ld的结点不能够进行右旋转!",y->item); 

 
[cpp]
//返回父亲结点 
node *parent(node *pnode,node *head) 

    node *result=null; 
    if(head!=null) 
    { 
        if(head->pleft==pnode || head->pright==pnode) 
            return head; 
        if(head->pleft!=null) 
        { 
            result=parent(pnode,head->pleft); 
            if(result!=null)//找到之后就不搜索其他的了 
                return result; 
        } 
        if(head->pright!=null) 
        { 
            result=parent(pnode,head->pright); 
            if(result!=null) 
                return result; 
        } 
    } 
    return result;//没有找到,返回null 

        总结:旋转的算法思路非常清晰,整个逻辑思考是重点

摘自 博观约取,厚积薄发