트리 데이터 구조

트리

트리 데이터구조는 데이터를 계층으로 정렬한다.

루트 노드는 식물의 뿌리에 해당한다. 트리의 나머지 요소들은 루트노드를 기준으로 구성된다. 루트 노드에서 멀어지는 방향으로 또 다른 노드가 연결되면 해당 노드를 하위 노드 또는 자식 노드라고 한다.

루트 노드를 향한 방향으로 또다른 방향으로 노드가 연결되면 해당 노드를 상위 노드 또는 부모 노드라고 한다. 부모 노드는 여러개의 자식 노드를 갖는다. 자식 노드를 갖지 않는 노드는 말단 노드 또는 리프 노드라고 하는데 이는 식물의 나뭇잎에 해당한다.

에지는 트리에서 노드를 연결하는 선이다. 노드 하나와 그 자식 노드들로 구성된 트리를 하위 트리 또는 자식 트리라고 한다.

트리를 탐색하는 과정을 순회라고 한다.

이진 트리

가장 많이 사용되는 데이터구조. 각 부모 노드가 항상 2개의 자식노드와 연결되어 있다. 가장 일반적인 이진 트리 유형은 이진 탐색 트리로, 이진 탐색 트리는 노드의 키를 기준으로 정렬한 상태이다.

이진 탐색 트리에서 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다. 가장 작은 키를 갖는 노드는 최상위 노드에서 가장 왼쪽에 있는 서브트리에 있고, 가장 큰 키를 갖는 노드는 최상위 노드에서 가장 오른쪽에 있는 서브트리에 있다.

AVL 트리

어떠한 이유로든 불균형 이진 트리가 있을 수 있으며 이는 일반적으로 많은 노드가 단 하나의 자식 노드를 갖는 구조다.

이를 해결하려면 트리의 균형을 조정하는 과정을 거쳐야 하는데, 트리의 역할은 유지하되 가능한 최소 높이로 만드는 것이다.

서브트리 2개 사이에서 높이 차이를 감지하면 트리회전이라는 균형 조정 과정을 수행하는데, 노드 하나는 위로 올라가고 다른 노드 하나는 아래로 이동한다. 이런 트리를 AVL(Adelson-Velsky and Landis) 이진 트리라고 한다.
트리가 균형을 조정하는 과정에서 중요한 것은 그 과정에 걸리는 시간이다. AVL트리의 시간 복잡도는 O(log n)이다.

RB트리

RB 이진 탐색 트리는 자채적으로 균형을 조정하는데, 균형을 조정하는 과정에서 트리 회전수가 적어 AVL 트리보다 효율적이다. RB트리의 시간 복잡도는 O(log n)이다.

RB 트리는 노드마다 빨강 또는 검정으로 해석되는 비트를 포함하는 특징이 있다. 일반적으로 루트노드는 검정이고, 빨강 노드는 검정 노드를 자식으로 갖는다.

B트리

데이터베이스 시스템을 설계할 때 사용하는 데이터 구조로 자체적인 균형 조정 기능을 갖춘 트리 유형이다. 이진 트리와 달리 B트리에는 자식 노드 3개 이상을 갖는 부모 노드가 있다.

많은 파일 시스템에서 데이터 계층 구조로 B트리를 이용한다. 파일 시스템에는 폴더가 있고, 노드의 키-값 구조를 통해 폴더 각각의 이름을 파일 시스템의 객체와 연결 할 수 있다.
또 폴더 각각에는 여러 파일을 갖는 다른 폴더가 존재 할 수 있다.

힙

이진 트리 데이터 구조의 한 종류이며, 값이 최대 혹은 최소인 노드에 빠르게 접근하는 경우에 유용하다.

힙의 구조를 설계하는 방법에는 두가지가 있는데 첫번째는 루트 노드가 힙에서 가장 큰 값이고 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성된 최대 힙이다.

두번째는 루트 노드가 힙에서 가장 작은 값이고 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성된 최소 힙이다.

해시 데이터 구조

해시와 해시 함수

해시는 어떤 길이의 임의의 데이터를 고정 길이의 데이로 매핑하는 것. 해시 함수는 이 해시를 실행하여 하나의 값을 다른 값으로 변환한다.
해시 함수는 일반 함수와는 다르게 서로 다른 입력 2개가 같은 해시값을 생성할 가능성도 있다. 이를 해시 충돌이라 한다.

