程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 紅黑樹系列之旋轉

紅黑樹系列之旋轉

編輯:關於C
(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 

        總結:旋轉的算法思路非常清晰,整個邏輯思考是重點

摘自 博觀約取,厚積薄發
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved