[자료구조]탐색 2 (12-2-1) LL/RR회전 도구

리밸런싱 도구 : LL 회전

LL회전은 어떻게 진행될까?

앞선 포스트들을 잘 보아왔다면 충분히 생각해낼수 있고
개념의 이해일때 추가해야할 함수도 생각했었다.

그러니 바로 코드를 짜보자 !

BTreeNode * RotateLL(BTreeNode * bst) // LL회전을 담당하는 함수
{
	BTreeNode * pNode; // parent Node
    BTreeNode * cNode; // child Node 
    
    // pNode 와 cNode가 LL회전을 위해 적절한 위치를 가리키게 한다.
    pNode = bst;
    cNode = GetLeftSubTree(pNode);
    
    // 실제 LL회전을 담당하는 두 개의 문장 
    ChangeLeftSubTree(pNode,GetRightSubTree(cNode);
    ChangeRightSubTree(cNode,pNode); // 회전이 일어난다. 
    
    //LL회전으로 인해서 변경된 루트 노드의 주소 값 반환
    return cNode;  
}

어떤가 !
그저 pNode,cNode를 생성 후 초기화를 진행중이고 앞서 구현한 회전 도구들을 이용한 후 !
루트 노드가된 cNode를 반환해주는 도구이다!

리밸런싱 도구 : RR회전

이제 RR회전의 함수를 정의해주자
자!
LL과 다른게 무엇이라고했는지 기억나는가?
바로 회전 방향만 다르다!!
그렇다면 바로 코드를 짜주자!

BTreeNode * RotateRR(BTreeNode * bst) // RR회전을 담당하는 함수
{
	BTreeNode * pNode; // parent Node
    BTreeNode * cNode; // child Node 
    
    // pNode 와 cNode가 LL회전을 위해 적절한 위치를 가리키게 한다.
    pNode = bst;
    cNode = GetRightSubTree(pNode);
    
    // 실제 LL회전을 담당하는 두 개의 문장 
    ChangeRightSubTree(pNode,GetLeftSubTree(cNode);
    ChangeLeftSubTree(cNode,pNode); // 회전이 일어난다. 
    
    //LL회전으로 인해서 변경된 루트 노드의 주소 값 반환
    return cNode;  
}

보이는가! LL회전과의 차이가
바로 방향뿐이다.

이제 다음 도구로 LR/RL회전을 다음 포스트에서 배워보자.