전체 글70 제 10장 선택 트리, 숲, 이진 트리 개수 1. 선택 트리합병 정렬 - 차례로 정렬된 데이터 리스트 2개를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정. 선택 트리 - 합병 정렬에 사용하는 특수한 트리. 선택 트리 - 승자 트리와 패자 트리. * 승자 트리 - 각 노드가 두 자식 노드의 작은 값인 완전 이진 트리. * 승자 트리 구축 과정 - 작은 값이 승자로 올라가는 토너먼트 경기와 유사. 트리의 각 내부 노드는 두 자식 노드 값의 승자를 자신의 값으로 함. 결과로 루트 노드는 전체 토너먼트 승자, 트리에서 가장 작은 값을 갖는 노드가 됨. 루트가 결정되면 그 값을 전체 순서 리스트(k개 리스트를 합병한 리스트)에 출력하고 트리에서 삭제. 삭제한 데이터를 가지고 있던 리스트의 다음 데이터를 승자 트리로 올려 보내 승자 트 리를 재구성.. 2024. 12. 22. 제 9장 힙 1. 우선순위 큐힙(heap), 히프 - 피라미드 모양으로 쌓아 올린 더미. 힙은 무엇인가를 쌓아 놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징. 큐 - 먼저 들어간 데이터가 먼저 삭제되는 자료구조. 먼저 줄을 선 사람이 먼저 서비스를 받는 구조. 우선순위 큐 - 먼저 도착 한 사람이 먼저 진료를 받지 않고 응급환자를 먼저 치료하는 경우의 자료구조. 항상 우선순위가 높은 것을 먼저 처리. 그리고 그것이 항상 꼭대기에 있음.2. 힙추상 자료형힙 - 우선순위 큐. 우선순위 큐를 트리로 구현한 것. 트리로 구현하면서 부모와 자식 노드 사이에 일정한 대소관계를 유지해야 하는 조건이 추가됨.■ 힙의 추상 자료형•힙 객체의 정의: 부분적으로 정렬된 완전 이진 트리로 부모 노드는 자식 노드보 .. 2024. 12. 15. 제 8장 스레드 트리 1. 스레드 트리스레드(thread) - 정해진 순회 방법에 따른 방문 순서를 유지하는 포인터를 사용하는 방법. 스레드 트리 - 스레드 포인터를 갖는 이진 트리. 스레드 트리는 스레드라는 포인터를 활용하여 트리 순회를 편리하게 함. 오른쪽 스레드 - 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴.왼쪽 스레드 - 그 노드의 선행 노드. - 후속 노드를 가리키는 하나의 스레드를 사용하는 방법을 사용. 2. 스레드 트리 구현1) 스레드를 저장하는 포인 터를 추가하는 것 - 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정하는 것. 2) 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 잎 노드에 있는 사용하지 않는 포인터.. 2024. 12. 1. 7장 트리(2) 3. 추상 자료형트리- 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조. 트리로 표현할 수 있는 데이터는 매우 광범위하며, 적용할 연산도 응용에 따라 매우 다양.■ 트리의 추상 자료형•트리 객체의 정의: 루트 노드를 갖는 유한 리스트•연산① Tree Creat()= 트리를 생성하고 루트 노드를 가리키는 포인터를 반환한다.② Destroy(Tree) ::= 더 이상 사용하지 않는 트리의 기억 장소를 시스템에 반환 한다.③ Tree Copy_Tree(Tree) :: 트리를 복사하고 새로 생성한 트리의 루트 노드를 가리키는 포인터를 반환한다.④ Insert(n) = 트리에 노드 n을 삽입한다.⑤ Delete() :: 트리에서 노드를 삭제한다. 보통 재구성 단계를 포함한다.⑥ Search() :: 트리에.. 2024. 11. 24. 이전 1 2 3 4 ··· 18 다음