이진 탐색 트리(Binary Search Tree)란? 각 노드에 중복되지 않는 키(Key)가 있다. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠릅니다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 가집니다. 이진 탐색 트리의 탐색 과정을 한번 보시죠! 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료합니다. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 ..

Binary Tree 란? 모든 노드가 정확하게 두개의 서브트리를 가지고 있습니다. 서브트리는 공백이 될 수 있습니다. 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽 서브트리와 오른쪽 서브트리로 구성 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖습니다. 위의 그림을 보겠습니다! 두개의 서브 트리가 모두 공백인 리프 노드 - D, H, F, I 공백이 아닌 서브 트리를 하나씩 가지고있는 노드 - E, G 노드 E는 공백 왼쪽 서브트리와 오른쪽 서브트리 H를 가지고 있으며 노드 G는 왼쪽 서브트리I와 오른쪽 공백 서브트리를 ..

트리란? - 노드들을 간선으로 연결한 계층형 자료구조 - 제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결 - 하나의 노드는 그자체로 트리이며 루트가 됩니다. - ㅌ스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조입니다. - 루트 노드는 0개 이상의 자식 노드를 갖습니다. - 자식 노드 또한 0개 이상의 자식 노드를 갖습니다. 1. 트리에는 사이클(cycle)이 존재할 수 없습니다. 트리는 사이클이 없는 하나의 연결 그래프구조라고 할 수 있습니다. 2. 트리의 노드는 self-loop가 존재 해서는 안됩니다. 트리와 관련된 용어 노드 node: 트리는 노드들의 집합으로 트리를 구성하는 것으로 보통 값과 부모 자식의 정보를 가지고 있다. 엣지/간선 edge: 엣지는 노드들을 연결하는..

스택(Stack)이란? 최근에 삽입된 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료구조(Structure) 스택이란 단어의 사전적 용어는 '차곡 차곡 쌓여진 더미'를 의미합니다. 메모리에서의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값등의 임시데이터를 저장합니다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 합니다. Stack 실생활 예시를 들자면 과자 프링글스 다들 아시죠? 제일 나중에 넣은 칩 조각을 가장 먼저 먹게되는 것과 같은 이치라고 생각하시면 됩니다! 위의 그림을 보시면 스택은 top으로 정한 곳을 통해서만 접근할 수 있습니다. top은 가장 최근에 들어온 자료를 가리키고 있으며 만약..

배열이란? 배열은 연관된 데이터를 모아서 관리하기 위해서 사용되는 데이터 타입입니다. 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리할 수 있습니다. 위의 예시를 보면 크기가 4인 과일에 대한 배열이 있습니다. 사과, 바나나, 포도, 수박은 배열에 저장된 값이고(Value) 그리고 밑에 있는 숫자들은 Value를 식별하는 Index입니다. 배열의 값을 찾기 위해 Index를 사용합니다! 그렇기 때문에 찾고자 하는 element의 인덱스 값을 알고 있다면 Big-O(1)에 해당 element로 접근할 수 있습니다. 즉 random access가 가능하다는 장점이 있습니다. random access란? - 인덱스 번호를 이용해서 빠르게 접근하는 것 임..