BST2 [MIT 6.006 정리] Lec 06. 균형 이진 탐색 트리, AVL 트리 * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 이진 탐색 트리 (BST) Recap 이진 (binary) & 트리 (tree) 구조 -- 각 노드가 해당하는 키(key) 값과 왼쪽 / 오른쪽 자식 노드를 가리키는 포인터(pointer) 를 가짐 Search property (= BST property) 를 가짐 -- 모든 노드에 대해 해당 노드를 기준으로 왼쪽 / 오른쪽에 위치한 모든 서브 트리는 해당 노드보다 작거나 같음 / 크거나 같음 이진 탐색 트리 구조에 저장된 자료들의 (정렬.. 2021. 2. 28. [MIT 6.006 정리] Lec 05. 이진 탐색 트리 * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * Why Binary Search Tree needed? -- 예시: 비행기 활주로 예약 시스템 (Runway Scheduling System) 활주로가 하나 뿐인 공항을 가정. 해당 활주로에 다음 비행기의 착륙 요청(landing request) 을 예약하는 시스템 다음 비행기가 특정 착륙 시각 t 에 대해 착륙 요청을 했을 때, 해당 시간 t 로부터 k 분 안에 다른 착륙 스케쥴이 없다면(제약 조건), 이미 예약 완료된 착륙 시각들의 집.. 2021. 2. 9. 이전 1 다음