자료구조
-
자료구조...65일지 2021. 3. 10. 11:07
이진 탐색 트리의 삭제 연산 삭제 연산의 경우 삭제되는 노드가 가진 자식의 수에 따라 연산이 달라지게 된다. 자식 노드가 없는 경우 대상 노드를 제거하고 연산을 종료한다. 자식 노드가 하나인 경우 대상 노드를 제거하고 자식 노드와 위치를 바꾼다. 자식 노드가 두 개인 경우 왼쪽 자식을 선택할지 오른쪽 자식을 선택할지에 따라 연산이 달라진다. 왼쪽 자식에게 계승하는 경우 대상 노드 삭제 후 왼쪽 서브 트리에서 가장 큰 값을 가진 노드와 위치를 바꾼다. 오른쪽 자식에게 계승하는 경우 대상 노드 삭제 후 오른쪽 서브 트리에서 가장 작은 값을 가진 노드와 위치를 바꾼다.
-
자료구조...64일지 2021. 3. 3. 08:30
삽입 연산 삽입하려는 원소가 이진 탐색 트리에 존재하는지 탐색한 뒤 존재하는 경우 연산을 종료하고 존재하지 않으면 해당 위치에 원소를 삽입하고 연산을 종료한다. 위와 같은 이진 탐색 트리에 4를 삽입하면 다음과 같은 과정을 통해 연산을 수행하게 된다. 노드의 값(8) > 찾으려는 값(4) 왼쪽 서브 트리로 이동하여 탐색 연산 진행 노드의 값(3) 찾으려는 값(4) 왼쪽 서브 트리로 이동하여 탐색 연산 진행 탐색 연산 실패 해당 위치에 4를 삽입하고 연산 종료 더보기 참고문헌 이지영.(2013.07.30).C로 배우는 쉬운 자료구조
-
자료구조...63일지 2021. 2. 23. 08:23
이진 탐색 트리 탐색을 위한 이진 트리로 데이터의 크기에 따라 노드의 위치를 결정하며 다음과 같이 정의한다. 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다. 이진 탐색 트리의 탐색 연산 값을 찾을 때에는 루트에서 시작해서 찾으려는 값을 비교하여 진행한다. 노드의 값 = 찾으려는 값 탐색 성공 노드의 값 > 찾으려는 값 왼쪽 서브 트리로 이동하여 탐색 연산 수행 노드의 값 < 찾으려는 값 오른쪽 서브 트리로 이동하여 탐색 연산 수행 참고문헌 참고문헌 이지영.(2013.07.30).C로 배우는 쉬운 자료구조
-
자료구조...62일지 2021. 2. 16. 08:13
이진트리의 순회 이진트리에 존재하는 모든 노드를 한 번씩 방문하여 데이터를 처리하는 과정을 순회라고 한다. 데이터를 처리하는 순서에 따라 다음과 같이 구분한다. 전위 순회 데이터를 처리한 뒤 왼쪽 노드, 오른쪽 노드 순서로 이동한다. 중위 순회 왼쪽 노드로 이동한 뒤 데이터 처리를 하고 오른쪽 노드로 이동한다. 후위 순회 왼쪽 노드로 이동한 뒤 오른쪽 노드로 이동하고 데이터 처리를 한다. 위와 같이 A를 루트로 하는 트리를 순회할 때 각각의 순회 방법은 다음과 같다. 전위 순회 A - B - D - E - C 중위 순회 D - B - E - A - C 후위 순회 D - E - B - C - A
-
자료구조...59일지 2021. 1. 21. 11:25
이진트리란 리프 노드를 제외한 노드의 자식이 1개 혹은 2개로 이루어진 트리를 말한다. 즉, 리프 노드를 제외한 모든 노드는 다음의 구조를 지녀야 한다. ※ 각 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 구분하며 각각의 자식 노드가 자식 노드를 가진 경우 자식 노드를 루트로 하는 노드 집단을 서브 트리라고 한다. 이진트리는 다음과 같은 특징을 가진다. n개의 노드를 진 경우 n-1 개의 간선을 가진다. 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 h-1 개이며 최대 개수는 2^(h+1)-1 개가 된다.