"트리"의 두 판 사이의 차이

2020년 8월 12일 (수) 11:37 기준 최신판

트리(tree)는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.

특징[편집]

그래프의 한 종류 이다. '최소연결 트리'라고도 불린다.
트리는 계층 모델이다.
임의의 노드에서 다른 노드로 가는 경로는 유일하다.
회로(cycle)가 존재하지 않는다.
모든 노드는 서로 연결되어 있다.
엣지를 하나 자르면 트리가 두개로 분리된다.
엣지의 수는 노드의 수에서 1을 뺀 것과 같다. (엣지 = 노드 - 1)

구조[편집]

node: 트리를 구성하고 있는 각 요소
Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
Root Node: 최상위 계층에 존재하는 노드
level: 트리의 특정 깊이를 가지는 노드의 집합
degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
Terminal Node(=leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.^[1]

트리 순회 (tree traversal)[편집]

트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한 번만 중복 없이 방문해야 한다.
노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉜다.
^[2] ^[2]

전위순회 (preorder)[편집]

루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal)라고도 한다. - 1 -> 2 -> 4 -> 5 -> 3^[2]

중위순회 (inorder)[편집]

루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)라고도 불린다. - 4 -> 2 -> 5 -> 1 -> 3^[2]

후위순회 (postorder)[편집]

루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식 - 4 -> 5 -> 2 -> 3 -> 1^[2]

이진 트리 (binary tree)[편집]

이진 트리(binary tree) : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.

이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)

깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)

이진트리는 완전 이진 트리 (completable binary tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.^[1]

완전 이진 트리 (completable binary tree)[편집]

^[1]

트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1 이하이고 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리이다.

전 이진 트리 (full binary tree)[편집]

^[1]

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

포화 이진 트리 (perfect binary tree)[편집]

모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다.

전 이진 트리이면서 완전 이진 트리인 경우이다.^[1]

이진 탐색 트리 (binary search tree)[편집]

이진 탐색 트리(binary search tree) : 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다.

이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.

연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.^[2]

^[2]

속성[편집]

각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
중복된 노드가 없어야 한다.
왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색트리이다.
이진 탐색트리를 순회할 때에는 중위순회(inorder)방식을 사용한다.

- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로^[2]

^[2] 위의 그림에서 중위순회를 사용한다면, 순서는 1, 3, 5, 7, 8, 10 순서로 순회한다.^[2]

각주[편집]

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 adam2,〈자료구조 Tree〉, 2020년 4월 5일
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 ^2.9 hanrimjo,〈이진 탐색 트리〉, 2020년 2월 7일

참고자료[편집]

adam2,〈자료구조 Tree〉, 2020년 4월 5일</ref>
hanrimjo,〈이진 탐색 트리〉, 2020년 2월 7일

같이 보기[편집]

자료구조

이 트리 문서는 데이터에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

개발 : 프로그래밍, 소프트웨어, 데이터^□^■^⊕, 솔루션, 보안, 하드웨어, 컴퓨터, 사무자동화, 인터넷, 모바일, 사물인터넷, 게임, 메타버스, 디자인

데이터	ACID • CRUD • CSV • DAO • DB • DBMS • DB 명령어 • DCL • DDL • DML • DTO • ERD • ETL • JDBC • LOD • MDM • ODBC • RDBMS • RDF • SQL • 가상 데이터베이스 • 관계형 데이터베이스 • 그래프 • 기본키(PK) • 내부조인 • 널 • 노드 • 다이어그램 • 대리키 • 대체키 • 데이터 • 데이터댐 • 데이터마트 • 데이터 모델링 • 데이터뱅크 • 데이터베이스(DB) • 데이터베이스 언어 • 데이터 사이언스 • 데이터 사전 • 데이터 웨어하우스 • 데이터 정의어(DDL) • 데이터 제어어(DCL) • 데이터 조작어(DML) • 데이터 클러스터 • 데이터 토큰 (문자열) • 데이터 통합 • 덱 • 디비서버 • 라이트조인 • 락 • 레코드 • 레프트조인 • 로그 • 로그파일 • 로깅 • 롤백 • 리두로그 • 릴레이션 • 마스터데이터 • 마스터데이터관리(MDM) • 마이그레이션 • 메타데이터 • 배열 • 뷰 • 빅데이터 • 서브쿼리 • 수퍼키 • 순차리스트 • 스키마 • 스택 • 슬로우쿼리 • 엔티티 • 역정규화 • 연결리스트 • 외래키(FK) • 외부조인 • 인덱스 • 인덱싱 • 인젝션 • 자료구조 • 정규화 • 정보 • 조인 • 커밋 • 쿼리 • 큐 • 키 • 타깃 • 테이블 • 튜플 • 트랜잭션 • 트리 • 트리거 • 티비마이그레이터 • 풀조인 • 프로시저 • 필드 • 해시 • 해시맵 • 해시태그 • 해시테이블 • 해시함수 • 해싱 • 후보키

데이터베이스 관리 시스템 (DBMS)	관계형 데이터베이스 관리 시스템(RDBMS) • 노에스큐엘(NoSQL) • 데이터베이스 관리 시스템(DBMS) • 더비 • 디비투(DB2) • 레디스 • 마리아디비(MariaDB) • 마이에스큐엘(MySQL) • 몽고디비 • 빅테이블 • 사이베이스 • 선디비 • 알티베이스 • 액세스 • 에스큐엘(SQL) • 에스큐엘라이트(SQLite) • 에이치베이스 • 엠에스에스큐엘(MS-SQL) • 오라클(Oracle) • 인터베이스 • 인포믹스 • 카산드라 • 카우치디비 • 큐브리드 • 티베로 • 파이어버드 • 포스트그레스큐엘(PostgreSQL) • 하이퍼테이블

DB 명령어	alter • array • create • delete • drop • from • full join • grant • inner join • insert • join • left join • null • order by • outer join • rename • revoke • right join • select • truncate • update • where

시스템 연계	API • CGI • EAI • ESB • JPA • RSS • SOA • SOAP • SSL • SSO • web3.js • XML • 디비투디비(DB-to-DB) • 레스트풀(RESTful) • 상호운용성 • 시스템 인터페이스 • 신디케이션 API • 오픈 API • 웹 API • 웹개방성 • 윈도우 API • 자바 API • 크롤링 • 프라이빗 API

위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반

[tree-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 adam2,〈자료구조 Tree〉, 2020년 4월 5일

[binary_search_tree-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 ^2.9 hanrimjo,〈이진 탐색 트리〉, 2020년 2월 7일

[1]

[2]

@@ 3번째 줄: / 3번째 줄: @@
 * 그래프의 한 종류 이다. '최소연결 트리'라고도 불린다.
 * 트리는 계층 모델이다.
-* 임의의 노드에서 다른 노드로 가는 경로는 유일하다
+* 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
 * 회로(cycle)가 존재하지 않는다.
 * 모든 노드는 서로 연결되어 있다.
 * 엣지를 하나 자르면 트리가 두개로 분리된다.
 * 엣지의 수는 노드의 수에서 1을 뺀 것과 같다. (엣지 = 노드 - 1)
 == 구조 ==
 [[파일:트리.png|600픽셀]]<ref name='tree'>adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref> <br>
@@ 17번째 줄: / 18번째 줄: @@
 * '''Terminal Node(=leaf Node, 단말 노드)''' : 하위에 다른 노드가 연결되어 있지 않은 노드
 * '''Internal Node(내부노드, 비단말 노드)''' : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.<ref name='tree'></ref>
-== 트리 순회(Tree Traversal) ==
+== 트리 순회 (tree traversal) ==
-트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한번만 중복없이 방문해야한다.<br>
+트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한 번만 중복 없이 방문해야 한다.<br>
-노드를 방문 하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)세가지로 나뉜다.<br>
+노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉜다.<br><ref name='binary_search_tree'>hanrimjo,〈[https://velog.io/@hanrimjo/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree-8gk6ablvfx 이진 탐색 트리]〉, 2020년 2월 7일</ref>
-[[파일:트리순회.png]]
+[[파일:트리순회.png]]<ref name='binary_search_tree'></ref>
-=== 전위순회(preorder) ===
+=== 전위순회 (preorder) ===
-트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal) 라고도 한다.
+루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal)라고도 한다.
-- 1 -> 2 -> 4 -> 5 -> 3
+- 1 -> 2 -> 4 -> 5 -> 3<ref name='binary_search_tree'></ref>
-=== 중위순회(inorder) ===
+=== 중위순회 (inorder) ===
-=== 후위순회(postorder) ===
+루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)라고도 불린다.
+- 4 -> 2 -> 5 -> 1 -> 3<ref name='binary_search_tree'></ref>
+=== 후위순회 (postorder) ===
+루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식
+- 4 -> 5 -> 2 -> 3 -> 1<ref name='binary_search_tree'></ref>
-== 이진 트리(Binary Tree) ==
+== 이진 트리 (binary tree) ==
-* '''이진 트리(Binary Tree)''' : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.
+* '''이진 트리(binary tree)''' : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.
 :이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)
 :깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)
