Binary Search Tree

Binary Search Tree(이진 탐색 트리)

• 이진 트리는 하나의 노드가 두개의 포인터를 가지고 있다

• 그중에서 이진 탐색 트리(binary search tree)는 이진 탐색과 연결 리스트를 결합한 자료구조라고 할 수 있다

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다

• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다

• 중복된 노드가 없어야 한다

• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색 트리이다

 

순회

트리의 모든 노드를 한 번씩 방문하여 모든 정보에 대한 선형 순서를 만들어내는 방법

 

 

전위순회(PreOrder Traversal) : Root를 가장 먼저 들린다

1. Root 를 방문

2. 왼쪽 Subtree 를 방문

3. 오른쪽 Subtree 를 방문

 

 

중위순회(InOrder Traversal) : Root를 중간에 들린다

1. 왼쪽 Subtree를 방문

2. Root를 방문

3. 오른쪽 Subtree를 방문

 

후위순회(PostOrder Traversal) : Root를 가장 나중에 들린다

1. 왼쪽 Subtree를 방문

2. 오른쪽 Subtree를 방문

3. Root를 방문

 

트리 노드 삭제 루틴

트리 노드를 삭제할시, 3가지 경우로 나뉜다

1. 하위 노드가 없는경우

   • 그냥 삭제 한다
      

2. 하위 노드가 하나만 있는경우(left 또는 right)

• 하위 노드를 삭제된 노드 자리에 앉힌다
   

•  

  

3. 하위 노드가 둘다 있는 경우

• 해당 노드가 head 루트 노드 보다 작으면 right node 를 삭제된 노드 자리에 앉힌다
• (해당 노드가 head 루트 노드 보다 크면 left node 를 삭제된 노드 자리에 앉힌다)
• 나머지 노드 left node를 새로 앉힌 노드의 left node로 맞춘다
• (나머지 노드가 right 노드 였던 경우 새로 앉힌 노드의 right node에 맞춘다)

 

 

 

 

 

순회 순서

 

 

위와 같은 이진탐색 트리가 존재할때

중위순회를 할경우

 

4,5,6,7,10,11,13,17,20 순으로 순회 한다 즉 그림으로 그리면

 

위와 같은 경로가 그려진다

모든 노드는 left, right, root 노드를 가지고 있으며, 각각 노드들이 또다른 어떤 노드의 루트 노드가 될 수 있다, 즉, 순회할수 있는 방향은 left, right, root 등으로 나뉘어지는게 어떤조건에서 어떤 경로로 이동하는 것일까?

 

일단 첫시작점을 이미 찾았다는 전제 하에서

가고자 하는 방향이 nullptr인 경우 무시하기로 한다

또한 순회하면서 나오는 값들은 이전값보다는 높아야한다

4 -> rightNode -> leftNode

5 -> rootNode

6 -> rightNode/ -> leftNode(nullptr)

