7-3. [C++] 이진 탐색 트리의 삽입 연산

이진 탐색 트리의 삽입 연산

앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다.

https://seongmoahn.tistory.com/100

7-2. [C++] 이진 탐색 트리의 탐색 연산

이진 탐색 트리에 새로운 노드를 삽입하기 위해서는 먼저 탐색을 수행해야 한다.

이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하며, 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 되기 때문이다.

탐색 과정에서 삽입하려는 노드의 키 값과 같은 키 값을 갖는 노드가 있다면 해당 노드는 삽입하지 않으면 된다.

탐색에 실패했다면 실패로 끝난 위치에 새로운 노드를 삽입하면 되는 것이다.

insert(root, node) // 이진 탐색 트리 삽입 알고리즘

if KEY(node) = KEY(root)
	then return ;
else if KEY(node) < KEY(root) then
	if LEFT(root) = NULL
    	then LEFT(root) <- node;
        else insert(LEFT(root), node);
else
	if RIGHT(root) = NULL
    	then RIGHT(root) <- node;
        else insert(RIGHT(root), node);

---

삽입 연산 구현

위 알고리즘을 바탕으로 이진 탐색 트리의 삽입 연산을 구현해보자.

// BiSearchTree.h
#include "BinaryTree.h"

class BiSearchTree : public BinaryTree {
public:
...    
    void insert(BinaryNode *newNode) {
        if (isEmpty()) root = newNode;
        else insert(root, newNode);
    }
    void insert(BinaryNode *rootNode, BinaryNode *newNode) {
        if (newNode->getData() == rootNode->getData()) return ;
        else if (newNode->getData() < rootNode->getData()) {
            if (rootNode->getLeft() == NULL) rootNode->setLeft(newNode);
            else insert(rootNode->getLeft(), newNode);
        }
        else {
            if (rootNode->getRight() == NULL) rootNode->setRight(newNode);
            else insert(rootNode->getRight(), newNode);
        }
    }
...
};

// BiSearchTree.cpp
#include "BiSearchTree.h"

int main() {
    BiSearchTree tree;

    BinaryNode *G = new BinaryNode(27, NULL, NULL);
    BinaryNode *F = new BinaryNode(31, G, NULL);
    BinaryNode *E = new BinaryNode(12, NULL, NULL);
    BinaryNode *D = new BinaryNode(3, NULL, NULL);
    BinaryNode *C = new BinaryNode(26, NULL, F);
    BinaryNode *B = new BinaryNode(7, D, E);
    BinaryNode *A = new BinaryNode(18, B, C);
    tree.setRoot(A);
    
    tree.search(9);

    BinaryNode *H = new BinaryNode(9, NULL, NULL);
    tree.insert(H);

    tree.search(9);

    return 0;
}

/*
실행 결과 :
key 값이 9인 노드 탐색 실패
key 값이 9인 노드 탐색 성공
*/

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.