728x90 반응형 균형 이진 탐색 트리1 트리(Tree) 자료구조의 확장인 AVL 트리와 레드-블랙 트리 AVL 트리(AVL Tree)와 레드-블랙 트리(Red-Black Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 균형을 유지하여 검색, 삽입, 삭제 연산의 성능을 보장하는 균형 이진 탐색 트리(Balanced Binary Search Tree)의 대표적인 예입니다. AVL 트리는 모든 노드의 서브트리 높이 차이가 1 이하로 유지되도록 설계되었으며, 레드-블랙 트리는 색상을 이용하여 균형을 유지합니다. 이러한 균형 트리는 최악의 경우에도 O(log n)의 시간 복잡도로 연산을 수행할 수 있게 합니다. AVL 트리와 레드-블랙 트리의 등장 배경기본 이진 탐색 트리는 특정 입력 순서에 따라 편향될 수 있어, 최악의 경우 O(n) 시간 복잡도를 가질 수 있습니다. 이를 해결하기 .. 2024. 11. 19. 이전 1 다음 728x90 반응형
