Data Structure/Tree (4) 썸네일형 리스트형 트리 : [4] 이진탐색트리 이진탐색트리(Binary Search Tree)는 탐색작업을 효율적으로 수행하기 위해 만들어진 이진트리다. ㄴ 임의의 노드 기준으로 노드의 값(Key, value)보다 (1) 작으면 왼쪽, (2) 크면 오른쪽에 저장한다.ㄴ 결과적으로 가장 왼쪽 끝의 자식노드에는 가장 작은 값을, 가장 오른쪽 끝의 자식노드에는 가장 큰 값을 갖는다.ㄴ 이진탐색트리를 중위순회하게되면, 오름차순으로 정렬된 배열을 출력한다. 이진탐색트리 연산위에서 말한 바와 같이 이진탐색트리를 구현하기 위해선 (1) 삽입, (2) 삭제연산을 구현해야 한다. (1) 삽입연산이진탐색트리가 존재할 때, 새로운 값을 삽입하고자 할 때 사용하는 방법이다. 핵심은 새롭게 삽입하고자 하는 변수(key)와 트리 내 존재하는 노드의 값을 순차적으로 비교하여 .. 트리 : [3] 이진트리 순회 순회(traversal)란, 트리의 노드들을 빠뜨리거나 중복하지 않고 모두 방문하는 탐색 방법이다. L, V, R을 각각 왼쪽으로 이동, 방문(또는 출력), 오른쪽으로 이동을 나타낸다고 할 때, 총 6가지 방법으로 L, V, R을 나열할 수 있다. 그러나 트리 : [2] 이진트리에서 언급한 바와 같이, 이진트리에는 왼쪽 → 오른쪽으로 이동이 정해져있다고 가정하기 때문에 (1) VLR, (2) LVR, (3) LRV 총 3가지 조합만 가능하다. 이 각각을 (1) 전위순회(preorder traversal), (2) 중위순회(inorder traversal), (3) 후위순회(postorder traversal)이라고 한다. 그 외 레벨순서대로 이진트리를 방문하는 (4) 레벨순회(lev.. 트리 : [2] 이진트리 이진트리(Binary Tree)의 경우, 상대적으로 많이 사용하는 자료구조로 다음과 같은 특징을 갖는다. 이진트리 개념1. 모든 노드가 2개의 서브트리를 갖는 트리다. (서브트리는 공백(∅)을 포함한다.) = 모든 노드는 최대 2개의 자식노드를 갖을 수 있다. (자식노드는 ∅을 포함한다.) = 모든 노드의 차수(degree)는 2 이하다.2. 이진트리의 서브트리 간에는 왼쪽 → 오른쪽 순서가 존재한다. 이진트리의 성질1. 노드가 N개이면, 링크는 N−1개다. (=루트를 제외한 모든 노드는 부모노드가 존재) 2. 레벨(level)이 i일 때, 해당 레벨이 갖을 수 있는 최대 노드 수 : 2i−1 ㄴ 높이(heigh.. 트리 : [1] 일반트리 트리(Tree)는 다음과 같은 특성을 갖는 자료구조다. (1) 위계구조를 나타내는 자료 구조다.(2) 트리의 원소(노드) 간 1:N의 비선형 구조를 갖는다. 트리 관련 용어 정리 (1) 노드(Node) : 트리의 구성요소 (2) 루트(Root) : 노드 중 부모를 갖지 않는 노드 (3) 단말노드(Leaf) : 자식 노드를 갖지 않는 노드 (4) 레벨(Level) : 트리의 각 층이 갖는 순서로, 루트는 0 또는 1이 된다. (5) 높이(Height) : 트리의 최대 레벨 (6) 차수(Degree) : 자식 노드 수 (7) 서브트리(Subtree) : 노드와 그 자식 노드로 이뤄진 집합 (8) 포레스트.. 이전 1 다음
