데굴데굴

공부자료: 신찬수 교수님 '자료구조' 재생목록 자료구조 - 균형이진탐색트리 - 정의와 회전 - YouTube 이진탐색트리의 연산시간을 빠르게 하기 위해서는 트리의 높이를 최대한 작게 유지하는 것이 좋다. 여러 값이 추가되거나 삭제되더라도 높이를 O(log n)으로 유지할 수 있는 트리를 '균형이진탐색트리'라고 한다. 균형이진탐색트리의 종류는 세 가지가 있다. AVL 트리 Red Black 트리 Splay 트리 삽입과 삭제 연산을 수행하여 트리의 높이가 변할 때에는 높이를 O(log n)으로 유지할 수 있도록 높이를 조절해야 한다. 그리고 이는 rotation이라는 기본 연산으로 이루어진다. 왼쪽으로 회전하는 방법과 오른쪽으로 회전하는 방법 두 가지가 있다. rotation을 한 후에도 값의 순서가 이진탐..