목록트리 (1)

제이슨의 개발이야기

[면접준비] 자료구조 면접준비 2탄

AVL 트리 란 무엇인가? AVL 트리( Adelson-Velsky and Landis tree) 는 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진트리 입니다 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다 AVL 트리는 탐색,삽입,삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡습니다 레드 블랙 트리란 무엇인가? 레드 블랙 트리는 균형 이진 탐색 트리로 탐색 , 삽입 , 삭제 모두 시간 복잡도가 O(logn)입니다 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 , 삽입 및 삭제 중에 트리가 균형을 유지하도록 ..
면접준비 2022. 11. 21. 17:23
이전 Prev 1 Next 다음