- 부모(Parent) : 다른 노드를 가리키는 노드는 그 노드의 부모가 된다. 루트를 제외한 모든 노드에는 부모가 하나씩 있다.
- 자식(Child) : 루트를 제외한 모든 도느는 그 노드를 가리키는 노드의 자식이 된다.
- 자손(Desceendant) : 특정 노드로부터 자식노드로 이어지는 경로를 따라 도달할 수 있는 모든 노드는 그 특정 노드의 자손이다.
- 조상(Ancestor) : 어떤 노드를 자손으로 삼고 있는 노드는 모두 그 노드의 조상이다.
- 잎(Leaves) : 자식이 없는 노드를 잎이라고 부른다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | class Node { public Node left { get; set;} public Node right { get; set; } public int data { get; set; }
public Node(int data) { this.data = data; } }
class Tree { public Node Root { get; set; }
public void PrintTree(Node Root) { if (Root == null) return;
Console.WriteLine(Root.data); PrintTree(Root.left); PrintTree(Root.right); } }
namespace test2 { class Program { static void Main(string[] args) { Tree tree = new Tree();
tree.Root = new Node(1);
tree.Root.left = new Node(2); tree.Root.right = new Node(3);
tree.PrintTree(tree.Root); } } } |
이진트리(Binary Tree)
보통 트리는 이진트리를 일걷는 경우가 많음
이진트리에서는 한 노드에 자식이 최대 2개까지만 있을 수 있으며, 그 두 자식은 각각 왼쪽 자식과 오른쪽 자식이라고 부름.
이진검색트리(Binary Search Tree)
트리를 써서 정렬된, 또는 순서가 정해진 자료를 저장할 때 사용
노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며 오른쪽 자식의 값은 반드시 자신의 값 이상이다.
룩업연산(Lookup, 트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 알 수 있다.
왼쪽으로만 따라가면 제일 작은 값을 찾을 수 있고, 오른쪽으로만 따라가면 제일 큰 값을 구할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | class Node { public Node left { get; set;} public Node right { get; set; } public int data { get; set; }
public Node(int data) { this.data = data; } }
class Tree { public Node Root { get; set; }
public void InputNode(int value) { if (Root == null) { Root = new Node(value); return; }
else { Node current = Root;
while(current != null) { if(current.data > value) { if (current.left != null) current = current.left; else { current.left = new Node(value); break; } } else { if (current.right != null) current = current.right; else { current.right = new Node(value); break; } }
} } }
public void PrintTree(Node node) { if (node == null) return;
Console.WriteLine(node.data); PrintTree(node.left); PrintTree(node.right); }
public void FindNode(int value) { Node current = Root; while(current != null) { if(current.data == value) { Console.WriteLine("찾음"); return; }
else { if(current.data > value) { current = current.left; }
else { current = current.right; } } }
Console.WriteLine("못찾음"); } }
namespace test2 { class Program { static void Main(string[] args) { Tree tree = new Tree();
tree.InputNode(5);
tree.InputNode(3); tree.InputNode(2); tree.InputNode(-3);
tree.FindNode(1);
tree.PrintTree(tree.Root); } } } |
힙
보통 이진 트리
노드의 각 자식의 값은 노드 자신의 값 이하여야 한다.
루트 노드의 값은 그 트리에서 가장 큰 값
따라서 최대값을 상수 시간으로 구할 수 있다.
빠르게 최대값을 추출해야 한다면 힙을 사용한다.
너비우선탐색(Breadth-First Search)
루트에서 시작해 왼쪽에서 오른쪽으로 훑어서 검색한다
검색시 같은 층에 있는 모든 노드의 자식 노드를 저장해야 하기 때문에 메모리를 많이 사용해 사용하지 않는다.
깊이우선탐색(Depth-First Search)
원하는 노드를 찾을 때 까지, 또는 끝에 다 다를때까지 한 가지를 따라 쭉 내려가는 방식이다. 더 이상 검색을 진행할 수 없으면 아직 확인해 보지 않은 자식이 있는 가장 가까운 조상노드로 돌아가서 검색을 계속 진행한다.
너비우선탐색보다는 메모리 사용량이 훨씬 적고 특정 층을 마지막으로 검색하는 문제가 없다(너비우선탐색은 마지막층을 맨 마지막에 검사한다)