홍시홍의 프로그래밍

1. AVL이란 BST의 단점(한쪽으로 치우치는 것)을 보완하기 위해 만들어진 균형 잡힌 이진 트리 각 노드의 BF(벨러스 백터) (왼쪽 서브 노드 높이 - 오른쪽 서브 노드 높이)가 -1,0,1 이 되어야한다. 2. 특징 균형 이진 트리를 유지하기 위해서 LL , RR, LR, RL 4가지의 경우 처리할 방법이 있다 LL은 오른쪽으로 이동 -> 현재 노드의 왼쪽 서브 트리 왼쪽에 삽입이 일어났을 경우 RR은 왼쪽으로 이동 -> 현재 노드의 오른쪽 서브 트리 오른쪽에 삽입이 일어났을 경우 LR 은 왼쪽으로 이동 후 오른쪽 -> 현재 노드의 왼쪽 서브트리 오른쪽에 삽입이 일어났을 경우 RL은 오른쪽으로 이동 후 왼쪽 -> 현재 노드의 오른쪽 서브트리 왼쪽에 삽입이 일어났을 경우 단점 삽입, 삭제가 빈번할 ..

1. 트리란 그래프의 일종으로 계층적인 구조를 지니는 자료 구조 * 결정 트리 : 인공지능에서 사용 주요 개념 노드, 루트, 서브트리, 간선, 부모 노드, 자식 노드, 형제 관계, 조상 노드, 자손 노드, 단말 노드, 트리의 높이 2. 이진 트리 : 공집합이거나, 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 트리 - 이진 트리의 성질 : n개의 노드 n-1개의 간선(그래야지 모두가 중복되지 않고 연결되있음) - 이진 트리의 높이 : 최대 2^h -1 h는 높이 3. 순회의 종류 - 전위 순회 : VLR 부모 먼저 계산 하고 싶을 때 - 중위 순회 : LVR 디렉토리 용량 계산 - 후위 순회 : LRV 자식 먼저 계산하고 싶을 때 4. 스레드 이진 트리 - 중위 순회 시 L쪽에 상단 위치를 저장하여 순회..

20190507 - 시간복잡도 추가 1. 연결리스트란 데이터 필드, 링크 필드로 구성되며, 자료 중간에 삽입이 쉬운 자료구조 데이터 이외에 링크 필드도 필요하므로 메모리가 더 소요된다 배열에 비해 삽입, 삭제가 간편하다 2. 연결리스트의 종류 2.1 단순 연결 리스트 - 헤드 포인트를 가진다 - 마지막 노드의 링크는 NULL을 참조한다 2.2 이중 연결 리스트 - 데이터 필드 하나와 두개의 링크 필드를 가진다. 2.3 원형 연결 리스트 - 단순 연결 리스트의 마지막 노드의 링크 필드를 헤드로 가르치면 원형 연결 리스트가 된다. 3. 시간 복잡도 - 일반 배열은 배열 삽입/삭제 하는데 O(n)이 드는 방면, 리스트는 O(1)에 가능 - 링크 필드만 재연결 및 삭제 해주면 된다

1. Queue란? First in First out 2. Queue의 특징 선입선출로 사용처는 - 스케쥴러 - bfs - 대기 순서에 따른 처리가 있다