BST ( Binary Search Tree )

각각의 노드는 최대 2개의 자식을 가질 수 있으며, 검색 하는데 O(log(n))의 시간이 소요 됨

BST와 일반 binary tree 의 차이점

1. 모든 노드들의 왼쪽 서브트리 값은 루트 노드보다 작다.
2. 모든 노드들의 오른쪽 서브트리 값은 루트 노드보다 크다.
3. 서브 트리들도 각각 위 2가지 조건 만족한다.

• 값이 루트보다 작을 경우 오른쪽 서브트리에 없음을 확신할수 있음
• 값이 루트보다 작으면 왼쪽 하위트르에서 검색하고, 값이 루트보다 클 경우 오른쪽 하위 트리에서 검색하면 되므로 log시간에 탐색 가능하다.

delete

총 3가지의 케이스를 처리해 줘야 함

case1: leaf노드일 경우 값을 탐색하고 그냥 제거하면 됨

case2: single child일 경우 노드 값을 자식 값으로 바꾸고 자식 노드를 제거하면 됨

case3: 2 child일 경우 ( 코드 참고 )

struct Node
{
    int key;
    Node *left, *right;

    Node(int key, Node *left, Node *right)
    {
        this->key = key;
        this->left = left;
        this->right = right;
    }
};

Node* insert(Node *node, int key)
{
    if (node == nullptr)
    {
        return new Node(key, nullptr, nullptr);
    }
    if (key < node->key)
    {
        node->left = insert(node->left, key);
    }
    else
    {
        node->right = insert(node->right, key);
    }

    return node;
}

Node* deleteNode(Node *node, int key)
{
    if (node == nullptr) // endpoint
    {
        return node;
    }

    if (key < node->key)
    {
    	// 현재 노드의 키보다 더 작으므로 왼쪽으로 이동
        node->left = deleteNode(node->left, key); 
    }
    else if (key > node->key)
    {
    	// 현재 노드의 키보다 더 크기 때문에 오른쪽으로 이동
        node->right = deleteNode(node->right, key);
    }
    else // 현재 노드와 찾는 키가 일치 !
    {
    
       	// case1 : leaf노드일 경우 값을 탐색하고 그냥 제거하면 됨
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        
        // case2: single child일 경우 노드 값을 자식 값으로 바꾸고 자식 노드를 제거하면 됨
        if (node->left == nullptr || node->right == nullptr)
        {
            Node *tmp = node->left ? node->left : node->right;
            delete node;
            return tmp;
        }
        
		// case3: 2 child일 경우 
        else if (node->left)
        {
            Node *tmp = node;
            tmp = tmp->left;
            while (tmp->right != nullptr)
            {
                tmp = tmp->right;
            }
            node->key = tmp->key;
            node->left = deleteNode(tmp->left, tmp->key);
        }
    }
    return node;
}

void inorderTravle(Node *root)
{
    if (root == nullptr)
    {
        return;
    }

    inorderTravle(root->left);
    cout << root->key << endl;
    inorderTravle(root->right);
}

int main()
{
    Node *root = nullptr;
    root = insert(root, 8);
    root = insert(root, 1);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 3);
    root = insert(root, 5);
    root = insert(root, 88);

    inorderTravle(root);
    cout << endl;
    deleteNode(root, 88);
    deleteNode(root, 1);
    deleteNode(root, 88);
    inorderTravle(root);
    return 0;
}

Time Complexity

n is the number of nodes in the tree.

Operation	Best Case Complexity	Average Case Complexity	Worst Case Complexity
Search	O(log n)	O(log n)	O(n)
Insertion	O(log n)	O(log n)	O(n)
Deletion	O(log n)	O(log n)	O(n)

Binary Search Tree Applications

1. In multilevel indexing in the database
2. For dynamic sorting
3. For managing virtual memory areas in Unix kernel