2.4.4 균형 트리

균형 트리(balanced tree)에 대해 설명하기에 앞서, 먼저 BST에 다음과 같은 순서로 원소를 삽입하는 경우에 대해 생각해보겠습니다.

bst tree;
tree.insert(10);
tree.insert(9);
tree.insert(11);
tree.insert(8);
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);

이렇게 구성된 BST를 그림으로 표현하면 다음과 같습니다.

▲ 그림 2-10 편향된 이진 검색 트리