mei 기술 블로그

1. 균형 이진 트리모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리2. 이진 탐색 트리의 편향 발생Case 1) 이진 탐색 트리에 삽입되는 순서: 20 -> 10 -> 30 -> 5Case 2) 이진 탐색 트리에 삽입되는 순서: 5 -> 10 -> 20 -> 303. 균형 이진 탐색 트리 (Balanced Binary Search Tree)노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리AVL 트리, Red-Black 트리4. AVL 트리노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리각 노드의 BF를 [-1, 0, 1]만 가지게 하여 균형을 유지BF (Balanced Factor)왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이5. AVL 트리 - 리밸런싱 (LL..

1. 이진 탐색 트리 (Binary Search Tree)아래의 규칙으로 구성된 이진 트리왼쪽 자식 노드의 키는 부모 노드의 키보다 작음오른쪽 자식 노드의 키는 부모 노드의 키보다 큼각각의 서브 트리도 이진 탐색 트리를 유지중복된 키를 허용하지 않음2. 이진 탐색 트리 특징이진 탐색 트리 규칙에 의해 데이터 정렬이진 트리에 비해 탐색 빠름 (균형 유지 필요)균형 상태 : O(logN)불균형 상태 : O(N)3. 이진 탐색 트리 - 탐색찾고자 하는 데이터를 루트 노드부터 비교 시작대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동찾는 데이터가 없으면 null 반환어떤 데이터를 찾더라도 최대 트리 높이만큼의 탐색이 이루어짐4. 이진 탐색 트리 - 삽입Root부터 비교 시작 (중복 키 발견..

1. 트리 (Tree)노드와 링크로 구성된 비선형 자료구조 (그래프의 일종, Cycle 없음)계층적 구조를 나타낼 때 사용폴더 구조 (디렉토리, 서브 디렉토리)조직도, 가계도, ...2. 트리의 구조노드 (Node) : 트리 구조의 자료 값을 담고 있는 단위엣지 (Edge) : 노드 간의 연결선 (= link, branch)루트 노드 (Root) : 부모가 없는 노드, 가장 위의 노드잎새 노드 (Leaf) : 자식이 없는 노드 (= 단말)내부 노드 (Internal) : 잎새 노드를 제외한 모든 노드부모 (Parent) : 연결된 두 노드 중 상위의 노드자식 (Child) : 연결된 두 노드 중 하위의 노드형제 (Sibling) : 같은 부모를 가지는 노드깊이 (Depth) : 루트에서 어떤 노드까지의 ..

1. 공통점둘 다 Map 인터페이스를 구현한 것Key-Value 쌍으로 데이터 처리2. 차이점Key에 Null 사용 여부Hashtable: 불가능HashMap: 가능Thread-safeHashtable: O (멀티 스레드 환경에서 우수)HashMap: X (싱글 스레드 환경에서 우수)synchronizedMap, ConcurrentHashMap을 사용하면 HashMap도 Thread-safe하게 사용 가능3. 코드// HashtableHashtable ht = new Hashtable();ht.put(0, 10);System.out.println(ht.get(0)); // 10// HashMapHashMap hm = new HashMap();hm.put(0, 10);System.out.println(hm..

1. 해시 테이블키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조키를 통해 해당 데이터에 빠르게 접근 가능해싱키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정2. 해시 테이블 구조키해시 테이블 접근을 위한 입력 값해시 함수키를 해시 값으로 매핑하는 연산해시 값해시 테이블의 인덱스해시 테이블키-값을 연관시켜 저장하는 데이터 구조3. 해시 충돌해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음4. 해시 충돌 해결 방법개방 주소법 (Open Address)충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장hash와 value가 1:1 관계..

1. 데크 (Deque)양쪽에서 삽입과 삭제가 모두 가능한 자료구조Deque, Doubly-ended QueueStack과 Queue를 합친 형태2. 데크 기본 구조데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조일부 기능을 제한하여 용도에 맞게 변형 가능add/remove vs offer/polladd와 remove는 데이터가 없으면 예외를 발생시킴offer과 poll은 데이터가 없으면 null이나 false를 반환하여 리턴 값을 받을 수 있음3. 입력 제한 데크 (Scroll)한 쪽의 입력을 제한한 데크4. 출력 제한 데크 (Shelf)한 쪽의 출력을 제한한 데크5. 코드Deque deque = new ArrayDeque();// Front 부분 입력deque.addFirst(1);deque.ad..

1. 큐 (Queue)선입선출 (First In First Out; FIFO) 자료구조먼저 들어온 데이터가 먼저 나가는 구조입력 순서대로 데이터 처리가 필요할 때 사용프린터 출력 대기열, BFS (Breath-First Search) 등2. 큐 기본 구조선입선출 구조를 따름기본적으로 데이터 추가/꺼내기/큐 공간 확인 동작으로 이루어짐3. 큐 기본 연산데이터 추가 (Enqueue)큐에 데이터 추가데이터 꺼내기 (Dequeue)큐에서 데이터 꺼내기4. 코드// Queue는 인터페이스라서 바로 객체 생성 불가능Queue queue = new LinkedList();queue.add(1);queue.add(2);queue.add(3);queue.add(4);queue.add(5);System.out.printl..

1. 스택 (Stack)후입선출 (Last In Fitst Out; LIFO) 자료구조마지막에 들어온 데이터가 먼저 나가는 구조데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용ex) 함수 콜 스택, 수식 계산, 인터럽트 처리 등2. 스택 기본 구조후입 선출 구조기본적으로 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어짐3. 스택 기본 연산데이터 추가 (Push)스택의 가장 마지막 위치에 데이터 추가데이터 꺼내기 (Pop)스택의 가장 마지막 위치에서 데이터 꺼냄4. 코드Stack stack = new Stack();stack.push(1); // [1]stack.push(2); // [1, 2]stack.push(3); // [1, 2, 3]stack.push(4); // [1, 2, 3, 4..

1. 코드class CircularLinkedList { NodeBi head; NodeBi tail; CircularLinkedList(NodeBi node) { this.head = node; this.tail = node; node.next = this.head; node.prev = this.head; } public boolean isEmpty() { if(this.head == null) { return true; } return false; } // 데이터 추가 // before_data가 null인 경우, 가장 끝에 추가 ..

1. 코드Class NodeBi { int data; NodeBi next; NodeBi prev; NodeBi(int data, NodeBi next, NodeBi prev) { this.data = data; this.next = next; this.prev = prev; }}class DoublyLinkedList extends LinkedList { NodeBi head; NodeBi tail; DoublyLinkedList(NodeBi node) { this.head = node; this.tail = node; } // 연결 리스트가 비어있는지 확인 p..