• 각 노드는 key를 갖는다. key에 데이터가 저장된다.
• 각 노드는 다른 노드에 대한 포인터 L, R을 갖는다.
• L은 왼쪽 자식 노드, R은 오른쪽 자식 노드를 가리키는 포인터이다.
• 자식 노드가 없다면 포인터에 NULL이 저장된다.
• 트리의 최상위 노드는 루트라고 부른다.

1. 키값으로 X를 가지는 노드 A가 BST에 존재한다면, Search(X, root)는 A의 주소값을 리턴한다.
• 이는 다음을 통해 증명된다 :
• Search(X, N) 이 호출될 때, N을 루트로 하는 서브트리 내에 A가 존재함을 먼저 증명하자. (N은 임의의 노드)
• Base : Search(X, root)부터 시작한다. 트리 내에 A가 존재한다고 가정하였으므로, root를 루트 노드로 하는 서브트리, 즉 전체 트리 내에 A가 존재한다.
• Step : Search(X, N)에서, N을 루트로 하는 서브트리 내에 A가 존재한다고 가정한다.
• N의 왼쪽 서브트리에 A가 존재한다면, 이진 탐색 트리의 특성에 의해 X < N->key 가 참이 된다. 따라서 N의 왼쪽 자식 노드에 대해 재귀 호출되고, 다음 호출에서도 서브트리 내에 A가 존재하게 된다.
• N의 오른쪽 서브트리에 A가 존재하는 경우에도, 마찬가지 이유로 다음 호출에도 가정이 참이 된다.
• N==A라면, X == N->key가 참이 되고, A의 주소값이 리턴되어 알고리즘이 올바르게 작동을 마친다.
• 따라서 Search(X, N)이 수행될 때 무조건 N을 루트로 하는 서브트리 내에 A가 존재하게 되며, 서브트리의 크기는 재귀 호출될 때마다 계속 작아지므로, 결국 A가 리턴된다.
2. 키값으로 X를 가지는 노드가 BST에 없다면, Search(X, root)는 NULL을 리턴한다.
• 노드의 키 값이 인수로 주어진 값과 같을 때만 주소값이 리턴된다. 그런 노드가 존재하지 않고, 자식 노드를 타고 내려가다 보면 N에 NULL이 들어가게 되므로, 결국 NULL이 리턴된다.

• 높이가 H인 특정한 Tree를 가정했을 때
• 최악의 경우 O(H)가 걸린다.
• 모든 생성 가능한 Tree에 대해서
• 
  
• 위와 같이 노드가 수직 방향으로 일렬로 배열된 트리가 최악의 경우이다.
• 이 경우 H=N-1이므로, O(N)이 걸린다.

void Insert(int X, Node* N = root, Node **RP = &root)
{
    Node *new_node;
    if(N == NULL) {
        new_node = new Node;
        new_node->key = X; new_node->left = new_node->right = NULL; *RP = new_node;
    }
    else {
        if(N->key < X) return Insert(X, N->right, &(N->right));
        else if(N->key > X) return Insert(X, N->left, &(N->left));
        else return;  // 중복된 키값이 있으면 Insert 취소
    }
}

• 먼저 Search()를 수행한다.
• 만약 Search()가 실패하면, Delete를 하지 않고 함수를 종료한다.
• 만약 Search()에 성공해 지울 노드 N을 찾았다면, 다음 세 가지 case를 고려해야 한다.
1. 지울 노드의 자식이 없는 경우
• N의 부모 노드의 포인터에 NULL을 대입하고, N을 메모리에서 해제하여 삭제하면 된다.
2. 지울 노드의 자식이 1개인 경우
• N의 부모 노드의 포인터에 N의 자식 노드를 대입하고, N을 메모리에서 삭제한다.
3. 지울 노드의 자식이 2개인 경우
• Tree의 모든 노드를 sorting된 상태에서 일렬로 배열하면, 노드 N 바로 다음에 노드 x가 온다고 하자.

• x는 N의 오른쪽 자식 노드에서 왼쪽으로만 최대한 타고 내려간 위치에 존재한다.
• 
  
• 노드 x의 키값을 N의 키값에 대입하고, x노드에 대해 Delete연산을 재귀 호출한다. x노드는 자식이 없거나 1개이므로 case 1, 2의 방법으로 지울 수 있다.
• 
  

