이진 트리 이론

이진 트리와 이진 검색 트리

no	설명	확인
1	트리는 데이터를 계층적으로 저장하는 비연속 형식의 자료구조다.
2	트리는 파일시스템에 파일을 저장하거나 정렬된 데이터 리스트 등 계층적인 데이터를 저장할 때 사용된다.
3	트리의 정의: 트리는 에지(Edge)로 연결된 노드(Node)의 집합이다.
4	트리의 최상위 노드를 루트(Root) 노드라 한다.
5	한 노드가 아래 노드와 연결되어 있을 때 위에 있는 노드를 부모(Parent) 노드라고 하며, 부모 노드의 아래 있는 모든 노드를 자식(Child) 노드라고 한다.
6	한 노드는 0개 이상의 노드와 연결 될 수 있다. 자식 노드가 없는 노드를 리프(Leaf) 노드라 부른다.
7	이진 트리는 모든 노드의 자식 노드 수가 2개 이하인 특수한 노드를 가리킨다.
8	이진 노드는 몇가지 동작을 매우 효율적으로 수행할 수 있다는 특징이 있다.
9	한 노드에서 다른 노드로 도달하는데 사용한 에지의 모음을 경로(Path)라 한다.
10	트리의 모든 노드를 일정한 순서로 방문하는 것을 트리 탐색(Tree traversal)이라 한다.
11	트리에 있는 레벨의 수를 트리의 깊이(Depth)라고 한다.
12	자식 수를 두 개 이하로 제한한 덕분에 트리의 데이터 삽입, 데이터 검색, 데이터 삭제를 매우 효율적으로 수행 할 수 있다.
13	이진 검색 트리 구현하기 : //Node 클래스의 정의 function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; }
14	이진 검색 트리 클래스는 BST의 루트 노드를 의미하는 한 개의 데이터 멤버와 Node 객체를 포함한다.
15	이진 검색 트리 클래스의 생성자에서는 루트 노드를 null로 설정하면서 빈 노드를 만든다.
16	insert() 함수를 구현하려면 먼저 데이터를 저장할 Node 객체를 만들어야 한다.
17	다음으로 BST의 루트 노드를 확인해야 한다. 루트 노드가 없으면 BST는 BST를 새로 만드는 상황이므로 현재 삽입하려는 노드가 루트 노드가 되며 insert() 함수의 동작이 끝난다. 루트가 있다면 다음 단계로 넘어간다.
18	삽입하려는 노드가 루트 노드가 아니면 BST를 탐색하면서 노드를 삽입할 위치를 찾아야 한다. insert() 함수는 BST 의 레벨을 바꿔가며 삽입 위치를 찾을 때 현재 노드에 할당된 Node 객체를 사용한다. insert() 함수는 BST의 루트 노드로 자신을 이동시킨 다음 작업을 시작한다.
19	이제 BST 내부에서 어느 위치에 노드를 삽입할 지 결정해야 한다. 삽입할 위치를 찾을 때까지 루프를 반복한다. 다음과 같은 방법으로 노드를 삽입할 위치를 결정한다.   1.루트 노드를 current 노드로 설정한다.   2.삽입할 노드의 값이 current 노드의 값보다 작으면 새로운 current 노드를 current 노드의 왼쪽 자식으로 설정한다. 삽입하려는 노드의 값이 current 노드의 값보다 크다면 4번 과정을 생략한다.   3.current 노드의 왼쪽 자식의 값이 null이면 새로운 노드를 왼쪽 자식으로 삽입한 다음 루프를 종료한다. current 노드의 왼쪽 자신의 값이 null이 아니면 다음 루프를 진행한다.   4.current 노드를 현재 노드의 오른쪽 자식으로 설정한다.   5.current 노드의 오른쪽 자식의 값이 null이면 새로운 노드를 현재 노드의 오른쪽 자식으로 설정하고 루프를 종료한다. current 노드의 오른쪽 자식의 값이 null이 아니면 다음 루프를 진행한다.
20	BST 클래스 코드 : function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() { this.root = null; this.insert = insert; this.inOrder = inOrder; } function insert(data){ var n = new Node(data, null, null); if ( this.root == null ){ this.root = n; } else { var current = this.root; //루트에서부터 시작 var parent; while (true) { parent = current; if (data < current.data) { current = current.left; if ( current == null ) { parent.left = n; beak; } } else { current = current.right; if (current == null) { parent.right = n; break; } } } } }
21	이진 검색 트리 탐색 : BST 클래스에서는 중위(inorder), 전위(preorder), 후위(postorder)라는 세 가지 탐색 방법을 사용한다.
22	중위 탐색 : 노드의 오름차순 키 값으로 BST 클래스의 모든 노드를 방문한다.
23	전위 탐색 : 먼저 루트 노드를 방문한 다음→ 루트의 왼쪽 자식을 중심으로 하는 서브트리를 같은 방식으로 방문하며 → 마지막으로 루트 노드의 오른쪽 자식을 중심으로 하는 서브트리를 방문한다.
24	후위 탐색 : 루트 노드의 왼쪽 자식을 중심으로 하는 서브트리를 먼저 방문한 다음→ 루트 노드의 오른쪽 자식을 중심으로 하는 서브트리를 방문하며, 마지막으로 루트 노드를 방문한다.
25	중위 탐색 함수 : function inOrder(node) { if ( !(node == null )) { inOrder(node.left); putstr(node.show() + “ “); inOrder(node.right); } }
26	전위 탐색 함수 : function preOrder(node) { if ( !(node == null)) { putstr(node.show() + “ “); preOrder(node.left); preOrder(node.right); } }
27	후위 탐색 함수 function postOrder(node) { if ( !(node == null)) { postOrder(node.left); postOrder(node.right); putstr(node.show() + “ “); } }
28	BST 검색 보통 BST에서는 다음과 같은 세 가지 검색을 수행한다.   1.특정값 검색   2.최솟값 검색   3.최댓값 검색
29	최솟값과 최댓값 검색 최솟값은 항상 왼쪽 자식에 저장하므로 더 이상 왼쪽 자식 노드가 없을 때까지 BST의 왼쪽 에지를 탐색하면 최솟값을 찾을 수 있다. function getMin() { var current = this.root; while ( !(current.left == null )){ current = current.left; } return current.data; } //getMin() 함수는 current.left = null 이 나올 때까지 각 노드의 left 링크를 따라가며 탐색. function getMax() { var current = this.root; while ( !(current.right == null )) { current = current.right; } return current.data; }
30	특정값 검색 BST에서 특정값을 검색하려면 현재(current) 노드와 검색 대상 노드의 값을 비교해야 한다. 검색 결과에 따라 왼쪽 자식 노드를 탐색할 지, 오른쪽 자식 노드를 탐색할 지를 결정할 수 있다. function find(data) { var current = this.root; while (current.data != data) { if (data < current.data) { current = current.left; } else { current = current.right; } if ( current == null ) { return null; } } return current; }
31	BST의 노드 삭제하기 BST에서 노드를 삭제하는 동작이 가장 복잡하며, 삭제하는 노드의 위치에 따라 노드 삭제 과정의 복잡도가 달라진다.
32	재귀를 이용하여 삭제.   1.현재 노드가 삭제할 데이터를 포함하고 있는지 확인.   2.현재 노드가 삭제할 데이터를 포함하면 노드를 삭제.   3.현재 노드가 삭제할 데이터를 포함하고 있지 않으면 현재 노드의 데이터와 삭제하려는 데이터의 크기를 비교한다.   4.삭제하려는 데이터가 현재 노드의 데이트보다 작으면 현재 노드의 왼쪽 자식 노드로 이동한 다음 다시 데이터를 비교한다. 삭제하려는 데이터가 현재 노드의 데이터보다 크면 현재 노드의 오른쪽 자식 노드로 이동한 다음 데이터를 비교한다.   5.노드를 삭제할 때 삭제하려는 노드가 리프 노드인지 확인해야 한다.   6.리프 노드를 삭제했으면 삭제된 노드를 가리키던 부모 노드의 링크를 null로 설정한다.   7.삭제하는 노드에 한 개의 자식이 있다면 삭제된 노드를 가리키던 링크를 삭제된 노드의 자식을 가리키도록 조정한다.   8.삭제하는 노드에 두 개의 자식이 있다면 삭제한 노드를 기준으로 왼쪽의 서브트리에서 가장 큰 값을 찾던지 아니면 오른쪽 서브트리에서 가장 작은 값을 찾아야 한다. 여기서는 오른쪽 서브트리의 가장 작은 값을 찾는 방법을 이용한다.   9.서브트리에서 가장 작은 값을 찾는 함수가 필요하다 이 함수를 이용해 가장 작은 값을 임시로 저장할 노드를 만들 것이다. 서브트리의 가장 작은 값을 우리가 교체하려는 노드로 복사한 다음 임시 노드를 삭제한다. function remove(data) { root = removeNode (this.root, data); } function removeNode(node, data) { if (node == null) { return null; } if (data == node.data) { //자식이 없는 노드 if (node.left == null && node.right == null ){ return null; } //왼쪽 자식이 없는 노드 if (node.left == null) { return node.right } //오른쪽 자식이 없는 노드 if(node.right == null) { return node.left; } //두 자식이 있는 노드 var tempNode = getSmallest(node.right); node.data = tempNode.data; node.right = removeNode(node.right, tempNode.data); return node; } else if (data < node.data) { node.left = removeNode(node.left, data); return node; } else { node.right = removeNode(node.right, data); return node; } }
33	발견 횟수 계산 데이터 집합에서 어떤 데이터가 얼마나 분포하는지 확인할 때 BST를 활용할 수 있다. 예를 들어 BST를 이용해 시험 점수의 분포도를 저장할 수 있다. BST에 저장된 점수를 이용해 어떤 점수가 BST에 저장되어 있는지 여부를 확인한 다음 BST에 점수가 저장되어 있지 않으면 BST에 추가하고, BST에 점수가 저장되어 있을 때는 발견 횟수를 증가시킨다.
34	BST의 점수 발견 횟수를 저장할 수 있게 Node 객체에 필드를 추가해야 하며, BST에서 점수를 발견했을 때 발견 횟수를 저장하는 필드가 증가되도록 노드를 갱신하는 함수도 필요하다. function Node(data, left, right) { this.data = data; this.count = 1; // 점수를 BST에 삽입하는 시점에는 count를 1로 설정. count 필드를 증가시킬 함수를 BST에 추가해야 한다. this.left = left; this.right = right; this.show = show; } //count 필드를 증가시키는 update() 함수의 정의. function update(data) { var grade = this.find(data); grade.count++; return grade; } //점수 집합을 생성하는 함수와 점수를 출력해주는 함수가 필요함. function prArray (arr) { putstr(arr[0].toString() + ‘ ‘); for (var i = 1 ; i < arr.length; ++i) { putstr (arr[i].toString() + ‘ ‘); if ( i % 10 == 0) { putstr(“\n”); } } } function genArray(length) { var arr = []; for (var i = 0; i < length; ++ i) { arr[i] = Math.floor(Math.random() * 101); } return arr; } load(“BST”); // BST 정의에 update()를 추가 var grades = genArray(100); prArray(grades); var gradedistro = new BST(); for (var i = 0; i < grades.length; ++i) { var g = grades[i]; var grade = gradedistro.find(g); if (grade == null) { gradedistro.insert(g); } else { gradedistro.update(g); } } var cont = “y”; while (cont == “y”) { putstr(“\n\nEnter a grade: “); var g = parseInt(readline()); var aGrade = gradedistro.find(g); if (aGrade == null) { print(“No occurrences of “ + g); } else { print(“Occurences of “ + g + “: “ +aGrade.count); } putstr(“Look at another grade (y/n)? “); cont = readline(); }