본문 바로가기

Tree4

[Java] 트리 Tree 3 - 이진 탐색 트리 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진트리 이진트리 기반의 탐색을 위한 자료 구조 이진 탐색 트리의 성질 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리 키들은 루트 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 찾고자 하는 키 값이 이진트리의 루트 노드의 킷값과 비교해 루트 노드보다 작으면 원하는 키값은 왼쪽 서브 트리에 있고, 루트 노드보다 크면 원하는 키 값은 오른쪽 서브 트리에 있다. ex. 왼쪽 서브 트리의 값들 (3, 7, 12)는 루트 노드인 18보다 작다. 오른쪽 서브 트리의 값들 (26, 31, 27)은 루트 노드인 18보다 크다. 위의 이진 탐색 트.. 2020. 12. 31.
[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현 4. 이진트리의 순회 이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V 왼쪽 서브 트리 방문을 L 오른쪽 서브트리 방문을 R 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다. 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 문제의 구조는 같고 크기만 작아지는 경.. 2020. 11. 6.
[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5.
[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법 1. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 한 개 이상의 노드로 이루어진 유합 집합 A~J를 노드(node) 이들 중 하나의 하나의 노드를 루트(root) 노드라 하고 나머지 노드들을 서브 트리(sub tree)라 한다. 계층적 구조에서 가장 높은 곳에 있는 노드 A가 루트가 됨 루트와 서브트리는 간선(edge)으로 연결됨 ex) {A, B, C, D, E, F, G, H, I, J} 중에서 루트 노드는 A이고 나머지 {B, E, F, G}, {C, H}, {D, I, J}의 3개의 노드 집합들은 A의 서브 트리라 한다. 다시 서브 트리 {B, E, F, G}의 루트는 B가 되고, 나머지 {E}, {F}, {G} 노드들은 다시 3개의 서브 트리로 나뉜다. 나머지도 마찬가지이다.. 2020. 11. 3.
반응형

티스토리툴바