자료구조 트리(Tree)에 관한 PPT

소개

자료구조 tree에 관한 ppt입니다.

목차

-트리의 정의
-트리의 종류
-트리의 표현법
-이진트리의 운행
-트리의 경로길이
-트리의 삽입과 삭제

본문내용

￭ 트리의 구성요소
노드(node)
- 정점(vertics)인
- 그들을 연결하는 가지(branch)로 이루어진 그래프(graph)형식의 구조
- 나무나 가족 관계처럼 한 줄기에서 계속 가지를 치는 형태

트리의 정의

※ 트리 T는 한 개 이상의 노드들로 이루어진 유한집합으로 다음의 조건
을 만족한다.
- 루트(root)로 불리는 특정한 1개의 노드가 존재한다.
- 루트를 제외한 나머지 노드들은 T1,…,Tn (n≥0)의 부분집합으로
나뉘어지며, 이들 각각은 하나의 트리가 된다. 이때 이들 트리를
루트의 부트리(sub tree)라 한다.

<중 략>

스레드 트리의 오른쪽 부트리가 없을 경우 오른쪽 노드 삽입 방법

① parent의 rightThread 값을 거짓으로 한다.

② child의 leftThread 와 child의 rightThread 값을 참으로 한다.

③ child의 leftChild가 parent를 가리키도록 한다.

④ child의 rightChild 값을 parent 의 rightChild 값으로 한다.

⑤ parent의 rightChild 가 child를 가리키도록 한다.

<중 략>

오른쪽 부트리가 있을 경우(알고리즘)

※ 이진 탐색 트리의 성능
트리의 구조와 노드에 접근하는 확률에 의해 결정되며, 트리의 구조는
노드의 삽입이나 삭제에 의해 결정된다.

※ 휴리스틱(heuristic) 알고리즘
최적에 가까운 이진 탐색 트리를 만들어 냄

1. 접근 빈도가 높은 키를 가진 노드를 트리의 루트에 가깝게 놓는다.
2. 좌측과 우측 서브트리가 가능한 같은 수의 노드를 가질 수 있게 한다.

참고자료

· 없음