Tree
◎ Tree
-> 자료구조에서 Tree는 그래프의 한 종류인 단방향 그래프다. 하나의 뿌리로부터 여러 개의 가지가 뻗어나온 형태와 유사하다.
-> 트리는 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이며, 계층 구조로 구성되어 있다.
-> 트리 구조는 루트에서 시작하여 아래에 있는 여러 개의 데이터를 간선(edge)로 연결한다. 각 데이터를 노드(node)라고 하며, 두 노드가 상하 계층으로 연결되어 있는 경우 상위 노드를 부모노드, 하위 노드를 자식노드라 한다.
-> 자식이 없는 노드는 리프 노드(leaf node)라 한다.
-> 트리의 구성을 깊이, 높이, 레벨로 구분할 수 있다.
-> 깊이 : 루트에서 하위 계층의 특정 노드까지의 깊이 위 트리에서 루트 노드 8의 깊이는 0이고, 5와 13의 깊이는 1이다.
-> 높이 : 리프 노드를 기준으로 루트 까지의 높이. 부모 노드는 자식 노드의 가장 높은 높이 값에 +1을 한 값을 높이로 가진다. 트리 구조를 높이를 표현할 경우 리프노드의 높이를 0으로 지정한다. 위 트리에서 2,7,12,18의 높이는 0이고, 13은 11의 높이 + 1인 2가 된다. 루트 노드 8의 높이는 3이다.
-> 레벨 : 트리에서 같은 깊이를 가지고 있는 노드들을 묶어서 레벨로 표현한다. 루트 노드인 8은 레벨이 1이다.
또한 같은 레벨에 위치한 노드들을 형제 노드(sibling node)라고 한다.
-> 전체 트리 내부에 트리 구조를 가진 작은 트리를 서브 트리라 한다. 트리에 구성된 5,2,7트리와 13,11,18,12는 서브 트리다.
◎ Binary Search Tree
-> 트리는 효율적인 탐색을 위해 사용한다. binary search tree, 이진 탐색 트리는 트리 구조를 가지며 효율적인 탐색을 위해 사용하는 트리다.
-> 이진 트리 : 자식 노드가 최대 2개인 노드들로 구성된 트리다. 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
-> 이진 트리는 정 이진 트리, 포화 이진 트리, 완전 이진 트리로 나눈다.
☆ 오늘 학습의 중요 포인트 및 이해도
학습 이해도 : ★★★완벽히 이해함, ★★이해함 ★ : 미흡
트리 : ★★★
이진 탐색 트리 : ★★(레벨, 깊이, 높이의 개념과 차이에 대해 좀 더 공부해야함)