lsh424

AVL트리 역시 레드-블랙 트리와 마찬가지로 자가 균형 이진 탐색 트리입니다. 레드-블랙 트리와 다른 점은 균형(balance)을 유지하기 위해 적용하는 조건이 다른데요. 그래서 같은 자가 균형 이진 탐색 트리이지만 같은 키를 삽입해도 트리의 결과는 다르게 나올 수 있습니다. ex) KEY = [2, 1, 8, 9, 7, 3, 6, 4, 5] 삽입 시 AVL트리 조건은 다음과 같습니다. 1. *높이 차가 2 이상이 되면 회전을 통해 높이차를 1 이하로 유지 * 높이 차 = 오른쪽 서브 트리의 높이 - 왼쪽 서브 트리의 높이 조건은 엄청 간단하죠?? 여기서 높이 차에 대해 예시를 통해 설명드리자면 각각의 노드 옆에 높이차를 적게 되는데, 이 높이 차는 해당 노드의 우측 서브 트리 높이- 왼쪽 서브 트리 높..

오늘 알아볼 자료구조는 리스트입니다 :) 리스트란? 순서를 가지고 일렬로 나열한 원소들의 모임으로 데이터 목록을 다루는 자료구조로 기본 연산으로는 삽입, 삭제, 탐색이 있습니다. 리스트 구현 방법 1. 배열 이용 (순차적인 메모리 공간 할당) 2. 연결 리스트 이용 (노드에 분산 저장) 리스트의 연산 init(list) - 리스트 초기화 is_empty(list) - 리스트 공백 유무 검사 is_full(list) - 리스트 포화상태 유무 검사 insert(list, pos, item) - pos 위치에 item 추가 insert_last(list, item) - 리스트 맨 끝에 item 추가 delete(list, pos) - pos 위치의 요소 제거 get_entry(list, pos) - pos 위..

우리 주변을 살펴보면 많은 부분에 있어 규칙이 정해져 있고, 조직화되어 있는 것을 볼 수 있습니다. 이렇게 하는 이유는, 효율적이기 때문인데요. 예를 들면 해야할 일을 리스트로 정리한다던가, 매표소에서 줄을 서서 구매하는 것 등등 여러 가지가 있습니다. (만약 매표소에서 줄을 서지 않고 표를 구매할 수 있다면, 엉망진창이 되겠죠?) 일상에서 볼수 있는 예와 자료구조를 비교해보면 아래와 같이 나타 낼 수 있습니다. 우리가 만들게 되는 프로그램은 적절한 자료구조와 알고리즘으로 이뤄집니다. 그래서 많은 회사들이 자료구조와 알고리즘을 중요하게 생각하는 것이죠! 만약 최대값을 찾는 프로그램을 작성한다고 가정해봅시다. 최댓값을 찾는 프로그램의 경우 다양한 방법이 있겠지만, 배열이라는 자료구조와 순차탐색이라는 알고리..