.

그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork

균형이진트리 등장배경

• BST는 일반적으로 인서트, 서치, 딜리트가 O(log n)으로 처리하는 좋은 구조이다.

• 그러나 BST는 키값을 어떻게 넣느냐에 따라 아래와 같이 최악의 경우로 구성되는 경우가 있다. 이 경우 O(n)이 된다. 이것은 우리가 원하는 자료구조가 아니다.

데이터를 어떻게 넣든지 자기가 균형있게 구현하는게 균형이진트리이다.

“노드가 insert 되거나 delete되면 알아서 균형을 맞춰줄 수는 없을까?”라는 고민에서 나온 아이디어다.

균형이진트리 종류

1) AVL

2) 레드블랙 트리

3) B tree

4) B+ tree

5) 2-3 tree

6) 2-3-4 tree

5),6)은 Btree의 특수한 케이스이다.