이진탐색트리

코드:

#include <iostream>
using namespace std;

// 이진 탐색 트리의 노드 구조체
struct TreeNode 
{
    int key;// 노드의 값
    TreeNode* left;   // 왼쪽 자식을 가리키는 포인터
    TreeNode* right;  // 오른쪽 자식을 가리키는 포인터

    TreeNode(int val) : key(val), left(nullptr), right(nullptr) {}
};

// BST 클래스 정의
class BST 
{
public:
    TreeNode* root;

    BST() { root = nullptr; }

    // 노드 삽입 함수
    TreeNode* insert(TreeNode* node, int key) 
    {
        if (node == nullptr) 
        {  // 빈 자리면 새로운 노드 삽입
            return new TreeNode(key);
        }

        if (key < node->key)
        {  // key가 작으면 왼쪽으로 이동
            node->left = insert(node->left, key);
        }
        else if (key > node->key) 
        {  // key가 크면 오른쪽으로 이동
            node->right = insert(node->right, key);
        }

        return node;  // 부모 노드 반환 (트리 갱신)
    }

    void insert(int key) 
    {
        root = insert(root, key);
    }

    // 중위 순회 (오름차순 정렬 출력)
    void inorder(TreeNode* node) 
    {
        if (node == nullptr) return;

        inorder(node->left);
        cout << node->key << " ";
        inorder(node->right);
    }

    void printSorted()
    {
        inorder(root);
        cout << endl;
    }
};

int main() {
    BST tree;

    tree.insert(5);
    tree.insert(3);
    tree.insert(8);
    tree.insert(2);
    tree.insert(7);

    cout << "Sorted Tree: ";
    tree.printSorted();  // 정렬된 순서로 출력

    return 0;
}

"동적 연결 구조(Linked Structure)" 로 이루어진 자료구조

트리는 구조체나 클래스를 선언해서 관리하는게 정신건강에 이롭다.

구조체에는 트리노드의 값, 왼쪽, 오른쪽을 가리키는 포인터로 구성되어있다.

 

이진탐색트리는 부모보다 작으면 왼쪽, 크면 오른쪽으로 삽입한다.

삽입하면서 트리노드가 동적으로 생성된다. 

탐색 시간복잡도는 log n 

 

중위순회 (왼쪽 →루트 → 오른쪽) 

전위순회(왼쪽 → 오른쪽 → 루트)

후위순회(왼쪽 → 오른쪽 → 루트)

 

중요한건

중위순회(오름차순 정렬) / 후위순회(내림차순 정렬) 

 

이진탐색트리는 map이나 set에서 key값에 접근하는데 사용함.