나무 소개

Tree개별 요소 또는 노드 간의 계층 적 관계를 나타내는 개별 구조입니다. 부모에 자식이 두 개 이하인 트리를 이진 트리라고합니다.

나무와 그 속성

Definition− 트리는 연결된 비순환 무 방향 그래프입니다. $ G $의 모든 정점 쌍 사이에는 고유 한 경로가 있습니다. N 개의 정점이있는 나무는 $ (N-1) $ 개의 가장자리를 포함합니다. 0 도인 정점을 나무의 뿌리라고합니다. 1 도인 정점을 트리의 리프 노드라고하며 내부 노드의 정도는 최소 2입니다.

Example − 다음은 나무의 예입니다 −

나무의 중심과 이중 중심

나무의 중심은 편심이 최소화 된 꼭지점입니다. 트리 $ G $에서 정점 $ X $의 이심률은 정점 $ X $와 트리의 다른 정점 사이의 최대 거리입니다. 최대 편심은 나무 지름입니다. 나무에 중심이 하나만있는 경우 중앙 트리라고하고, 하나 이상의 중심 만있는 경우 Bi-central Tree라고합니다. 모든 나무는 중앙 또는 이중 중앙입니다.

나무의 중심과 이중 중심을 찾는 알고리즘

Step 1 − 주어진 트리에서 차수가 1 인 모든 정점을 제거하고 입사 모서리도 제거합니다.

Step 2− 단일 정점 또는 가장자리로 연결된 두 정점이 남을 때까지 1 단계를 반복합니다. 하나의 정점이 남아 있으면 그것은 나무의 중심이고 가장자리에 의해 결합 된 두 개의 정점이 남아 있으면 그것은 나무의 이중 중심입니다.

Problem 1

다음 트리의 중심 / 양심을 찾으십시오-

Solution

처음에는 1 도의 모든 정점을 제거하고 입사 모서리를 제거하고 다음 트리를 얻습니다.

다시, 우리는 차수 1의 모든 정점을 제거하고 입사 모서리를 제거하고 다음 트리를 얻습니다.

마지막으로 우리는 단일 정점 'c'를 얻고 알고리즘을 중지합니다. 하나의 정점이 있기 때문에이 트리에는 중앙 'c'가 하나 있고 트리는 중앙 트리입니다.

Problem 2

다음 트리의 중심 / 양심을 찾으십시오-

Solution

처음에는 1 도의 모든 정점을 제거하고 입사 모서리를 제거하고 다음 트리를 얻습니다.

다시, 우리는 차수 1의 모든 정점을 제거하고 입사 모서리를 제거하고 다음 트리를 얻습니다.

마지막으로 두 개의 정점 'c'와 'd'가 남았으므로 알고리즘을 중지합니다. 가장자리로 연결되는 두 개의 정점이 남아 있기 때문에이 나무는 이중 중심 'cd'를 가지며 나무는 이중 중심입니다.

레이블이있는 나무

Definition− 레이블이있는 트리는 정점에 1부터 n까지의 고유 번호가 할당 된 트리입니다. 우리는 일반 공식을 추측하기 위해 손으로 n의 작은 값에 대해 그러한 나무를 셀 수 있습니다. n 개의 꼭지점의 레이블이 지정된 트리의 수는 $ n ^ {n-2} $입니다. 두 개의 레이블이있는 트리는 그래프가 동형이고 두 트리의 해당 지점에 동일한 레이블이있는 경우 동형입니다.

예

레이블이없는 나무

Definition− 레이블이없는 트리는 정점에 번호가 할당되지 않은 트리입니다. n 개의 꼭지점의 레이블이있는 트리의 수는 $ \ frac {(2n)!} {(n + 1)! n! } $ (n ^번째 카탈로니아 숫자)

예

뿌리 나무

루트 트리 $ G $는 트리의 루트라고하는 특수 노드가있는 연결된 비순환 그래프이며 모든 에지는 루트에서 직접 또는 간접적으로 발생합니다. 정렬 된 루트 트리는 각 내부 정점의 자식이 정렬 된 루트 트리입니다. 뿌리 나무의 모든 내부 정점에 자식이 m 개 이하인 경우이를 m-ary 나무라고합니다. 뿌리 나무의 모든 내부 정점에 정확히 m 개의 자식이있는 경우 전체 m-ary 트리라고합니다. $ m = 2 $이면 루트 트리를 이진 트리라고합니다.

이진 검색 트리

이진 검색 트리는 다음 속성을 만족하는 이진 트리입니다-

$ X $ 정점의 왼쪽 하위 트리 $ V, Value (X) \ le Value (V) $
정점 $ V의 오른쪽 하위 트리에있는 $ Y $, Value (Y) \ ge Value (V) $

따라서 내부 노드 $ V $의 왼쪽 하위 트리의 모든 정점 값은 $ V $보다 작거나 같고 내부 노드 $ V $의 오른쪽 하위 트리의 모든 정점 값은 $ V $보다 크거나 같습니다. 루트 노드에서 가장 깊은 노드까지의 링크 수는 이진 검색 트리의 높이입니다.

예

BST에서 키를 검색하는 알고리즘

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)

이진 검색 트리의 복잡성

	평균 사례	최악의 경우
공간 복잡성	의 위에)	의 위에)
검색 복잡성	O (로그 n)	의 위에)
삽입 복잡성	O (로그 n)	의 위에)
삭제 복잡성	O (로그 n)	의 위에)