트리

Tree는 스택과 큐와 달리 비선형 자료구조로, 계층적 관계를 표현하는 자료구조이다.

 

트리의 구성 요소

• 노드(Node) : 트리를 구성하고 있는 각각의 요소를 의미한다.
• 루트(Root) : 트리의 가장 상단에 있는 노드를 의미한다.
• 간선(Edge) : 노드와 노드를 연결하는 선을 의미한다.
• 단말 노드(Leaf Node) : 하위에 다른 노드가 연결되어 있지 않는, 즉 자식이 없는 노드를 의미한다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 한다. 레벨의 값을 0부터 시작하고, 루트 노드의 레벨은 0이다. 트리의 최고 레벨을 가리켜 해당 트리의 높이라고 한다.

 

트리에는 대표적으로 이진트리가 있다. 이진트리란 루트 노드를 중심으로 두개의 서브 트리로 나뉘어 지고, 나누어진 서브트리 또한 이진 트리임을 만족하는 트리이다. 재귀적인 의미를 가진 트리이다. 공집합, 루트밖에 없는 트리도 이진트리이다.

 

이진 트리를 이용해서 BST(Binary Search Tree)를 만들 수 있다. 

BST는 부모 노드를 기준으로 부모의 키가 왼쪽 자식 노드의 키보다 크거나 같고, 오른쪽 자식 노드의 키보다 작은 이진트리이다. 이진트리는 좌우 서브 트리가 밸런스 있게 존재한다는 가정하에 탐색하는데 O(h)≒O(log n)의 시간 복잡도를 갖는다. 하지만 트리가 한쪽으로 치우쳐진 worst case에서는 O(n)의 시간복잡도를 가진다.