Coding Diary

1. 개념 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조. 각 노드는 문자 혹은 문자열의 한 글자를 나타낸다. 또한, 각 노드는 자식을 가지고 있을 수 있는데, 이는 각 노드의 다음 문자를 나타낸다. 2. 특징 루트 노드는 항상 공백이다. N진 트리의 형식을 가진다. 문자 종류에 따라 N이 결정된다. 알파벳은 26개의 문자로 이루어져 있기 때문에 26진 트리 형태를 갖게 된다. 즉 부모 노드가 자식을 최대 26개까지 가질 수 있다는 것이다. 각 문자의 접두사를 공유하기 때문에 검색이 빠르다. 트리 형태로 문자를 저장하기 때문에 삽입과 삭제 연산이 빠르다. 조건을 만족한다면 상수시간 안에도 가능하다. 3. 구현 // 트라이에서 사용하는 노드 정의 class tNode{ tNode[] ..

1. 개념 노드와 에지로 연결된 그래프의 특수한 형태. 2. 특징 순환 구조를 가지고 있지 않다. 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리도 트리의 모든 특징을 따른다. 3. 트리의 구성 요소 1) 루트 노드 2) 부모 노드 3) 자식 노드 4) 에지 5) 리프 노드 6) 서브 트리 4. 구현 1) 그래프 이용 그래프 구현을 이용해서 구현하면 된다. 인접 리스트 사용. 동적으로 크기 조정이 가능하다. 연결리스트로 구현되기 때문에 노드의 삽입과 삭제가 쉽다. 특정 위치의 노드에 접근하기 위해서 연결리스트를 순회해야 해서 접근 시간이 오래 걸린다. 다음 노드를 가리키는 정보를 저장해야 해서 메모리 사용량이 증가할 수 있다. adjList = ..