본문 바로가기
C++/자료구조와 알고리듬

3. Tree, Binary Search Tree

by GameStudy 2022. 11. 4.

 

3.1 Tree

3.1-1 Binary Tree

 Note) 이진 트리

    좀 더 자세한 내용은 여기에서 참고.

<hide/>

#include <iostream>
#include <memory>

using namespace std;

template<typename T>
class STree
{
    struct SNode
    {
    public:
        SNode(const T& InData)
            : Data(InData)
            , LeftChild(nullptr)
            , RightChild(nullptr)
        {
        }

    public:
        T Data;

        std::unique_ptr<SNode> LeftChild;

        std::unique_ptr<SNode> RightChild;

    };

public:
    void Insert(const T& InValue)
    {
        InsertInternal(Root, InValue);
    }

    void PreorderTraversal()
    {
        PreorderTraversalInternal(Root);
    }

    void InorderTraversal()
    {
        InorderTraversalInternal(Root);
    }

    void PostorderTraversal()
    {
        PostorderTraversalInternal(Root);
    }
    

private:
    void InsertInternal(std::unique_ptr<SNode>& InCurrentNode, const T& InValue)
    {
        if (nullptr == InCurrentNode)
        {
            InCurrentNode = std::make_unique<SNode>(InValue);
        }
        else if (nullptr == InCurrentNode->LeftChild)
        {
            InsertInternal(InCurrentNode->LeftChild, InValue);
        }
        else if (nullptr == InCurrentNode->RightChild)
        {
            InsertInternal(InCurrentNode->RightChild, InValue);
        }
        else
        {
            InsertInternal(InCurrentNode->LeftChild, InValue);
        }
    }

    static void PreorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        { 
            return; 
        }

        cout << InCurrentNode->Data << " -> ";
        PreorderTraversalInternal(InCurrentNode->LeftChild);
        PreorderTraversalInternal(InCurrentNode->RightChild);
    }

    static void InorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        {
            return;
        }

        InorderTraversalInternal(InCurrentNode->LeftChild);
        cout << InCurrentNode->Data << " -> ";
        InorderTraversalInternal(InCurrentNode->RightChild);
    }

    static void PostorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        {
            return;
        }

        PostorderTraversalInternal(InCurrentNode->LeftChild);
        PostorderTraversalInternal(InCurrentNode->RightChild);
        cout << InCurrentNode->Data << " -> ";
    }

private:
     std::unique_ptr<SNode> Root;

};

 

  Def) 전위 순회(Preorder Traversal)

    현재 노드(상위 노드) -> 왼쪽 서브트리 -> 오른쪽 서브트리

 

  Def) 중위 순회(Inorder Traversal)

    왼쪽 서브트리 -> 현재 노드(상위 노드) -> 오른쪽 서브트리

 

  Def) 후위 순회(Postorder Traversal)

    왼쪽 서브트리 -> 오른쪽 서브트리 -> 현재 노드(상위 노드)

 

 

  Ex) 임의의 두 노드 간의 거리를 반환하는 함수를 구현하시오.

 

  Def) 최소 공통 조상(Lowest Common Ancestor, LCA)

    이진 트리 상의 임의의 두 노드가 있다.

    두 노드 사이에 공통 조상 노드 중, 가장 작은 공통 조상 노드.

 

  Def) 레벨 순서 순회(Levelorder Traversal)

    낮은 레벨에 있는 노드를 모두 방문한 후,

    다음으로 큰 레벨로 이동하여 노드를 모두 방문하는 순회.

    따라서 전위/중위/후위 순회와 다르게, 서로 연결되어 있지 않는 노드를 순회하게 됨.

    큐를 사용하여 구현해야 함. (이 개념은 BFS에서도 비슷하게 적용됨.)

 

  Note) LCA와 Levelorder Traversal 템플릿 코드

<hide/>

#include <iostream>
#include <memory>

using namespace std;

