BST 일반적인 삽입 과정

다음과 같은 BST에 50이라는 데이터를 삽입하려 한다.

삽입과정은 매우 재귀적이다

 

성능

트리의 밸런스가 잘 맞을 경우 → O(logN)

트리의 편향이 심할 경우 → O(N)

 

삽입 과정

•삽입하려는 노드와 루트노드를 비교한다

•삽입하려는 노드가 더 크다 → 오른쪽 서브트리에 반복(=재귀)

•삽입하려는 노드가 더 작다 → 왼쪽 서브트리에 반복 (=재귀)

이 과정에서 서브트리가 비어있다면, 그 위치에 삽입한다

 

→ 50이 더 크다. 그러므로 오른쪽 서브트리에 이 과정을 반복한다

→ 50이 더 크다. 마찬가지로 오른쪽 서브트리에 반복한다

→ 50이 더 작다. 왼쪽 서브트리에 반복한다 → 그런데 왼쪽 서브트리가 비어있다 → 왼쪽 노드로 삽입한다

→ 완료