Knowledge23 [ Non Linear Data Structure ] 이진 탐색 트리 (Binary Search Tree) [ Non Linear Data Structure ] 이진 탐색 트리 (Binary Search Tree) 📚 Table of Contents 이진 탐색 트리 (Binary Search Tree) 개념 이진 탐색 트리란 아래의 규칙으로 구성된 이진 트리이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리를 유지 한다. 중복된 키를 허용하지 않는다. 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬된다. 유일한 키: 모든 노드는 중복되지 않는 키를 갖습니다. 왼쪽 서브 트리: 어떤 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 그 노드의 키보다 작습니다. 오른쪽 서브 트리: 어떤 노드의 오른쪽 서브 트리에 있는 모든.. 2024. 1. 21. [ Non Linear Data Structure ] 트리 구현 (Java) [ Non Linear Data Structure ] 트리 구현 (Java) 📚 Table of Contents 배열을 이용한 이진 트리 구성 class BinaryTree { // 문자 배열 char[] arr; // 생성자 BinaryTree(char[] data) { this.arr = data.clone(); } // 전위 순회 // 순서 : 현재 - 왼쪽 - 오른쪽 // A B D H I E J C F G public void preOrder(int idx) { // 현재 idx에 해당하는 data 출력 System.out.print(this.arr[idx] + " "); // 왼쪽, 오른쪽 자식 노드 int left = 2 * idx + 1; int right = 2 * idx + 2; // .. 2024. 1. 10. [ Non Linear Data Structure ] 트리 ( Tree ) [ Non Linear Data Structure ] 트리 ( Tree ) 📚 Table of Contents 트리란? ( Tree ) 트리( Tree )는 노드들이 가지처럼 연결된 비선형 자료구조이다. 트리는 노드와 링크로 구성된 자료구조이다. (그래프의 일종, Cycle 없음) 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 트리는 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 계층적 자료구조이기도 하다. 컴퓨터의 directroy구조가 트리 구조의 대표적인 예이다. 사용 사례 계층 적 데이터 저장 트리는 데이터를 계층 구조로 저장하는 데 사용됩니다. 예를 들어 파일 및 폴더는 계층적 트리 형태로 저장됩니다. 효율적인 검색 속도 효율적인 삽입, 삭제 및 검.. 2024. 1. 10. [ Non Linear Data Structure ] 힙 ( Heap ) [ Non Linear Data Structure ] 힙 ( Heap ) 📚 Table of Contents 힙 ( Heap ) 힙은 우선순위 큐 구현, 힙 정렬을 하기 위해 사용하는 자료구조이다. 힙은 이진 힙( Binary Heap )이라고 불리기도 한다. 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조 반 정렬 상태를 유지 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큼 / 작음 이진탐색트리(BST)와 달리 중복된 값이 허용된다. 완전 이진 트리 상태를 유지 항상 왼쪽부터 채워지는 트리( 왼쪽 자식이 없는데 오른쪽 자식 값이 있을 수 없다. ) 우선순위 큐 ( Priority Queue ) Queue : FIFO(First Out First In ) 형식의 자료구조 우선순위.. 2023. 12. 16. [ Linear Data Structure ] 해시 테이블 ( Hash Table ) [ Linear Data Structure ] 해시 테이블 ( Hash Table ) 📚 Table of Contents 해시 테이블 ( Hash Table ) 이란? 해시 테이블이란 해시함수를 사용하여 변환한 값을 index로 삼아 (key, value)로 저장하는 자료구조이다. 키를 통해 해당 데이터에 빠르게 접근할 수 있다. 해싱( Hashing ) 해싱이란 key를 특정 계산식인 해시함수( Hash Function )에 넣어 나온 결과를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해시 테이블 특징 key : 해시 테이블 접근을 위한 입력 값 hash function : 키를 해시 값으로 매핑하는 연산 hash value : 해시 테이블이 인덱스 hash table : key - val.. 2023. 12. 5. [ Linear Data Structure ] 데크 ( Deque ) [ Linear Data Structure ] 데크 ( Deque ) 📚 Table of Contents 데크 ( Deque ) 이란? 데크(Deque)는 Double-Ended Queue의 줄임말로, 양쪽 끝에서 데이터를 추가/반환/삭제할 수 있는 형태의 자료구조이다. 스택(Stack)과 큐(Queue)의 특징을 모두 갖고 있다. 배열(Array)로도 구현 가능하지만 이중 연결 리스트(Double Linked List)로 구현하는 것이 효율이 좋다. 데크 특징 자료의 추가, 삭제가 양쪽 끝에서 모두 가능 큐, 스택의 특징을 모두 갖는다. 큐 : 자료 삭제는 front / 추가는 rear 에서 만 가능 스택 : 자료 삭제 / 추가 모두 top 에서 만 가능 양쪽 2개의 포인트를 가진다. 이중 연결 리스트.. 2023. 12. 4. [ Linear Data Structure ] 큐 ( Queue ) [ Linear Data Structure ] 큐 ( Queue ) 📚 Table of Contents 큐 ( Queue ) 이란? 큐는 한쪽 끝에서 삽입되고, 다른 한쪽 끝에서 삭제되는 리스트 구조이다. 큐는 먼저 집어 넣은 데이터가 먼저 나오는 특징이 있다. ( 후입선출 ) 이러한 자료구조를 FIFO ( First In FIrts Out ) 라고 한다. 큐 특징 데이터의 입력, 출력이 정해진 위치에서만 가능하다. 자료 추가( 삽입, 입력 )는 끝( rear )에서 만 가능하다. 자료 반환( 삭제, 출력 )은 처음( front )에서 만 가능하다. 전후 / 선후 관계가 1 : 1 이다. 선형자료구조 이다. 입출력 순서 / 처리 방법에 따라 큐를 구분할 수 있다. 일반적인 큐 ( Genaral Queue.. 2023. 12. 3. [ Linear Data Structure ] 스택 ( Stack ) [ Linear Data Structure ] 스택 ( Stack ) 📚 Table of Contents 스택 ( Stack ) 이란? 일반적으로, 차곡차곡 쌓아둔 모양 / 형태의 자료구조를 의미한다. 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내는 특징이 있다. ( 후입선출 ) 이러한 자료구조를 LIFO( Last In FIrts Out ) 라고 한다. 스택 특징 후입선출 ( LIFO ) 구조 : 마지막에 들어온 데이터가 가장 먼저 나가는 구조 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같다. 리스트의 top에서 데이터가 들어오고 나간다. 데이터를 하나씩만 넣고 뺄 수 있다. 추가 ( push ) 삭제 ( pop ) 스택의 TOP, BOTTOM TOP, BOTTOM은 스택의 특정위.. 2023. 12. 2. [ Linear Data Structure ] 연결리스트 ( Linked List ) [ Linear Data Structure ] 연결리스트 ( Linked List ) 📚 Table of Contents 연결 리스트 ( Linked List ) 선형 리스트의 단점 ( 고정 크기의 순서 배열 )을 보완한 자료구조 이다. 동적으로 크기를 바꿀 수 있다. 삭제, 삽입 등에 데이터 이동이 필요 없다. 데이터 및 링크( 포인터 )에 의해 비 연속적( 비 순차적 )으로 연결된 선형 자료구조이다. 연결 리스트 특징 포인터로 연결되어 있다. 원소들이 메모리 내 어느 위치에도 가능하다. 동적으로 노드의 삽입과 삭제가 용이하다 항목의 삭제, 삽입 시에 데이터 이동이 필요 없다. 원 소 끝 포인터는 null을 가르킨다. 크기가 가변적이다. 메모리가 허용하는 만큼 커질 수 있다. 메모리 공간 사용이 효율적.. 2023. 12. 1. [ Linear Data Structure ] 배열 ( Array ) [ Linear Data Structure ] 배열 ( Array ) 📚 Table of Contents 배열 ( Array ) 배열 ( Array )는 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 방법이다. 예를 들어 배열이 int 타입인 경우 정수 요소만 저장할 수 있고 그 외 타른 타입의 요소는 저장할 수 없다. 배열을 구성하는 각각의 값을 요소 ( element )라고 하며, 배열의 위치를 가르키는 숫자는 인덱스 ( index )라고 한다. 배열 예시 // 배열 선언 // type[] name = new type[size] int[] arr = new int[5]; // 선언 + 초기화 int[] arr1 = {1, 2, 3, 4, 5}; //elements : 1, 2, 3 ,4.. 2023. 12. 1. 이전 1 2 3 다음