// parent는 N의 부모 노드를 가리킴
int Delete(Node *N, Node *parent)
{
    if(N->left == NULL && N->right == NULL) {
        if(parent->left == N) parent->left = NULL;
        else parent->right = NULL;
        delete N;
    }else if(N->left == NULL || N->right == NULL) {
        if (parent->left == N) {
            if(N->left != NULL) parent->left = N->left;
            else parent->left = N->right;
        }
        else {
            if(N->left != NULL) parent->right = N->left;
            else parent->right = N->right;
        }
        delete N;
    }else {
        // 일렬로 배열했을 때 노드 N 바로 다음에 오는 노드를 next_N이라 하고
        // next_N의 부모 노드를 next_N_parent라 한다.
        Node* next_N = N->right;
        Node* next_N_parent = N;
        while(next_N->left != NULL) {
            next_N_parent = next_N;
            next_N = next_N->left;
        }
        N->key = next_N->key;
        Delete(next_N, next_N_parent);
    }
}

1. 자식이 없는 노드를 지우는 경우
• 어떤 노드가 삭제되었을 때, 임의의 노드 x의 왼쪽 서브트리에 x보다 키값이 큰 노드가 생기거나, x의 오른쪽 서브트리에 x보다 키값이 작은 노드가 생길 수는 없다.
• 자식이 없는 노드를 지울 때는 단순히 그 노드를 삭제하므로, 이진 탐색 트리 특성이 깨지지 않는다.
2. 자식이 한 개인 노드 N을 지우는 경우
• N의 부모 노드를 P, 자식 노드를 C라 하자.
• 
  
• N이 P의 왼쪽 자식이라면, 이진 탐색 트리의 특성에 의해, N을 루트로 하는 서브트리의 모든 노드는 키값이 P보다 작다.
• 따라서 C를 루트로 하는 서브트리의 모든 노드는 키값이 P보다 작다.
• 또한 C를 루트로 하는 서브트리는 그 자체로 이진 탐색 트리 특성을 만족한다.
• 따라서 N을 지우고, 그 자리에 C를 루트로 하는 서브트리가 와도 이진 탐색 트리 특성이 유지된다.
• N이 P의 오른쪽 자식인 경우도 마찬가지 원리로 이진 탐색 트리 특성이 유지됨을 증명할 수 있다.
3. 자식이 두 개인 노드 N을 지우는 경우
• N의 오른쪽 자식 노드에서 출발하여 왼쪽으로만 최대한 타고 내려갈 경우, 노드 x에 도달하게 된다고 하자.
• x는 N보다 키값이 큰 노드들 중에서 가장 키값이 작은 노드이다.
• 증명은 다음과 같다.
• N외의 노드를 N의 왼쪽 서브트리의 노드, N의 오른쪽 서브트리의 노드, 그 외 N의 조상 노드와 그것의 자손 노드로 구분할 수 있다. 각각의 노드에 대해 N보다 키값이 작거나, x보다 크다는 것을 증명할 것이다.
• case 1) N의 왼쪽 서브트리의 노드는 모두 N보다 키값이 작다.
• case 2) N의 오른쪽 서브트리의 노드는 모두 N보다 키값이 크다.
• 여기서 x는 서브트리에서 가장 키값이 작다. 서브트리 내 임의의 노드의 오른쪽 자식 노드는 부모보다 키값이 크기 때문에 가장 작은 노드가 될 수 없고, x의 부모들도 모두 x보다 크기 때문이다.
• case 3) N의 임의의 부모 노드 P에 대해, N이 P의 오른쪽 서브트리에 존재한다면 P의 키값은 N보다 작다. P의 왼쪽 서브트리의 노드도 전부 N보다 작다.
• 
  
• N이 P의 왼쪽 서브트리에 존재한다면 P의 키값은 N보다 크다. 그런데 x도 P의 왼쪽 서브트리에 포함되므로 P의 키값은 x보다 크다. P의 오른쪽 서브트리의 노드도 x보다 키값이 크다.
• 
  
• 따라서 (어차피 삭제될 노드 x를 고려하지 않으면) N의 키값을 x의 키값으로 고쳐도 이진 탐색 트리 특성이 유지된다.
• x는 자식이 한 개 이하이므로, 재귀 호출을 통해 이진 탐색 트리 특성을 유지하도록 삭제가 이루어진다.