👣 개요
자료 구조가 일렬로 나열된 형태의 구조가 아닌 Tree나 Graph와 같은 형태로 존재하는 것을 일컫음.
👣 그래프
정점과 간선으로 이뤄진 자료 구조.
👣 그래프 표현 방법 - 인접 행렬
i번째 노드와 j번째 노드가 연결되면 해당 간선의 가중치를 (i, j) 셀에 기입.
👣 그래프 표현 방법 - 인접 리스트
각 노드가 연결된 노드를 리스트로 표현
👣 트리
그래프의 일종으로 부모, 자식 계층의 구조를 가지고 있다.
그리고 간선 사이의 가중치가 없다. 오로지 연결 여부만 나타낼 뿐이다.
👣 이진 트리
트리의 일종으로 자식 노드 수가 2개 이하인 트리.
Full
자식노드가 0 또는 2개인 이진 트리. 쉽게 말해서 1개 짜리 자식노드가 없다는 것.
Complete
왼쪽부터 차곡차곡 채워진 트리.
Degenerate
자식 노드가 모두 1개 밖에 없는 이진 트리.
Perfect
모든 노드가 꽉 차있는 이진 트리.
Balanced
왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리.
👣 이진 탐색 트리
이진 트리의 일종으로 부모 노드의 값을 기준으로
왼쪽 자식노드는 부모 노드값보다 작고
오른쪽 자식노드는 부모 노드값보다 크다.
해당 트리는 최악의 경우, 그냥 연결리스트가 되어 탐색 속도가 느려질 수 있다.
👣 AVL 트리
AVL 트리
이진 탐색 트리의 최악의 경우를 피하기 위해 스스로 균형있는 트리로 변형되는 이진 탐색 트리. AVL 트리는 모든 노드의 Balence Factor가 [-1, 0, 1]이어야 한다. Balance Factor 왼쪽 자식 노드가 루트 노
ikadnorth.tistory.com
👣 레드 블랙 트리
레드 블랙 트리
균형 이진 탐색 트리를 위해 고안된 자료 구조. 각 노드는 빨간색, 검은색 색상을 나타내는 추가 비트를 저장하며, 삽입, 삭제 중에 균형을 유지하기 위해 사용된다. 레드 블랙 트리 규칙 1. 모든
ikadnorth.tistory.com
👣 힙
Heap
완전 이진 트리의 자료 구조. 이진 탐색 트리는 아니다. 최소힙과 최대힙으로 나뉠 수 있다. 해당 트리는 최소값, 최대값을 찾기에 특화되어 있는 자료 구조다. 최소값과 최대값은 각각 최소힙과
ikadnorth.tistory.com
👣 해시
Hash Table
(Key, Value) 로 데이터를 저장하는 자료 구조. 해시 함수에 Key 값을 입력하면 Value를 저장할 메모리의 Index가 결과값으로 도출된다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 랜덤 탐
ikadnorth.tistory.com