제이슨의 개발이야기

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

안녕하세요 제가 요즘 면접 준비하고 있어서 자료구조 관련 면접 질문 대비를 해보려구 합니다! 1. 시간 복잡도 란? 시간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값 2. 공간 복잡도 란? 공간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 공간이 필요한 지에 대한 값 3. 연결리스트에 대해서 설명하기 { 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조 입니다. 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸립니다 연결 리스트에는 3종류가 있는대 1. 싱글 연결 리스트 : 다음 노드의 주소만 가지고 있다 2. 이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있고 가장 첫번째 노드의 이전 주소값은 null 마..