template<typename T>
class SQueue
{
public:
    SQueue(size_t InCapacity = 10u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , Size(0u)
        , FrontIndex(0u)
        , RearIndex(0u)
    {
    }

    ~SQueue()
    {
        delete[] Data;
    }

    void Enqueue(const T& value)
    {
        if (Full() == true)
        {
            std::cout << __FUNCTION__ << " Full() == true." << std::endl;
        }
        Data[RearIndex] = value;
        RearIndex = (RearIndex + 1) % Capacity;
        Size++;
    }

    void Dequeue()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        FrontIndex = (FrontIndex + 1) % Capacity;
        --Size;
    }

    T& Front()
    {
        if (Empty() == true)
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        return Data[FrontIndex];
    }

    const T& Front() const
    {
        if (Empty())
        {
            std::cout << __FUNCTION__ << " Empty() == true." << std::endl;
        }
        return Data[FrontIndex];
    }

    bool Empty() const
    {
        return Size == 0;
    }

    bool Full() const
    {
        return Size == Capacity;
    }

    size_t GetSize() const
    {
        return Size;
    }

private:
    T* Data;

    size_t Capacity;

    size_t Size;

    size_t FrontIndex;

    size_t RearIndex;

};

template<typename T>
class STree
{
    struct SNode
    {
    public:
        SNode(const T& InData)
            : Data(InData)
            , LeftChild(nullptr)
            , RightChild(nullptr)
        {
        }

    public:
        T Data;

        std::unique_ptr<SNode> LeftChild;

        std::unique_ptr<SNode> RightChild;

    };

public:
    void Insert(const T& InValue)
    {
        InsertInternal(Root, InValue);
    }

    void PreorderTraversal()
    {
        PreorderTraversalInternal(Root);
    }

    void InorderTraversal()
    {
        InorderTraversalInternal(Root);
    }

    void PostorderTraversal()
    {
        PostorderTraversalInternal(Root);
    }

    void LevelOrderTraversal()
    {
        SQueue<SNode*> Queue(100);
        Queue.Enqueue(Root.get());

        while (false == Queue.Empty())
        {
            SNode* CurrentNode = Queue.Front();
            Queue.Dequeue();

            cout << CurrentNode->Data << " -> ";

            if (CurrentNode->LeftChild != nullptr)
            {
                Queue.Enqueue(CurrentNode->LeftChild.get());
            }
            if (CurrentNode->RightChild != nullptr)
            {
                Queue.Enqueue(CurrentNode->RightChild.get());
            }
        }
        cout << endl;
    }

    T FindLCA(const T& InNode1Data, const T& InNode2Data)
    {
        SNode* LCANode = FindLCAInternal(Root.get(), InNode1Data, InNode2Data);
        if (LCANode != nullptr)
        {
            return LCANode->Data;
        }
    }    

private:
    void InsertInternal(std::unique_ptr<SNode>& InCurrentNode, const T& InValue)
    {
        if (nullptr == InCurrentNode)
        {
            InCurrentNode = std::make_unique<SNode>(InValue);
        }
        else if (nullptr == InCurrentNode->LeftChild)
        {
            InsertInternal(InCurrentNode->LeftChild, InValue);
        }
        else if (nullptr == InCurrentNode->RightChild)
        {
            InsertInternal(InCurrentNode->RightChild, InValue);
        }
        else
        {
            InsertInternal(InCurrentNode->LeftChild, InValue);
        }
    }

    static void PreorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        { 
            return; 
        }

