<BST> Binary Search Tree

이진 탐색 트리 검색

이진 탐색 트리는 한 노드를 기준으로 왼쪽 자식 노드를 루트로 하는 서브 트리의 모든 노드 값은 현재 노드보다 작은 값을 갖고 오른쪽 자식 노드를 루트로 하는 서브 트리의 모든 노드 값은 현재 노드보다 큰 값을 갖는다.

이진 탐색 트리 삽입

삽입할 노드가 들어갈 위치를 찾고($O(logN)$) 현재 노드보다 작으면 왼쪽 크면 오른쪽에 삽입

이진 탐색 트리 삭제

삭제도 삽입과 마찬가지로 먼저 삭제할 노드의 위치를 찾는다.
찾은 후에 아래 3가지 경우로 나뉘게 된다.

삭제할 노드의 자식이 0개인 경우

리프 노드를 제거하는 것이므로 부모 노드와 자식 노드의 관계를 끊어주기만 하면 된다.

삭제할 노드의 자식이 1개인 경우

삭제할 노드의 부모 노드와 삭제 할 노드의 자식 노드를 이어준다. 한개이므로 이진 트리를 벗어나지 않는다.

삭제할 노드의 자식이 2개인 경우

• 1. 삭제 대상 노드를 삭제한다.
• 2. 삭제 대상 노드의 자리를 대신할 노드를 찾아야 한다.
• 3. 왼쪽 자식 노드를 루트로 하는 서브 트리의 모든 값보다는 크고 오른쪽 자식 노드를 루트로 하는 서브 트리의 모든 값보다는 작아야 한다. 즉 왼쪽 서브 트리의 최대 값이나 오른쪽 서브 트리의 최소 값이 삭제된 노드를 대신할 수 있다.
• 4-1. 이진 탐색 트리의 최소 값은 왼쪽 자식을 타고 가다가 리프 노드가 나오면 된다.
• 4-2. 이진 탐색 트리의 최대 값은 오른쪽 자식을 타고 가다가 리프 노드가 나오면 된다.
• 5. 4-1과 4-2중 한 값으로 삭제된 노드를 대신하면 삭제 과정이 완료된다.