목록트리 (3)
판봉 개발 일기
인덱스의 개념 인덱스는 데이터 레코드를 빠르게 접근하기위해 구성하는 것입니다. 데이터가 저장된 물리적 구조와 관계가 있습니다. 레코드가 저장된 물리적 구조에 접근하는 방법을 제공합니다. 인덱스를 통해 파일의 레코드에 대한 액세스를 빠르게 할 수 있습니다. 레코드의 삽입과 삭제가 수시로 일어나면 인덱스의 개수를 줄이는게 좋습니다. m-원 검색 트리(m-way Search Tree) 한 노드가 최대 m-1개의 키와 m개의 Subtree를 갖도록 구성됨 키 값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 좋음 트리 높이가 얕아져 특정 노드의 검색 시간이 감소됨 삽입, 삭제 시 트리 균형을 유지하기 위해 복잡한 연산이 필요합니다. B-트리의 특징 Index를 구성하는 방법으로 가장 많이 사용하는..
트리를 구성하는 각 노드들을 찾아가는 방법을 운행법이라 합니다 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖습니다. 트리의 운행법 이진 트리의 운행법은 다음 세 가지가 있다. Preorder 운행 : Root -> Left -> Right 순으로 운행한다. Inorder 운행 : Left -> Root -> Right 순으로 운행한다. Postorer 운행 : Left -> Right -> Root 순으로 운행한다. 수식의 표기법 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위, 전위, 후위 표기법이 됩니다. 스레드 이진 트리(Threaded Binary Tree) 스레드 이진 ..
트리의 정의 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태 가족의 계보(족보), 연산 수식, 회사 조직 구조도, 히프(Heap) 등을 표현하기에 적합 트리 관련 용어 노드 : 트리의 기본 요소로 자료 항목과 다른 항목에 대한 가지를 합친 것 근 노드 : 트리의 맨 위에 있는 노드 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지 수 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 도그, 즉 Degree가 0인것 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드 조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르는 경로상에 있는..