Dev/Data Structure5 [자료구조] Tree에 대하여(2) - 이진 검색 트리와 AVL 트리 1. BST (Binary Search Tree) : 이진 검색 트리 Binary Tree에서는 검색 연산의 worst case가 O(n)의 복잡도를 가졌다. 하나의 노드를 찾는 데에는 모든 노드를 탐색했어야 하기 때문이다. BST(Binary Search Tree)에서는 제약을 둔다. 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값, 오른쪽에는 큰 값. 위 제약을 통하여 검색 연산에 대한 시간 복잡도를 O(log n)으로 줄일 수 있다. 더보기 사실 위 제약만으로는 검색 연산에서의 worst case가 O(n)으로 동일하다. (skew tree의 경우) 이는 BST를 밸런싱 작업을 통해 해결할 수 있으며 잠시 후 배우게 될 것이다. 1-1. 특징 1. 노드의 왼쪽 서브 트리는 노드의 키 값보다 작은 키.. 2021. 5. 31. [Kotlin/자료구조] Tree에 대하여(1) 1. 들어가기 전에 : 선형 구조 vs 비선형 구조 이전 포스팅에서 설명한 LinkedList(연결 리스트), Queue(큐), Stack(스택)은 선형(Linear) 자료구조라고 한다. 선형 자료구조는 데이터가 연속적으로, 순차적으로 나열된 형태를 뜻한다. 배열과 리스트가 대표적이다. 하나의 선에 데이터의 앞(front). 뒤(rear)가 존재한다고 생각하면 쉽다. 선형 구조 외에 분류로 비선형(NonLinear) 자료구조가 있다. 비선형 자료구조는 데이터의 관계들이 계층적으로 연관된, 또는 1:n / n:m 관계를 갖는 자료구조이다. 트리와 그래프가 대표적이다. 하나의 데이터 뒤에 여러개의 데이터가 존재한다고 생각하면 쉽다. 그래프에 대해서는 다음 포스팅에서 다루도록 하겠다. 사실 트리도 그래프의 한.. 2021. 5. 9. [Kotlin/자료구조] Stack과 Queue에 대하여 Stack(스택)과 Queue(큐)는 선형 자료구조 중 하나이다. 이에 대해서 알아보고 Kotlin에서는 어떻게 사용하는지 알아보는 포스트이다. 1. Definition Stack(스택)의 정의 Stack은 삽입과 삭제가 한쪽 끝에서 이루어지는, 순서가 매겨진 리스트이다. LIFO(Last In First Out, 후입 선출) 혹은 FILO(First In Last Out, 선입 후출)의 형태이다. 위 그림과 같이 데이터를 삽입할 때 마다 바닥에 순서대로 쌓이며 꺼낼 때에는 가장 나중에 들어온 데이터가 꺼내진다. Stack에서의 삽입과 삭제의 행위를 각각 push(삽입)와 pop(삭제)이라고 부른다. Java의 단일 클래스로 Stack 클래스(extends Vector)가 존재하며 Kotlin에서 사용할.. 2021. 4. 25. [Kotlin/자료구조] Linked List에 대하여(2) - Singly Linked List 삭제와 Doubly Linked List 노드 삭제 (in Singly Linked List) Singly Linked List내에 있는 노드를 삭제하는 방법은 삽입하는 것과 마찬가지로 3가지 방식으로 가능하다. 1️⃣ Head (첫 노드) 삭제하기 - Head를 두 번째 항목으로 Pointer나 Reference를 옮긴다. - 기존 노드 Component를 모두 null로 변경한다. 더보기 C에서는 OS 메모리에 직접 접근하기 때문에 삭제할 노드를 메모리에서 삭제(free) 해줘야하지만, 코틀린(자바)은 JVM에서 알아서 처리해준다.(Java GC) 하지만 기존 노드를 그대로 유지시킨다면 GC가 콜렉팅하지 않을 수 있기에 기존 항목을 null로 변경해서 GC를 도와주자. C에서는 임시 노드를 생성하여 기존 노드를 기억하고 있다가 Pointer.. 2021. 4. 17. 이전 1 2 다음
