c++/자료구조 간단 이론6 레드-블랙 트리(Red_Black_Tree) 레드-블랙 트리 레드 블랙 트리는 자가 균형 이진 탐색 트리입니다. 탐색(Search) 연산의 시간 복잡도 O(logN) 레드 블랙 트리는 아래의 조건을 항상 만족해야 합니다. 1. 루트 노드는 블랙이다. 2. 모든 리프 노드는 블랙이다. 3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (No Double Red) 4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다 노드 삽입 과정 노드의 삽입은 항상 빨간색 단 루트노드 제외 첫 번째 노드 삽입 (루트 노드는 항상 블랙 노드) 2, 8 노드 삽입 노드 삽입은 항상 빨간색 3 노드 삽입 3번 조건 위배되는 상황 발생 (Double Red) 이중 레드 (Double Red) 문제 해결 Restructuring .. c++/자료구조 간단 이론 2023. 5. 31. 이분 탐색 이분 탐색이란? - 정렬된 배열에서 원하는 값의 존재 여부를 찾는 알고리즘. - 반드시 배열을 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. 시간복잡도 : O(log N) 탐색 방식 - 전체 배열의 중간 요소를 찾고자 하는 키로 시작합니다. - 찾고자 하는 키의 값이 항목과 같으면 찾고자 하는 키의 인덱스를 반환합니다. - 또는 찾고자 하는키의 값이 Mid보다 작으면 End = Mid - 1으로 좁힙니다. - 그렇지 않으면 Start = Mid + 1으로 좁힙니다. - 두 번째 지점부터 값을 찾거나 간격이 비어 있을 때까지 반복적으로 확인합니다. 출처 : https://www.geeksforgeeks.org/binary-search/ Binary Search -.. c++/자료구조 간단 이론 2022. 11. 3. deque 정의 및 시간복잡도 deque 정의 앞, 뒤 전부 삽입 삭제가 가능함 Restricted Structure 시퀀스 컨테이너이자, 배열 기반 컨테이너입니다 시간복잡도 1. 원소의 추가O(1) 2. 원소의 제거O(1) 3. 제일 앞/뒤의 원소 확인O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 (단, stl deque에는 인덱스로 접근이 가능함) c++/자료구조 간단 이론 2022. 8. 23. Stack 간단 정의, 시간복잡도 Stack 정의 스택은 대표적인 후입선출(LIFO) 방식의 자료 구조입니다. 가장 나중에 저장된 데이터가 가장 먼저 제거되는 구조입니다. 기본 함수로는 push, pop, empty, top, size이 있습니다 후입선출(LIFO) : Last In First Out 컨테이너 Stack는 컨테이너 어뎁터이다. 어뎁터 컨테이너는 다른 컨테이너 클래스들을 상속 받아서 다른 컨테이터 클래스의 객체에 특정한 인터페이스를 제공해주는 개념이다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 시간복잡도 1. 원소의 추가O(1) 2. 원소의 제거O(1) 3. 제일 상단의 원소 확인O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 c++/자료구조 간단 이론 2022. 8. 23. List 간단 정의 성질 및 종류 list : 노드형 시퀀스 컨테이너 연결 리스트의 성질 1. K번째 원소를 확인/변경하기 위해 O(k)가 필요함 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 리스트 배열 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가 / 제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간 (Overhead) - O(N) c++/자료구조 간단 이론 2022. 8. 23. queue간단 정의, 성질 queue정의 큐는 대표적인 선입선출(FIFO) 방식의 자료 구조입니다. 가장 처음에 저장된 데이터가 가장 먼저 제거되는 구조입니다. 기본 함수로는 push, pop, front, back, empty, size이 있습니다 선입 선출구조 FIFO(First In First Out) 컨테이너 queue는 컨테이너 어뎁터이다. 어뎁터 컨테이너는 다른 컨테이너 클래스들을 상속 받아서 다른 컨테이터 클래스의 객체에 특정한 인터페이스를 제공해주는 개념이다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 시간 복잡도 1. 원소의 추가 O(1) 2. 원소의 제거O(1) 3. 제일 앞/뒤의 원소 확인O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 c++/자료구조 간단 이론 2022. 8. 23. 이전 1 다음
