Jump into BST

이진트리 구조에 특수한 규칙을 적용한 트리입니다. 부모 노드를 기준으로 왼쪽 자식 노드에는 작은 값의 노드가 삽입되고, 오른쪽 자식 노드에는 큰 값이 삽입 됩니다.

Basic aspects of BST:

1. 좌우의 균형이 맞으면, 탐색, 삽입, 제거의 시간복잡도가 log(n)으로 상당히 빠른 편에 속한다.
2. 삽입되는 순서에 따라 트리가 달라진다.
3. 한쪽으로 치우친 skewed Tree 형태가 되면, 탐색, 삽입, 제거의 시간복잡도가 o(n)이 된다.
4. 숫자가 삽입된 노드를 기준으로 왼쪽 서브 트리에는 기준 값보다 모두 작은 값을 가진 노드가 있으며, 반대로 오른쪽에는 큰 값을 가진 노드만이 연결된다.
5. 자료의 중복이 허용되지 않는다.

Method:

탐색: log(n)

• 루트 노드를 기준으로 찾고자하는 값과 대소 관계를 파악한다.(탐색 시작)
• 같은 값을 가진 노드가 발견되면, True 를 리턴한다.
• 찾고자 하는 값이 노드의 값보다 작으면 왼쪽 노드로 이동한다.
• 찾고자 하는 값이 노드의 값보다 크면 오른쪽 노드로 이동한다.
• 더 이상 내려 갈 수 없는 마지막 노드에 도달하면 False를 반환한다.

삽입: log(n)

• 탐색과 같이 루트 노드를 기준으로 값의 대소관계를 가려 더 이상 아래로 이동할 수 없는 노드까지 도달하면 그 자리에 삽입한다.(부모노드와, 부모노드에서 이동된 방향 필요) note: 단, 같은 값이 발견되면 즉시 False를 반환한다.

제거: log(n)

• case 1. 제거하고자하는 노드가 자식 노드를 가지고 있지 않은 경우 => 부모 노드와의 연결을 끊는다.

• case 2. 제거하고자하는 노드가 한 개의 자식 노드를 가지고 있는 경우 => 부모 노드와 자식노드의 자식노드를 연결한다.

  • 부모노드에서 연결된 방향과 자식노드에서 연결된 자식노드의 방향을 고려해서 총 4가지의 경우가 생긴다.
• case 3. 제거하고자하는 노드가 두 개의 자식 노드를 가지고 있는 경우 => 제거하려는 노드의 오른쪽 서브 트리에서 가장 작은 값을 가진 노드로 대체 or 제거하려는 노드의 왼쪽 서브 트리에서 가작 큰 값을 가진 노드로 대체한다.