-:이진트리는 완전 이진 트리(Completable Binary Tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.<ref name='tree'></ref>
+:이진트리는 완전 이진 트리 (completable binary tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.<ref name='tree'></ref>
-=== 완전 이진 트리(Completable Binary Tree) ===
+=== 완전 이진 트리 (completable binary tree) ===
 [[파일:완전이진트리.png|700픽셀]]<ref name='tree'></ref><br>
 :트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1 이하이고 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리이다.
-=== 전 이진 트리(Full Binary Tree) ===
+=== 전 이진 트리 (full binary tree) ===
 [[파일:전이진트리.png|700픽셀]]<ref name='tree'></ref><br>
 :모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
-=== 포화 이진 트리(Perfect Binary Tree) ===
+=== 포화 이진 트리 (perfect binary tree) ===
 :모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다.
 :전 이진 트리이면서 완전 이진 트리인 경우이다.<ref name='tree'></ref>
+== 이진 탐색 트리 (binary search tree) ==
+* '''이진 탐색 트리(binary search tree)''' : 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다.
+:이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
+:예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.
+:연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.<ref name='binary_search_tree'></ref>
+[[파일:이진탐색트리.png]]<ref name='binary_search_tree'></ref>
+=== 속성 ===
+* 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
+* 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
+* 중복된 노드가 없어야 한다.
+*왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색트리이다.
+*이진 탐색트리를 순회할 때에는 중위순회(inorder)방식을 사용한다.
+:- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로<ref name='binary_search_tree'></ref>
+[[파일:이진탐색트리속성.png]]<br><ref name='binary_search_tree'></ref>
+위의 그림에서 중위순회를 사용한다면, 순서는 1, 3, 5, 7, 8, 10 순서로 순회한다.<ref name='binary_search_tree'></ref>
+{{ 각주 }}
+== 참고자료 ==
+* adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref>
+* hanrimjo,〈[https://velog.io/@hanrimjo/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree-8gk6ablvfx 이진 탐색 트리]〉, 2020년 2월 7일
 == 같이 보기 ==
 * [[자료구조]]
-{{데이터|토막글}}
+{{데이터|검토 필요}}

위키원

이름공간

변수

보기

더 보기

검색