분류 전체보기
-
2. AVL 트리의 LL회전, RR회전C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 00:42
시작 하기에 앞서, AVL 트리의 구현에 이진 탐색 트리의 모든 헤더 파일과 소스 파일이 필요 지금부터 만드는 모든 함수들은 AVLTree헤더 파일과 AVLTree 소스 파일에 정의함. 1. LL회전 아래 [그림 1]의 LL타입의 경우 6,5,2순으로 노드를 삽입했을 경우에 만들어 진다. 노드6은 균형인수가 2로서 불균형하다. 그러나 오른쪽으로 회전을 시키면 다시 균형 트리를 만들 수 있다. [그림 1 : LL 타입 ] [그림 2 : LL 회전 결과 ] LL회전을 보다 일반적인 경우로 정리해보자. LL타입은 조상 노드A의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로 해서 발생한다. 아래의 그림을 보자. LL회전은 노드들을 오른쪽으로 회전시키면 된다. 회전을 시키면 아래와 같다. 2. RR회전 ..
-
1. AVL 트리의 개념C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 18. 19:46
1. 이진 탐색 트리의 단점 이진 탐색 트리에서의 삽입, 삭제 연산을 앞에서 다루었지만, 이들 연산들은 이진 탐색 트리를 유지시키기는 하지만, 균형 트리를 보장하지는 않는다. 만약 이진 탐색 트리가 균형 트리가 아닐 경우에는 탐색의 시간이 높아지게 된다. 예를 들어, {5,2,8,1,7,3,9}와 같은 순서로 정수를 공백 이진 탐색 트리에 삽입하면 아래 [그림 1]과 같은 이진 탐색 트리가 만들어 진다. 그러나, 만약 {1,2,3,5,7,8,9}의 순으로 입력 된다면 [그림 2 ]와 같은 트리가 만들어 질 것이다. [그림 1 ] [그림 2 ] 위의 [ 그림 1]의 이진 탐색 트리에서 최대 비교 횟수는 3회인 반면, [그림 2 ]의 트리에서는 7회가 된다. 이진 탐색 트리가 [그림 2 ]와 같이 경사 트리..
-
2. Binary Search Tree 만들기 - 삭제C 자료구조/6. Binary Search Tree Basic 2020. 6. 17. 00:57
아래 글을 이어서 진행해보자. designatedroom87.tistory.com/14?category=869957 1. Binary Search Tree 만들기 - 삽입과 탐색 시작 하기 전에, Tree에서 구현한 BinaryTree 헤더 파일과 소스파일이 필요하다. 그리고 BinarySearchTree에서의 삽입과 탐색 그리고 삭제 함수들은 모두 BinarySearchTree 헤더 파일과 소스 파일에 구현하도 designatedroom87.tistory.com 이진 탐색 트리의 삭제 먼저 노드를 삭제하기 위해서는 먼저 노드를 탐색하여야 한다는 것은 삽입과 마찬가지이다. 우리가 삭제하려고 하는 키값이 트리 안에 어디 있는지를 알아야 삭제할 수 있다. 노드를 탐색하였으면, 아래의 3가지 경우를 고려하여야..
-
1. Binary Search Tree 만들기 - 삽입과 탐색C 자료구조/6. Binary Search Tree Basic 2020. 6. 16. 11:47
시작 하기 전에, Tree에서 구현한 BinaryTree 헤더 파일과 소스파일이 필요하다. 그리고 BinarySearchTree에서의 삽입과 탐색 그리고 삭제 함수들은 모두 BinarySearchTree 헤더 파일과 소스 파일에 구현하도록 함. 1. 이진 탐색 트리의 정의 이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진 트리를 말한다. 이진 탐색 트리의 정의는 아래와 같다. (1). 모든 노드의 키는 유일하다. (2). 왼쪽 서브 트리의 키들은 루트의 키보다 작다. (3). 오른쪽 서브 트리의 키들은 루트의 키보다 크다. (4). 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 위의 정의와 같이, 찾고자 하는 키값이 이진 트리의 루트 노드의 키값과 비교하여 작으면 우리가 찾고자 하는 키값은 왼쪽..
-
4 - (2). 수식 트리 만들기( 수식 트리의 순회 )C 자료구조/5. 트리( Tree ) 2020. 6. 15. 11:05
아래의 내용에 이어서 진행하도록 하자. designatedroom87.tistory.com/12?category=869064 4 - (1). 수식 트리 만들기 ( 수식 트리 구성 & 수식 트리 계산 ) 이진 트리 순회는 수식 트리를 처리하는데 사용될 수 있다. 수식 트리는 산술식이나, 논리식의 연산자와 피연산자들로부터 만들어진다. 피연산자들은 단말 노드가 되며, 연산자는 비단말 노드 designatedroom87.tistory.com 수식 트리의 순회는 앞에서 이진 트리의 순회와 그 형태가 같다. designatedroom87.tistory.com/10?category=869064 2. 이진 트리의 순회 순회 알고리즘은 다음과 같다. 전위 순회는 루트를 먼저 방문하고, 그 다음에 왼쪽 서브 트리를 방문하..
-
4 - (1). 수식 트리 만들기 ( 수식 트리 구성 & 수식 트리 계산 )C 자료구조/5. 트리( Tree ) 2020. 6. 15. 00:24
이진 트리 순회는 수식 트리를 처리하는데 사용될 수 있다. 수식 트리는 산술식이나, 논리식의 연산자와 피연산자들로부터 만들어진다. 피연산자들은 단말 노드가 되며, 연산자는 비단말 노드가 된다. 각 이진 연산자에 대하여 왼쪽 서브 트리는 왼쪽 피연산자가 되며, 오른쪽 서브 트리는 오른쪽 피연산자를 나타낸다. [ 그림1 ] [ 그림2 ] [ 그림3 ] 구성에 앞서, 수식 트리 구성하는 함수와 수식 트리 계산하는 함수는 ExpressionTree 헤더 파일과 ExpressionTree 소스 파일에 정의. 1. 수식 트리 구성하기 수식 트리를 구성하기에 앞서 수식은 후위 표기법의 수식이며, 만약 중위 표기법의 식이면 이를 후위 표기법으로 변경이 필요하다. 아래의 글을 읽어보자. designatedroom87.t..
-
3. 이진 트리의 연산 ( 노드의 개수, 단말 노드의 개수, 트리의 높이 구하기 )C 자료구조/5. 트리( Tree ) 2020. 6. 13. 01:21
1. 이진 트리의 노드의 갯수 구하기 이진 트리 안의 노드의 갯수를 세어서 표시한다. 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다. 각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 된다. 이진 트리에서 노드의 갯수 구하는 알고리즘 의사코드 2. 단말 노드 갯수 구하기 단말 노드의 갯수를 세기 위해서는 트리안의 노드들을 전체적으로 순회하여야 한다. 순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 NULL이 되면, 단말 노드이므로 1을 반환한다. 만약 그렇지 않다면 비단말 노드이므로 각 각의 서브 트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다. 이진 트리에서 단말 노드의 갯수 구하는 알고리즘 의사코드 3. 트리의 높이 구하..
-
2. 이진 트리의 순회C 자료구조/5. 트리( Tree ) 2020. 6. 11. 15:43
순회 알고리즘은 다음과 같다. 전위 순회는 루트를 먼저 방문하고, 그 다음에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 마지막으로 방문하는 것이다. 중위 순회는 먼저 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문한다. 후위 순회는 왼쪽 서브 트리, 오른쪽 서브 트리, 루트 순으로 방문한다. 그림으로 보자. ㉠. 전위 순회 : VLR ㉡. 중위 순회 : LVR ㉢. 전위 순회 : LRV 이진 트리에서 각 각의 서브 트리도 이진 트리이다. 따라서, 서브 트리에서도 전체 이진 트리와 똑같은 방법을 적용할 수 있다. 즉, 전위 순회라면 서브 트리에 들어 있는 노드들도 VLR의 순서대로 순회된다. 트리 순회 알고리즘은 앞에서 한 순환 기법을 이용한다. 아래의 그림의 이진 트리에서 보면 전체 트리나 서..