트리와 이진트리

쉽게 쓰는, 그리고 많이 접하는 구조.........트리

 

트리는 알고리즘 테스트에서도 많이 출제하고, 해당 구현, 개념을 알고있는 것이 굉장히 좋다

그러면 트리와 이진트리 , binary tree에 대해서 알아보자

 

1. 트리

트리는 쉽게 노드,경로 등으로 이루어져 있으며, 해당 트리는 아래와 같은특징을가진다.

 - 모든 노드들은 연결되어있다.

 - 노드들에 대한 회신 cycle이 존재하지 않는다.

 - 임의의 노드에서 다른 노드로 이동하는 경로는 유일하다.

 

2. 이진 트리

 - 자식 노드가 최대 두개로 이루어진 트리이다.

모든 노드는, 공백이나 왼쪽 혹은 오른쪽의 서브노드를 가지고있다.

 

그러면 2개 이상을 가지는 트리는 어떻게 명명 할까?

바로, b-tree라고 한다. 

일단, 이렇게 한가지의 노드에 키값이 있고, 해당 키를 바탕으로 자식 노드리스트들의 값을 가질수 있다.

 

해당 그래프에서 18을 검색한다고 하면, 레벨2의 기준으로 18 보다 작은 값들만 필터링 해서 검색을 하고

해당 검색 기준으로, 하나씩 찾아보면서 검색을 완료하면 종료하도록 설계한다.

 

비트리는 이진트리를 진화시킨 모델로, 해당 관련은 key별로, 데이터 값들을 관리할때 편하게 쓰인다.