개발자공부일기

레드-블랙 트리(Red-Black Tree)  레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다.1. 모든 노드는 빨간색 혹은 검은색이다.2. 루트 노드는 검은색이다.3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)4. 빨간색 노드의 자식은 검은색이다.   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)5. 모든 리프 노드에서 Black Depth는 같다.   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.삽입우리는 삽입 후 밸런싱을 하기 위해 회전을 도구로 사용했습니다. Red-Black 트리에서 우리는 밸런싱을 하기 위해 두..

B+ TreeB+ 트리는 B-트리 데이터 구조의 변형입니다. B+ 트리에서 데이터 포인터는 트리의 리프 노드에만 저장됩니다. B+ 트리 에서 리프 노드의 구조는 내부 노드의 구조와 다릅니다. 리프 노드에는 레코드(또는 이 레코드가 포함된 블록)에 대한 데이터 포인터와 함께 검색 필드의 모든 값에 대한 항목이 있습니다. B+ 트리의 리프 노드는 레코드에 대한 검색 필드에 대한 정렬된 액세스를 제공하기 위해 서로 연결됩니다. B+ 트리의 내부 노드는 검색을 안내하는 데 사용됩니다. 리프 노드의 일부 검색 필드 값은 B+ 트리의 내부 노드에서 반복됩니다.B+ 트리의 특징균형: B+ 트리는 자체 균형이 있습니다. 즉, 트리에 데이터가 추가되거나 제거되면 균형 잡힌 구조를 유지하기 위해 자동으로 조정됩니다. 이를..

https://javacpp.tistory.com/128 그래프(Graph)와 트리(Tree)그래프 와 트리는 컴퓨터 과학에서 객체 간의 관계를 나타내는 데 사용되는 두 가지 기본 데이터 구조입니다. 몇 가지 유사점을 공유하지만, 서로 다른 애플리케이션에 적합하게 만드는 뚜렷javacpp.tistory.com여기서 트리구조를 알아봤고 오늘은 이진트리다. 이진 트리 (binary tree) 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로(그래서 이름이 이진트리다), 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 트리와 이진 트리의 차이점이진 트리의 모든 노드는 차수가 2이하이다. 즉, 자식 노드의 개수가 2 이하이다. 반면 일반 트리는..

그래프 와 트리는 컴퓨터 과학에서 객체 간의 관계를 나타내는 데 사용되는 두 가지 기본 데이터 구조입니다. 몇 가지 유사점을 공유하지만, 서로 다른 애플리케이션에 적합하게 만드는 뚜렷한 차이점도 있습니다.그래프와 트리의 차이점Graph란 무엇인가요?그래프 데이터 구조는 노드 (정점이라고도 함)와 이를 연결하는 에지 의 모음입니다 . 노드는 사람, 장소 또는 사물과 같은 엔티티를 나타낼 수 있는 반면 에지는 이러한 엔티티 간의 관계를 나타냅니다.그래프는 소셜 네트워크 , 교통 네트워크 , 컴퓨터 네트워크 등 다양한 실제 시스템을 모델링하는 데 사용됩니다 . Tree란 무엇인가?트리 데이터 구조는 에지로 연결된 노드로 구성된 계층적 데이터 구조입니다. 각 노드는 여러 자식 노드를 가질 수 있지만 부모 노드는..

스택(Stack)스택은 LIFO(Last In First Out) 법칙을 분리하여 데이터 구조로 , 마지막으로 삽입된 요소가 가장 먼저 팝됩니다. 즉, 삽입 및 삭제 작업이 끝에서만 발생한다는 의미입니다.LIFO(후입선출)프링글스통을 상상하면 편하다. 우리가 통에 감자칩을 여러개 넣고 맨아래 감자칩을 빼려면 위에 감자칩부터 먼저 빼야할 것이다.스택 데이터 구조의 표현:스택은 LIFO(마지막에 들어간 요소가 먼저 나감) 원칙을 따르므로 마지막으로 푸시된 요소가 먼저 팝됩니다.스택의 종류:고정 크기 스택 : 이름에서 알 수 있듯이 고정 크기 스택은 고정된 크기를 가지며 동적으로 커지거나 줄어들 수 없습니다. 스택이 가득 차 있고 요소를 추가하려고 하면 오버플로 오류가 발생합니다. 스택이 비어 있고 요소를 제..

배열(Array)이란?배열은 연속된 메모리 위치에 요소를 저장하는 데 사용되는 데이터 구조입니다. 이는 각 요소가 서로 인접한 메모리 위치에 저장된다는 것을 의미합니다. 또한 배열의 크기는 변경할 수 없으며 미리 선언됩니다.이것은 각 상자가 인접한 메모리 위치에 해당하는 크기 6 의 배열의 예입니다 . 보시다시피, 배열은 처음에 크기 6 으로 선언되었지만 인덱스 0-4 만 사용됩니다. 그러나 인덱스 5 가 비어 있고 값이 없지만 메모리 공간을 차지하고 있습니다.접근요소에 접근할 때 배열은 매우 효율적이며 상수 시간 O(1)이 걸립니다 .이는 각 메모리 위치의 순차적 특성 때문입니다. 예를 들어 인덱스 4에서 요소를 검색하고 싶다고 가정해 보겠습니다. 그런 다음 배열의 기본 주소(첫 번째 요소의 메모리 주..