해시 테이블

해싱할 때 사용하며, 해시 함수는 해시 테이블 데이터 구조에서 중요한 부분이다. 해시 테이블은 키-값으로 구성된 검색 시스템으로 해시 테이블에는 모든키에 해당하는 값이 있다.
각 키는 값 하나와 연결되어 있으므로 키를 알면 연결된 값을 즉시 찾을 수 있다. 따라서 해시 테이블에서 요소를 검색할 때 시간복잡도는 O(1)이다.

보통 문자열안 카룰 햐사 함수에 입력하면 저장을 위한 데이터 구조의 인덱스에 매핑된 해시값이 생성된다. 이 방식은 효율적이지만 해시값과 배열 크기 때문에 해시 충돌이 발생 할 수 있다.
이런 해시 충돌의 발생을 막기 위해 체이닝이라는 방식으로 해시 테이블을 구현한다.

체이닝은 요소를 단순 배열이 아니라 연결 리스트에 저장하는 방식이다. 테이블의 각 인덱스에 할당된 것은 값이 아니라 키와 값을 가진 연결 리스트이다.
해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환하면 해시값과 해당 요소들을 함께 연결하여 해시 테이블의 같은 인덱스에 저장한다.
단, 체이닝을 사용하면 연결 리스트가 길어졌을 때 해시 테이블 검색의 시간 복잡도가 증가할 가능성이 있다.

컴퓨터 보안 기초

해싱은 컴퓨터 보안 영역에서 주로 사용된다. 컴퓨터 보안의 암호 시스템은 평문 입력을 암호문 출력으로 변환하는 알고리즘이다. 대칭 키 방식은 암호화 및 복호화에 같은 키를 사용하기 때문에 제3자가 키를 가로채면 암호화된 데이터를 복호화 할 수 있다.
이 결함을 해결하기 위해 암호화와 복호화에 사용하는 키를 따로 두는 공개 키 암호 시스템이 개발되었다.

암호화와 해싱의 차이는, 암호화는 키가 있는 사람이 정보를 해독해 사용하는 양방향 과정이지만 해싱은 데이터를 변환한 후에 원래 데이터가 필요없는 단방향 과정이다.

컴퓨터 보안에서 해시의 역할

가장 먼저 눈에 띄는 해시의 역할은 디지털 서명이다. 디지털 서명 방식은 일반적으로 RSA(Rivest-Shamir-Adleman)와 DSA(Digital Sigunature Algorithm)를 사용하고, 둘 모두 해시 방식의 함수를 이용한다.

이외에도 난수생성, 메시지 인증 코드, 암호 관련 응용프로그램 등에 사용된다.

해시와 순환 중복 검사

순환 중복 검사(CRC - Cyclic Redundancy Check)는 디지털 데이터의 오류를 감지하는 방식으로 해시 함수의 원리를 이용하여 데이터의 유효성을 검증한다.

보통 해시 함수를 통해 고정된 비트수의 체크섬을 찾아 발신할 데이터에 첨부하는 방식으로 동작하는데, 수신 데이터의 CRC와 발신 데이터의 CRC와 일치하지 않는다면 데이터가 손상되었을 가능성이 크다.
이 때, 해당 데이터를 무시하거나 데이터를 재전송 하도록 응용프로그램을 설계할 수 있다.

해시의 다른 용도

검색 엔진, 컴파일러, 데이터베이스 등은 많은 양의 복잡한 검색 연산을 수행해야 한다. 검색 연산에는 많은 시간이 필요하고 소요시간이 성능에 큰 영향을 주기 때문에 일반 적인 데이터 구조로는 검색 연산을 보조 할 수 없다.

복잡한 검색 연산을 수행하는 응용 프로그램에는 해시의 시간복잡도 O(1)을 적용하기 좋은 조건이다.

그래프

차원, 점, 선

차원, 점, 선은 컴퓨터 과학의 그래프를 이해햐는데 필수적인 게념이다. 수학에서 말하는 차원은 주로 한 방향으로의 거리를 뜻한다. 이 거리는 길이나 너비 또는 높이일 수 있다.
가장 일반적인 것은 2차원과 3차원이다. 2차원 형상에는 길이와 너비의 차원이 있고, 3차원 형상에는 길이, 너비, 높이의 세 가지 차원이 있다.

