탐색이란? 탐색(search)은 컴퓨터 응용 중 가장 중요한 것들 중 하나이다. 컴퓨터에는 데이터들이 저장되어 있고 이 데이터들 중에서 필요한 데이터를 찾아내는 작업은 빈번한 작업이다. 컴퓨터에 저장되는 데이터의 양이 급속도로 증가하고 있어 효율적이고 바른 탐색을 하는 것은 매우 중요하다. 자료구조의 관점에서 보면 탐색은 자료구조의 중요한 응용 분야 중 하나이다. 후에 다양한 탐색 방법을 알아볼 것이지만, 지금은 탐색을 위해 특화된 이진 트리인 이진 탐색 트리를 알아보자. 탐색 관련 용어 이진 탐색 트리를 알아보기 전에 탐색 관련 용어들을 먼저 알아보자. 컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다. 레코드는 하나 이상의 필드(field)로 구성된다..

스레드 이진 트리 앞서 알아본 순회 방법은 재귀 함수를 사용(전위/중위/후위 순회)하거나 별도의 자료구조 큐를 사용(레벨 순회)했다. 이런 방법말고는 순회하는 방법이 없을까? 이제 알아 볼 스레드 이진 트리(threaded binary tree)가 그렇다. 이진 트리에는 수많은 NULL링크가 존재한다. 노드의 개수가 n개인 이진 트리는 각 노드마다 2개의 링크 필드가 존재한다. 그래서 총 링크 필드의 개수는 2n개이고, 이 중 n-1개의 링크 필드만이 부모 노드와 연결되어 있다. 그러면 남은 n+1개의 링크 필드는 NULL을 가리키게 되는 것이다. 스레드 이진 트리는 NULL 링크 필드를 이용해서 재귀 호출이나 큐 없이 순회할 수 있다. 중위 순회를 위한 스레드 이진 트리를 알아 보자. 트리의 노드들을 ..

이진 트리의 연산 앞서 구현했던 이진 트리 코드에서 연산 부분을 완성시켜보자. https://seongmoahn.tistory.com/96 6-5. [C++] 이진 트리의 순회(전위/중위/후위/레벨 순회) 이진 트리의 순회 앞서 구현했던 이진 트리 코드에서 순회 부분을 완성시켜보자. https://seongmoahn.tistory.com/95 6-4. [C++] 연결 리스트로 구현한 이진 트리 앞서 다뤘던 이진 트리의 ADT를 이용해 정수(i seongmoahn.tistory.com 이진 트리에는 순회 이외에도 여러 가지 연산들이 있다. (노드 개수 구하기, 단말 노드 개수 구하기, 높이 구하기 등) 이진 트리의 노드 개수 구하기 트리의 전체 노드 개수를 구하기 위해서는 트리의 모든 노드들을 순회해야 한..

이진 트리의 순회 앞서 구현했던 이진 트리 코드에서 순회 부분을 완성시켜보자. https://seongmoahn.tistory.com/95 6-4. [C++] 연결 리스트로 구현한 이진 트리 앞서 다뤘던 이진 트리의 ADT를 이용해 정수(int)를 저장하는 이진 트리의 UML 다이어그램을 구성해보자. 이진 트리의 노드를 구현한 BinaryNode 클래스를 만들고 이진 트리를 구현한 BinaryTree 클래스 seongmoahn.tistory.com 트리를 순회(traversal)한다는 것은 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다. 트리를 사용하는 목적은 노드에 자료를 저장하고 필요에 따라 이 자료를 처리하기 위함이다. 그래서 트리에 포..

앞서 다뤘던 이진 트리의 ADT를 이용해 정수(int)를 저장하는 이진 트리의 UML 다이어그램을 구성해보자. 이진 트리의 노드를 구현한 BinaryNode 클래스를 만들고, 이진 트리를 구현한 BinaryTree 클래스에서는 노드 클래스를 사용할 것이다. BinaryNode 클래스를 먼저 구현해보자. // BinaryNode.h #include class BinaryNode { protected: int data; BinaryNode *left; BinaryNode *right; public: BinaryNode(int data = 0, BinaryNode *left = NULL, BinaryNode *right = NULL) : data(data), left(left), right(right) {} ..

이진 트리를 구현하는 방법은 크게 두 가지가 있다. 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이다. 배열을 이용해 이진 트리를 구현하는 방법 이진 트리의 높이가 h이면 먼저 2h-1개의 공간을 배열로 할당한다. 이진 트리의 '위에서 아래로', '왼쪽에서 오른쪽으로'의 순서대로 번호를 할당한다. 이 번호가 배열의 인덱스로 사용된다. 노드간의 부모/자식 관계를 쉽게 파악하기 위해 노드의 번호는 1부터 사용한다. 노드의 번호를 1부터 사용하면 다음과 같은 장점이 있다. 노드 i 의 부모 노드 인덱스 : i / 2 노드 i 의 왼쪽 자식 노드 인덱스 : 2 * i 노드 i 의 오른쪽 자식 노드 인덱스 : 2 * i + 1 임의의 노드 인덱스 값만 알고 있다면 그 노드의 부모/자식 노드를 쉽게 알 수가 ..

이진 트리란? 이진 트리(binary tree)는 모든 노드가 2개 이하의 서브트리를 갖는 트리이다. 이진 트리의 모든 노드는 0~2개의 서브트리를 갖기 때문에 모든 노드의 차수는 0~2가 된다. 이진 트리에서는 서브트리 간의 순서를 구분한다. (왼쪽 서브트리, 오른쪽 서브트리) 이것을 이용해 이진 트리를 재귀적으로 정의할 수 있다. 이진 트리(binary tree) (1) 공집합이거나 (2) 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의된다. (2)-1 이진 트리의 서브트리들은 모두 이진트리여야 한다. 이진 트리의 재귀적인 정의는 이진트리의 알고리즘을 작성할 때 매우 중요하게 사용된다. 이진 트리의 성질 n개의 노드를 갖는 이진 트리는 n-1개의 간선을 갖는다. 높이가 h..

트리란? 앞서 다뤘던 자료구조들이 자료들을 일렬로 나열하는 선형 자료구조(linear data structure)인 것과 달리, 트리는 계층적인 구조(hierarchical structure)의 자료구조이다. 트리의 구조를 쉽게 이해할 수 있는 것이 회사의 조직 체계이다. 트리를 계층적 구조라고 부르는 이유는 구조의 이미지가 나무를 거꾸로 뒤집어 놓은 듯한 모양을 하기 때문이다. 인공지능 문제에서도 트리가 사용된다. 대표적인 것이 결정 트리(decision tree)이다. 알파고 같이 복잡한 인공지능 프로그램의 결정 트리는 아래처럼 매우 복잡한 형태를 띄기도 한다. 트리의 용어 트리에서 데이터를 저장하는 각각의 원을 노드(node)라고 한다. 트리는 한 개 이상의 노드로 이뤄진 유한 집합이다. 노드들 중..