7 -> rootNode -> rootNode-> rootNode (7 보다 높지않은 값들(6,4)을 거쳐서 10에 도달

10 -> rightNode->leftNode

11 -> rootNode

13 ->rightNode -> leftNode

17 -> rootNode

20 ->/rightNode(nullptr)

 

즉 위패턴으로 이터레이터 연산자 오버로딩 operator ++ () 을 구현할 경우

 

void operator ++ ()
{
    assert(m_pNode != nullptr);
 
    if (m_pNode->m_pRightNode != nullptr)
    {
        m_pNode = m_pNode->m_pRightNode;
        while (m_pNode->m_pLeftNode != nullptr)
        {
            m_pNode = m_pNode->m_pLeftNode;
        }
        return;
    }
    else if (m_pNode->m_iData < m_pNode->m_pRootNode->m_iData)
    {
        m_pNode = m_pNode->m_pRootNode;
        return;
    }
 
    while (m_pNode->m_iData > m_pNode->m_pRootNode->m_iData)
    {
        m_pNode = m_pNode->m_pRootNode;
    }
    m_pNode = m_pNode->m_pRootNode;
}

위와 같은 코드가 된다

 

 

그럼 반대 루틴을 보면

20 -> leftNode

17 -> rootNode -> rootNode

13 -> leftNode

11 -> rootNode -> rootNode

10 -> leftNode -> rightNode -> rightNode //m_pHead

7 -> rootNode

6 -> leftNode

5 -> rootNode -> rootNode

4

 

일단 시작은 leftNode로 간뒤 rightNode를 찾는다, 그리고 rightNode가 나오면 나올수록 계속 rightNode로 간다

그리고 rootNode->rootNode 가 되는 부분은 왼쪽으로 뻗은길을 찾기위한 반복되는 과정이라고 할수있다

즉 해당 노드의 데이터가 노드의 루트 데이터 보다 큰경우를 찾는것이다

즉 오른쪽으로 뻗은길이 나올때까지 이동한다

(pNode->iData > pNode->pRoot->iData)

 

 

 

또다른 트리를 통해 다시 한번 자세히 살펴보면 

 

 

4,10,11,13,26,27,28,29,30,31 를 노드로 가지고 있는 트리다 이걸 제일 큰값 31에서 제일 작은값 4까지

순회하는 로직을 그려보면 붉은 화살표와 같다

 

순회 동작 과정

 

31

처음 31에서 시작할때는 바로 root 데이터가 30이므로 (왼쪽으로 뻗은길)

30으로 한칸 이동하면 끝난다

 

30

30에서는 왼쪽으로 뻗은길이 있기떄문에 바로 13으로 갈수 있지만

30의 leftNode 자식이 있으므로(30보다 작고 13보다 큰수)

leftNode로 가야 한다

그렇게 해서 29로 이동한후 rightNode가 있는지(29와 30사이의 수) 파악하고 없으면 대기 한다

 

29

29에서도 마찬가지로 leftNode(27)로 이동

27에서 rightNode가 있는지 확인, 28 발견 했으므로 rightNode 로 이동한다

이때 주의할점은 rightNode로 한번 갈때는

가장 끝의 rightNode까지 이동해야한다는것이다

여기서 나오는 rightNode들은 27과 29사이의 수들이다

즉 가장끝 rightNode 일 수록 29에 가까운 바로 아랫수가 될것이다

그러나 28이 끝이므로 28에서 멈춘다

 

 

28

28은 leftNode가 없다 즉 root로 이동해야 하는데,

root로 이동할때는 왼쪽으로 뻗은길이면 한번만 이동하면되고

오른쪽으로 뻗은길이면 왼쪽으로 뻗은길이 나올때까지 계속 이동해야 한다

(28 > root->iData)조건을 만족할때까지

그런데 왼쪽으로 뻗은길 즉 28 은 root->iData 인 27보다 크므로

한번만 이동한다

 

 

 

27

LeftNode가 있으므로, leftNode로 이동

26에서 멈추고 rightNode가 있는지 확인, 없으므로 그자리에 대기

 

 

 

26

leftNode,RightNode 둘다 없으므로 아까처럼 root를 타야한다

그런데 오른쪽길로 뻗어있다 즉 (26 < pRoot->iData) 식이 되므로

26 > pRoot->iData 조건이 만족할때까지 계속 이동한다

그렇게 하면 27, 29, 30,(셋다 전부 26보다 크다) 거쳐서 13에 도착한다 ( 26보다 작은수)

즉 26보다 작은수가 나올때까지 계속 이동한것이다

13에서 대기한다

 

 

13

leftNode를 확인하고, 11이 있으므로 11로 이동, rightNode를 확인한다

그러나 rightNode가 없으므로 11에서 대기 한다

 

 

11

13에서 대기한다 leftNode, RightNode가 없으므로 root로 올라가는데 마찬가지로

왼쪽으로 뻗은길을 찾을때까지 계속올라간다, 그러나 바로 왼쪽으로 뻗으므로 13 > (pRoot->iData == 10)

바로 한칸 이동한다

 

 

10(phead)

head에 도달 이때도 마찬가지로 leftNode를 확인 4가 있으므로 4로 이동한뒤

rightNode를 확인한다

없으므로 ,4에서 대기한다

 

4

끝에 도달

 

그림으로 그리면 위와 같다,

위의 경로를 패턴화 시키면

아래와 같은 순서로 동작한다

 

1.LeftNode를 확인, LeftNode가 있는경우 이동

그리고 rightNode가 있는경우 가장 끝의 rightNode까지 이동

 

2.LeftNode가 없으므로 Root로 이동 이때

해당 노드 데이터가 root 데이터보다 큰경우가 올때까지 계속

root로 이동(왼쪽으로 뻗은길이 나올때까지 이동)

 

그래서 코드로 정리하면

 

void operator -- ()
{
    assert(m_pNode != nullptr);
 
    if (m_pNode->m_pLeftNode != nullptr)
    {
        m_pNode = m_pNode->m_pLeftNode;
        while(m_pNode->m_pRightNode != nullptr)
        {
            m_pNode = m_pNode->m_pRightNode;
        }
        return;
    }
    else if (m_pNode->m_iData > m_pNode->m_pRootNode->m_iData)
    {
        m_pNode = m_pNode->m_pRootNode;
        return;
    }
 
    while (m_pNode->m_iData < m_pNode->m_pRootNode->m_iData)
    {
        m_pNode = m_pNode->m_pRootNode;
    }
    m_pNode = m_pNode->m_pRootNode;
}

 

위와 같은 코드가 나온다