[c++] 균형 잡힌 이진 트리 검색 알고리즘

15 Dec 2023

이진 탐색 트리에서의 검색 알고리즘은 일반적으로 반복문을 사용하여 구현됩니다.

Node* search(Node* root, int key) {
    while (root != nullptr && root->key != key) {
        if (key < root->key)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

균형 잡힌 이진 트리의 검색 알고리즘은 AVL 트리에서 사용되는 회전 연산 등의 추가적인 균형 조정 작업이 필요할 수 있습니다.

AVL 트리의 검색 알고리즘은 다음과 같이 구현될 수 있습니다.

Node* searchAVL(Node* root, int key) {
    if (root == nullptr || root->key == key)
        return root;
    if (key < root->key)
        return searchAVL(root->left, key);
    else
        return searchAVL(root->right, key);
}

따라서, 균형 잡힌 이진 트리에서의 검색 알고리즘은 기본적으로 이진 탐색 트리의 검색 알고리즘과 유사하며, AVL 트리에서의 추가적인 균형 유지 작업을 고려해야 합니다.

관련 참고 자료:
AVL 트리: https://en.wikipedia.org/wiki/AVL_tree
이진 탐색 트리: https://en.wikipedia.org/wiki/Binary_search_tree