        cout << InCurrentNode->Data << " -> ";
        PreorderTraversalInternal(InCurrentNode->LeftChild);
        PreorderTraversalInternal(InCurrentNode->RightChild);
    }

    static void InorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        {
            return;
        }

        InorderTraversalInternal(InCurrentNode->LeftChild);
        cout << InCurrentNode->Data << " -> ";
        InorderTraversalInternal(InCurrentNode->RightChild);
    }

    static void PostorderTraversalInternal(std::unique_ptr<SNode>& InCurrentNode)
    {
        if (InCurrentNode == nullptr)
        {
            return;
        }

        PostorderTraversalInternal(InCurrentNode->LeftChild);
        PostorderTraversalInternal(InCurrentNode->RightChild);
        cout << InCurrentNode->Data << " -> ";
    }

    SNode* FindLCAInternal(SNode* InCurrentNode, const T& InNode1Data, const T& InNode2Data)
    {
        if (nullptr == InCurrentNode)
        {
            return nullptr;
        }

        if (InCurrentNode->Data == InNode1Data || InCurrentNode->Data == InNode2Data)
        {
            return InCurrentNode;
        }

        SNode* LeftLCA = FindLCAInternal(InCurrentNode->LeftChild.get(), InNode1Data, InNode2Data);
        SNode* RightLCA = FindLCAInternal(InCurrentNode->RightChild.get(), InNode1Data, InNode2Data);

        if (LeftLCA && RightLCA)
        {
            return InCurrentNode;
        }

        return LeftLCA ? LeftLCA : RightLCA;
    }

private:
     std::unique_ptr<SNode> Root;

};

 

 

3.1-2 Binary Search Tree

  Def) 이진 탐색 트리(BST, Binary Search Tree)

    자료의 효율적인 관리(삽입, 탐색, 삭제)를 위한 이진 트리 기반의 자료구조.

    자료의 계층적인 구조를 표현하기 위해 트리를 사용하는 것이 아님.

 

  Note) 이진 탐색 트리의 특징

    1. 임의의 노드 N에 대해, 왼쪽 서브 트리에 있는 모든 노드의 키값은

      노드 N의 키값보다 작음.

    2. 오른쪽 서브 트리에 있는 모든 노드의 키 값은 노드 N의 키 값보다 큼.

    3. 자료의 탐색, 삽입, 삭제가 모두 O(logN)의 시간 복잡도로 동작.

    4. 중위 순회시, 오름차순으로 정렬된 값을 얻을 수 있음.

 

  Def) 후속 노드(Successor Node)

    어떤 노드의 데이터 다음으로 큰 데이터를 가진 노드.

    후속 노드는 자식이 없거나, 오른쪽 자식만 있음.

    왼쪽 자식이 있는 경우에는 후속 노드가 아님이 자명함.

    반대로 다음으로 작은 데이터를 가진 노드를 Predecessor Node라 함.

  

  Thm) 이진 탐색 트리에서의 삭제

    - 해당 노드를 삭제한 후에는 BST 특징을 유지할 수 있어야 함.

      따라서 다른 적절한 노드를 찾아 해당 노드를 대체하는 방식.

    - 이때 삭제 연산의 시간 복잡도는 O(logN) 혹은O(h)이라 할 수 있음.

Case 1. 자식 노드가 없음. Case 2. 자식 노드 하나 있음. Case 3. 자식 노드 두 개 있음.
- 해당 노드 삭제
- 엣지 삭제(NULL 대입)		 - 해당 노드 삭제
- 부모 노드의 포인터가
  해당 노드의 자식 노드 주소를 저장		 - 후속 노드의 값을 현재 노드로 복사
- 후속 노드 삭제

 

  Note) 구현코드

<hide/>

#include <iostream>
using namespace std;

template <typename T>
class SNode 
{
public:
    SNode(T InValue)
        : Data(InValue)
        , Left(nullptr)
        , Right(nullptr)
    {
    }

    T Data;

    SNode* Left;

    SNode* Right;

};

