Tree

# Tree

트리는 한 노드가 여러 노드를 가르킬 수 있는 비선형적 자료구조 입니다. 리스트나 스택, 큐는 선형적 자료구조로 이전 데이터와 다음 데이터의 순서가 존재했습니다. 물론 트리도 내부적으로 순서정보를 가질 수는 있지만, 트리에서 순서정보는 그렇게 중요한 요소가 아닙니다.

트리는 그래프자료 구조의 일종이며, 데이터 구조의 계층적인 속성(상하관계)을 표현할 때에 사용할 수 있습니다. 

이렇게 트리를 구성하는 각 구성요소들을 노드라고 합니다,

부모노드가 없는 최상위 노드를 root노드라고 하며, 트리는 최대 하나의 루트노드를 가질 수 있습니다. 그리고 노드를 연결하는 선을 edge라고합니다. 그래서 트리는 root로 시작해 edge로 연결된 노드들로 구성되어 있습니다. 

트리안의 계층구조에서 상위계층에 있는 노드를 부모노드, 부모노드의 하위계층에 있는 노드를 자식노드라고 합니다. 같으 부모노드 밑에 있는 다른 노드들은 형제노드라고 합니다 (부모,자식 노드는 상대적인 개념입니다) 자식 수는 degree로 표현하며 자식이없는 노드는 leaf노드로 노드의 끝노드이기 떄문에 터미널 노드라고도 합니다

노드의 경로는 path라고 합니다 이때 경로는 중복노드를 포함하지 않습니다. 노드까지의 거리를 깊이 depth라고 합니다. 가장 큰 depth는 트리의 높이라고도 합니다.  같은 depth를 가진 노드들의 집합을 그 트리의 level이라고 합니다 root노드는 level0입니다.

트리는 트리의 하부 트리를 가진다는 재귀적 특성을 가집니다

트리는 하나의 자식만 가질 수도 있는데, 이런 경우를 경사트리라고 합니다 왼쪽 자식만 갖는 경우 왼쪽 경사 트리, 오른쪽 자식만 갖는 경우 오른쪽 경사트리, 왼쪽-오른쪽 번갈아가면서 있는 트리도 경사트리의 일종입니다

트리는 특성에 따라 여러 종류의 트리로 구분될수있습니다. 이진트리, AVL트리, 레드-블렉트리, B-트리, B+트리, 세그먼트 트리, 트라이가 있습니다. 이중 이진트리는 다른 트리들의 파생트리로 많이 사용됩니다.