이진 검색 트리🌳

-> I will walk you through the implementation of a binary search tree. Working with trees requires knowledge about pointers, the memory layout of a C program, memory allocation, and a good understanding of recursion.

-> We focus on binary search tree🌳 because this is a time-efficient data structure. We call it binary because every node can have at most two children. It is a search tree because it respects a particular condition which says that every node with a value smaller than the root node is going to be placed on the left of the root node, and every node with a value bigger than the root node is going to be placed in the right of the root node. This rule is applied recursively for every right subtree and left subtree.

-> Searching, accessing, inserting, and deleting in a binary search tree🌳 are usually done in O(log n). But there is a chance that a binary search tree can have a structure similar to a linked list, and the operations mentioned above will be done in O(n). This situation is a drawback for the tree data structure and it happens when every new node has either a smaller value than the last node, or a bigger value than the last node. Try to draw a binary search tree with these values: 10, 9, 8, 7, 6, 5, 4 및 다음 값으로 4, 5, 6, 7, 8, 9, 10 무슨 일이 일어나는지 확인하십시오.

-> 다행스럽게도 또 다른 tree🌳 데이터 구조인 AVL은 기존 트리를 개선한 것입니다. AVL은 자체 균형 트리이며 균형을 조정하면 트리가 연결 목록이 될 수 있는 상황을 피할 수 있습니다. 그러나 이것은 또 다른 논의입니다.

-> 자식이 둘 이상인 트리를 구현할 수 있지만 시간 복잡도는 변하지 않습니다. 로그 밑만 변경되지만 복잡도는 중요하지 않으므로 시간 복잡도는 최상의 경우 O(log n)이고 최악의 경우 O(n)입니다.

1. First step: creating a Node 데이터 유형

트리 데이터 구조로 작업하려면 새 데이터 유형인 Node 데이터 유형을 만들어야 합니다. Trees🌳는 노드를 사용합니다. 여기에서 우리는 Node 데이터 유형을 세 가지 속성을 갖는 것으로 정의합니다. 서명되지 않은 long long 변수 - 저장할 정보를 나타냅니다(기본 데이터 유형 또는 추상 데이터 유형도 될 수 있습니다. 단순성을 위해 기본 데이터 유형을 사용했습니다). 왼쪽 자식에 대한 참조와 오른쪽 자식에 대한 참조입니다.

struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};

2. Second step: generating Node 변수
Node 데이터 유형의 모양을 정의한 후 해당 유형의 변수를 생성할 수 있어야 합니다. 우리는 힙 메모리로 작업하고 있으므로 새 노드에 메모리를 동적으로 할당해야 합니다. 새 연산자는 데이터 유형 크기의 메모리를 요청합니다. 그런 다음 데이터 속성과 참조를 초기화합니다. nullptr 키워드는 C++에서 도입되었으며 0을 주소로 나타내고 주소로만 나타냅니다. nullptr은 포인터 유형의 키워드입니다. 반면에 NULL은 기본적으로 0이며 항상 포인터는 아닙니다. 앞으로 nullptr와 NULL의 차이점에 대해 포스팅하겠습니다. 우리는 포인터로 작업하고 있고 C++에 있기 때문에 nullptr을 사용하는 것이 좋습니다.

Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}

3. 3단계: 노드 삽입

After we defined how our Node 데이터 유형이 보이고 해당 유형의 변수를 만들 수 있는지 확인했습니다. 이진 검색 트리의 정의를 존중하는 방식으로 이러한 변수를 배치할 수 있어야 합니다. 이진 검색 트리에 삽입하는 함수를 만들 것입니다. 더 짧은 재귀 방법을 선호합니다. 해당 함수에 대한 두 가지 인수가 필요합니다. 루트 노드와 저장할 정보/객체입니다. 루트가 null이면 새Node 변수를 만들고 삽입해야 할 때임을 알 수 있습니다. 정보/객체의 값이 실제 루트 노드의 값보다 크면 오른쪽으로 이동합니다. 그렇지 않으면 왼쪽으로 이동합니다.

void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}

4. 네 번째 단계: 이진 검색 트리 인쇄

We created a Node 데이터 유형이며 Node 변수를 생성할 수 있고 올바르게 삽입할 수 있는지 확인했습니다. 이제 데이터 구조를 볼 수 있는 방법에 대해 생각해야 합니다. 이를 위해 깊이 순회 또는 폭 순회를 위한 알고리즘을 사용해야 합니다. 가능한 알고리즘에는 inorder, preorder, postorder 및 level order traversal의 네 가지가 있습니다. 이 예에서는 선주문을 사용합니다.

void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}


We are done. We have all pieces for working with a binary search tree.
Here is the complete code🔥:


#include <iostream>
using namespace std;


struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};


Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}


void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}


void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}


int main()
{
    Node* root = nullptr;
    unsigned long long i = 0, nodesNumber;
    cout << "Number of nodes to be added: "; cin >> nodesNumber; cout << '\n';

    while (i < nodesNumber)
    {
        unsigned long long number; cout << "Value of node: "; cin >> number; cout << '\n';
        InsertNode(root, number);
        ++i;
    }

    cout << "Binary search tree printed: "; Print(root);
    cout << '\n';

    return 0;
}

This is a basic structure. I wanted to give you the main idea. We can also create a Tree🌳 data type and think about Tree🌳 as an object with attributes rather than a simple variable called root. But from here, you can improve/change this implementation as you like. Feel free to explore.🗺️ and be curious.


❗Observations:

• I focused on the idea rather than on a real-world scenario where I must consider validations and other stuff.

• I have used C++ programming language.

• Emanuel Rusu👨‍🎓

• You can visit my GitHub

• Or you can find me on

• Next topic: Intern reprezentation of primitive data types

• See you next time! 👋