열혈 자료구조 - 11.2 이진 탐색 트리

이진 탐색 트리

- 데이터의 저장 규칙이 있는 이진트리

- 데이터 저장 규칙

    -> 부모 노드를 기준으로 작은 값은 좌측, 큰 값은 우측에 저장

- 데이터의 삽입 과정

    -> 루트 노드부터 비교하면서 삽입하고자 하는 데이터가 작으면 왼쪽으로 크면 오른쪽으로 이동하면서 자리를 찾음

    -> 탐색도 이런 과정을 거침

- 삭제

    -> 삭제는 고려해야 할 상황이 3가지가 있음

    -> 1. 삭제할 노드가 단말 노드인 경우

        * 부모 노드(4)에서 왼쪽, 오른쪽(7) 노드를 삭제시킴

    -> 2. 삭제할 노드가 하나의 자식 노드(서브 트리)를 갖는 경우

        * 삭제하고자 하는 노드를 지우고 자식 노드를 삭제하고자 하는 노드의 부모 노드와 연결

        * 삭제하려는 노드가 오른쪽이었다면 오른쪽에 연결하고 왼쪽이었다면 왼쪽에 연결

    -> 3. 삭제할 노드가 두 개의 자식노드(서브트리)를 갖는 경우

        * 삭제하고자 하는 노드의 데이터의 서브 트리에서 좌측에서 가장 큰 값과 우측에서 가장 작은 값을 찾음

        * 아래의 경우 8을 삭제할 경우 8의 좌 우측에서 가장 작고 큰 값인 7과 9를 찾음

        * 둘 중 하나의 값으로 대체        

        * 우측과 같은 경우에는 대입->삭제->연결의 순서

     -> 4. 삭제할 노드가 루트노드인 경우

        * 루트노

이진 탐색 트리의 구현

- 삽입

    -> 비교하면서 NULL을 만날 때까지 탐색하고 그 위치에 삽입

void BSTInsert(BTreeNode * pRoot, BSTData data)
{
	BTreeNode * pNode = NULL;    // 부모 노드
	BTreeNode * cNode = pRoot;    // 현재 노드 (트리 자체가 루트 노드)
	BTreeNode * nNode = NULL;    // 새로 저장할 노드

	// NULL이 나올때까지 탐색
	while(cNode != NULL)
	{
		if(data == GetData(cNode)) {
			return;    // 키의 중복을 허용하지 않음
		}
        
		pNode = cNode;

		if(GetData(cNode) > data) {
			cNode = GetLeftSubTree(cNode);
        	}
		else {
			cNode = GetRightSubTree(cNode);
        	} // 비교하면서 작으면 왼쪽 크면 오른쪽으로 
	}
	
	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL)    // 새 노드가 루트 노드가 아니면
	{
		if(data < GetData(pNode)) {
			MakeLeftSubTree(pNode, nNode);
        }
		else {
			MakeRightSubTree(pNode, nNode);
        } // 저장할때도 작으면 왼쪽에 크면 오른쪽에 저장
	}
	else    // 새 노드가 루트 노드면
	{
		*pRoot = nNode;
	}
}

- 탐색

    -> 삽입과 같이 좌우측으로 비교하면서 내려가다가 찾고자 하는 데이터의 값을 가진 노드의 주소 값을 반환

BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
	BTreeNode * cNode = bst;    // 현재 노드
	BSTData cd;    // 현재 노드의 데이터

	while(cNode != NULL)
	{
		cd = GetData(cNode);

		if(target == cd) {
			return cNode;		// 찾고자 하는 값과 같다면 노드의 주소값을 반환
        	}
		else if(target < cd) {
			cNode = GetLeftSubTree(cNode);
        	}
		else {
			cNode = GetRightSubTree(cNode);
        	}
	}
	// while문을 빠져나왔을 경우는 원하는 데이터를 가진 노드가 없는 경우
	return NULL; 
}

- 삭제

    -> 위와 같이 상황을 3개로 나눠서 구현

BTreeNode * BSTRemove(BTreeNode * pRoot, BSTData target)
{
	BTreeNode * pNode = pRoot;    // 부모 노드
	BTreeNode * cNode = pRoot;    // 현재 노드
	BTreeNode * dNode;    // 삭제하려는 노드
	
	// 삭제 대상을 저장한 노드 탐색
	while(cNode != NULL && GetData(cNode) != target)
	{
		pNode = cNode;

		if(target < GetData(cNode))
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	if(cNode == NULL)    // 삭제 대상이 존재하지 않는다면,
		return NULL;

	dNode = cNode;    // 삭제 대상을 dNode가 가리키게 한다.

	// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우
	if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
	{
		if(GetLeftSubTree(pNode) == dNode)
			RemoveLeftSubTree(pNode);
		else
			RemoveRightSubTree(pNode);
	}

	// 두 번째 경우: 하나의 자식 노드를 갖는 경우
	else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
	{
		BTreeNode * dcNode;    // delete node의 자식 노드

		if(GetLeftSubTree(dNode) != NULL)
			dcNode = GetLeftSubTree(dNode);
		else
			dcNode = GetRightSubTree(dNode);

		if(GetLeftSubTree(pNode) == dNode)
			ChangeLeftSubTree(pNode, dcNode);
		else
			ChangeRightSubTree(pNode, dcNode);
	}

	// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우
	else
	{
		BTreeNode * mNode = GetRightSubTree(dNode);    // 삭제하고자 하는 노드의 오른쪽 노드
		BTreeNode * mpNode = dNode;
		int delData;

		// 우측에서 가장 작은 값을 구함
		while(GetLeftSubTree(mNode) != NULL)
		{
			mpNode = mNode;		// 부모-자식노드 연결을 위한 mpNode
			mNode = GetLeftSubTree(mNode);	// 좌측 노드를 구하면서 NULL이 나올때까지 반복
		}
		
		// 대체할 노드에 저장된 값을 삭제할 노드에 대입
		delData = GetData(dNode);    // 대입 전 데이터 백업
		SetData(dNode, GetData(mNode));		// 삭제할 위치에 가장 작은 노드의 값을 대입

		// 대체할 노드의 부모 노드와 자식 노드를 연결
		if(GetLeftSubTree(mpNode) == mNode) {
			ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
        	}
		else {
			ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
        	}
	}
    
	return dNode;
}