https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search%20Tree
https://hongku.tistory.com/160

Binary Search Tree (BST)

이진 탐색 트리는 이진트리 중 특별한 종류로 삽입과 삭제를 효율적으로 하여 정렬된 트리를 만든다.

항상 정렬된 속성

다음은 유효한 이진 탐색 트리의 예제이다.

왼쪽 자식은 항상 부모보다 작고, 오른쪽 자식은 항상 부모보다 크다.

새로운 노드의 삽입

루트 노드를 기준으로 작은 값을 왼쪽 자식에, 큰 값을 오른쪽 자식에 넣는다.

9를 넣는다고 하면, 7보다 크니까 오른쪽 노드로 가고 10보다 작으니까 왼쪽 노드로 가서 다음과 같이 된다.

순회

• 전위 순회(pre-order)

부모 -> 왼쪽 자식 -> 오른쪽 자식 순으로 순회한다.

• 중위 순회(in-order)

왼쪽 자식 -> 부모 -> 오른쪽 자식 순으로 순회한다.

• 후위 순회(post-order)

왼쪽 자식 -> 오른쪽 자식 -> 부모 순으로 순회한다.

삭제

하나의 노드를 삭제하면 왼쪽 자식중 가장 큰 값 또는 오른쪽 자식 중 가장 작은 값으로 대체한다.

따라서 figure 2 또는 3으로 대체된다.