점은 차원이 없고 위치만 갖는다. 점은 시작위치이고 선은 한 방향으로 이동한 점이라고 할 수 있다. 2개의 선이 만나면 정점(vertex)이 생긴다.

이 같은 기본적인 기하학 지식은 그래프를 이해하는 기반이 된다.

그래프

그래프는 노드 사이의 연결을 보여준다. 컴퓨터 과학과 수학의 관계를 확인 할 수 있는 중간 영역 개념이기도 하기에 수학에서 파생된 그래프 이론은 컴퓨터 과학의 많은 응용 분야에 적용되고 있다.

그래프 VS 트리

그래프는 루트 노드가 없는 트리처럼 보이며, 부모 노드 또는 자식 노드로 식별할 수 있는 노드를 찾을 수 없다. 또한 각 자식 노드가 여러개의 부모 노드를 갖는 혼잡한 트리처럼 보이기도 한다.

매우 구조화된 트리와 달리 그래프는 현실 세계에 존재하는 연결 관계를 더 잘 표현한다. 또 일부 프로그래머는 트리를 일종의 최소화된 그래프로 여기기도 한다. 왜냐하면 그래프에서 동작하는 알고리즘이 트리에서 동작하고 트리는 기본적으로 순환 상호작용이 없는 그래프와 같기 때문이다.

무향 그래프와 유향 그래프

그래프의 노드를 보통 객체 또는 정점이라 하고, 정점들을 연결하는 선을 에지(edge)라고 한다. 에지로 연결된 정점들은 서로 인접한 상태이다. 에지는 노드 하나에서 다른 노드로 방향성을 가질 수 있는데 이러한 에지를 가진 그래프를 유향 그래프라고 한다.

반대로 방향성이 없는 에지를 가진 그래프를 무향그래프하고 한다. 방향성을 가진 에지가 없으므로 노드 양쪽으로 에지를 타고 이동할 수 있다.

그래프의 정점에서 다른 정점으로 이동하려면 에지를 타고 이동해야 하는데 이를 경로(path)라고 한다. 그리고 에지가 정점 하나에서 시작해 다시 해당 정점으로 이어지는 형태를 루프라고 한다.

어떤 그래프가 더 큰 그래프의 일부라면 해당 그래프를 하위 그래프 또는 서브 그래프라고 한다. 그래프는 객체(노드)사이의 관계를 볼 수 있다는 점에서 편리하다. 이러한 그래프의 속성은 다양한 경우에 유용하고, 많은 탐색 기반 알고리즘이 그래프에 의존한다.

가중치 그래프

에지가 가중치를 갖는 그래프를 가중치 그래프라고 하고, 가중치 그래프에도 무향과 유향이 있다. 여러 알고리즘이 가중치 그래프에 의존한다.

그래프 데이터베이스

그래프와 그래프 이론이 적용된 예 가운데 하나는 그래프 데이터베이스 설계와 메커니즘이다. 데이터를 저장할 경우 파일 시스템이나 데이터베이스 관리 시스템을 사용할 수 있는데, 파일시스템의 단점을 해결하기 위해 관계형 데이터베이스 관리 시스템(RDBMS)이 등장했다.

RDBMS에는 데이터베이스의 테이블 속성과 저장되는 데이터를 설명하는 스키마가 있고, 스키마를 잘 활용하면 데이터베이스 설계 명세, 관리 조건, 보안 등을 수립하는데 유용하다.

또 키 시스템을 통해 조건을 만족하는 데이터를 찾거나 정렬할 때 기준을 정할 수 있다. 데이터를 식별하는 속성이 담겨 널 값이면 안되는 기본키와, 다른 테이블과의 관계를 참조하는 속성 정보를 담은 외래키의 개념은 중요하다.

RDBMS는 데이터베이스가 확장될 때 문제가 발생한다. 연결된 테이블 사이의 일부 연산은 컴퓨터의 많은 자원을 필요로 하는데, 그래프 구조로 설계된 데이터베이스는 RDBMS가 지닌 많은 문제를 개선한다.

RDBMS의 데이터 검색은 테이블 사이의 조인이 너무 많으면 테이블을 거쳐 데이터에 접근하는 과정이 반복되므로 검색 속도에 영향이 발생한다. 그러나 그래프 데이터베이스는 테이블이 아닌 데이터 중심으로 직접 연결하는 구성이므로 데이터베이스의 검색속도가 상대적으로 빠르다.