template <typename T>
class SBinarySearchTree 
{
public:
    SBinarySearchTree()
        : Root(nullptr)
    {
    }

#pragma region Insert

public:
    void Insert(T InValue)
    {
        Root = InsertInternal(Root, InValue);
    }

private:
    SNode<T>* InsertInternal(SNode<T>* InNode, T InValue)
    {
        if (nullptr == InNode)
        {
            return new SNode<T>(InValue);
        }

        if (InValue < InNode->Data)
        {
            InNode->Left = InsertInternal(InNode->Left, InValue);
        }
        else if (InNode->Data < InValue)
        {
            InNode->Right = InsertInternal(InNode->Right, InValue);
        }

        return InNode;
    }

#pragma endregion

#pragma region Delete

public:
    void Delete(T InValue)
    {
        Root = DeleteInternal(Root, InValue);
    }

private:
    SNode<T>* FindMinInternal(SNode<T>* InNode)
    {
        while (InNode != nullptr && InNode->Left != nullptr)
        {
            InNode = InNode->Left;
        }

        return InNode;
    }

    SNode<T>* DeleteInternal(SNode<T>* InNode, T InValue)
    {
        if (nullptr == InNode)
        {
            return InNode;
        }

        if (InValue < InNode->Data)
        {
            InNode->Left = DeleteInternal(InNode->Left, InValue);
        }
        else if (InValue > InNode->Data)
        {
            InNode->Right = DeleteInternal(InNode->Right, InValue);
        }
        else
        {
            if (nullptr == InNode->Left)
            {
                SNode<T>* NewNode = InNode->Right;
                delete InNode;
                return NewNode;
            }
            else if (nullptr == InNode->Right)
            {
                SNode<T>* NewNode = InNode->Left;
                delete InNode;
                return NewNode;
            }

            SNode<T>* MinNode = FindMinInternal(InNode->Right);
            InNode->Data = MinNode->Data;
            InNode->Right = DeleteInternal(InNode->Right, MinNode->Data);
        }

        return InNode;
    }

#pragma endregion

#pragma region Search

public:
    bool Search(T InValue)
    {
        return Search(Root, InValue) != nullptr;
    }

private:
    SNode<T>* SearchInternal(SNode<T>* InNode, T InValue)
    {
        if (nullptr == InNode || InNode->Data == InValue)
        {
            return InNode;
        }

        if (InValue < InNode->Data)
        {
            return SearchInternal(InNode->Left, InValue);
        }
        else
        {
            return SearchInternal(InNode->Right, InValue);
        }
    }

#pragma endregion

#pragma region Traversal

public:
    void InOrderTraversal()
    {
        InOrderInternal(Root);
        cout << endl;
    }

private:
    void InOrderInternal(SNode<T>* InNode)
    {
        if (nullptr == InNode)
        {
            return;
        }

        InOrderInternal(InNode->Left);
        cout << InNode->Data << " ";
        InOrderInternal(InNode->Right);
    }

#pragma endregion

private:
    SNode<T>* Root;

};

 

  Note) 이진 탐색 트리의 문제점

    - 원소의 삽입 순서에 따라 이진 탐색 트리가 한쪽으로

      치우친 형태로 구성될 수도 있음.

    - 이럴 경우 트리의 높이 h = n - 1 형태로 구성됨.

      즉, 삽입/탐색/삭제 시간 복잡도 O(h) == O(n)으로 결정됨.

 

  Note) 해결 방법

    - 한쪽으로 치우친 트리의 구성을 변경하여

      균형 잡힌 트리 형태로 변경할 수 있음.

    - ex. AVL 트리, 레드-블랙 트리(Red-Black Tree),

      B 트리, 스플레이 트리(Splay Tree) 등등

저작자표시 비영리 변경금지

'C++ > 자료구조와 알고리듬' 카테고리의 다른 글

6. Linked list, Hash table  (0) 2022.12.30
5. Dynamic Programming, Backtracking  (0) 2022.12.01
4. Graph, DFS, BFS  (0) 2022.11.22
2. Sort, Search, Stack, Queue  (0) 2022.10.23
1. Recursive Function, Array  (0) 2022.10.21

관련글

댓글

티스토리툴바