-
[자료구조] 이진트리의 개념직장일기/용어개념 정리 2021. 5. 19. 12:34
트리를 사용하는 이유
선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에, 트리라는 자료구조를 활용한다.
선형 데이터 구조는 데이터를 구성하는 원소들이 순차적으로 나열된 데이터 구조이다. 리스트(선형, 연결) , 스택, 큐, 데크 같은 것들이다.
계층으로 나타낼 수 있는 예로, 가족 관계도를 생각해보면..
가족 관계를 선형으로 나타내기는 굉장히 어렵다. 또한, 선형데이터로 나타낸 가족 관계도에서 내 조카를 찾아보라고 하면 굉장히 찾기 어려울 테다.
트리는 주로 탐색을 하기 위해 사용된다. 폴더 구조, DBMS, 검색 엔진 등에서 활용이 된다.
트리의 개념
트리(Tree)란, 배열, 링크드리스트, 스택, 큐와 같이 일직선 개념의 자료구조가 아니라 부모-자식 개념을 가지는 자료구조이다. 최상위에 잇는 노드를 루트 노드라고 하며 루트 노드는 부모를 가지지 않는다.
데이터를 저장할 수 있으며 시간복잡도 상으로 우수하기 때문에 여러가지 부수적인 자료구조나 알고리즘을 만드는데도 사용된다.
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다.
이진트리가 중요한 이유는 매우 간단해서,
N링크법을 사용하는 트리에 비해 문제를 일으킬 상황이 적다.
시간 복잡도 면에서 N링크법에 밀리지만 사용성과 편리성이 앞선다
이진 탐색 트리(binary search tree)
기본적인 특징은 이진 트리와 같지만 하나 다른 점은 자기 왼쪽에는 자신보다 값이 작은 노드가, 오른쪽에는 자신보다 값이 큰 노드가 와야한다는 것이다.
특정 노드를 기준으로 왼쪽에는 보다 작은 값이, 오른쪽에는 보다 큰 값을 가진 노드가 위치한 트리를 이진 탐색 트리라
고 한다
완전 이진 트리(complete binary tree)
완전 이진 트리는 이진 트리의 조건을 만족하면서 아래 조건을 만족해야 한다.
1. 마지막 레벨(위 그림에서는 레벨 3)을 제외한 나머지 레벨에서는 노드들이 꽉 차있어야 한다.
2. 마지막 레벨은 왼쪽부터 노드가 채워져 있어야 한다.위 그림 왼쪽 트리가 완전 이진 트리가 되지 못하는 이유는 마지막 레벨에서 왼쪽부터 노드를 채우지 않았기 때문이다.(20의 자식인 30이 왼쪽이 아닌 오른쪽에 있다.)
full binary tree
full binary tree는 이진 트리의 조건을 만족하면서 아래 조건을 만족해야 한다.
1. 루트 노드를 제외한 모든 노드들은 2개의 자식 노드를 가지거나 자식 노드가 하나도 없어야 한다.따라서, 위 완전 이진 트리 그림에서 노드 15가 없어진다면 full binary tree입니다.
출처: https://prosaist0131.tistory.com/entry/트리에-대하여 [내일은 개발을 잘 할 거야]
'직장일기 > 용어개념 정리' 카테고리의 다른 글
폴더와 디렉토리에 대해서 (0) 2021.05.20 사물인터넷(Internet of things, IoT) (0) 2021.05.19