6-8주차 트리(tree, bst, avl tree)

수강일시 : 2020.09~ 2020.12

출처:  고려대학교 정연돈 교수님 자료구조 강의

 

6주차 tree

7주차 binary search tree

8주차 avl tree

 

트리는 말그대로 나무 형태의 자료구조이다.

tree는 node와 노드를 잇는 branches로 구성되어있다.

각 노드들은 부모/자식으로 표현하고 같은세대는 level로 표현한다.

예를들어 root node는 level 0, BEF노드들은 level1 CDGHI노드들은 level2 라고 한다.

각 노드들은 그 자체로도 서브트리를 구성한다.

 

트리중에서 각 노드의 자식이 2개 이하인 트리를 binary tree(이진트리)라고 한다.

이진트리의 특성은 다음과 같다.

 

이진트리중에서 모든 노드의 자식이 2개로 이루어진 경우 FULL binary tree라고 한다.

모든 노드의 자식이 2개이거나 마지막 노드만 1개로 이루어진경우(FULL binary tree 또는 마지막노드 한개가 적은 경우) complete binary tree라고 한다.

binary tree의 ADT는 다음과 같다

이진트리의 경우 NODE의 자식이 비어있는경우(자식이 없는 경우)NULL로 초기화하고 값을 대입하지 않는다.

 

트리의 탐색은 대표적으로 두가지로 나뉘는데

첫번째는 DFS(깊이우선 탐색)

두번째는 BFS(너비우선 탐색)이다.

깊이우선탐색은 최대한 깊이 탐색한다음 한단계씩 부모로 나오고 다시 최대한 깊이탐색하고 다시올라오는 방식을 취한다.

 

깊이 우선탐색의 방식으로는

preorder traversal

inorder traversal

postorder traversal

세가지 방식이 존재한다.

preorder는 루트먼저 다음 왼쪽 오른쪽 마지막으로 간다.

코드로 본다면

 

traverse(NODE* root)

{

printdata(root->data);

traverse(root->left);

traverse(root->right);

}

가 된다.

 

inorder는 왼쪽먼저 다음 루트, 오른쪽 마지막으로 간다.

코드로 본다면

 

traverse(NODE* root)

{

traverse(root->left);

printdata(root->data);

traverse(root->right);

}

가 된다.

 

postorder는 왼쪽먼저 다음 오른쪽, 루트가 마지막으로 간다.

코드로 본다면

 

traverse(NODE* root)

{

traverse(root->left);

traverse(root->right);

printdata(root->data);

}

가 된다.

 

너비우선탐색은 level이 낮은 노드를 먼저 탐색하는 방식이다.

따라서 이를 level order traversal이라고 표현하기도 한다.

 

탐색에 있어서 tree를 이용하면 훨씬 빠르게 진행할 수 있는데 이를위해 고안된 방법중 하나가 BST(이진탐색트리)이다.

이진탐색을 이용하면 O(n)=log(n)만에 탐색을 할 수 있다.

 

이진탐색 트리는 노드를 기준으로 노드보다 낮은값은 왼쪽 높은값은 오른쪽에 몰아두게 된다.

 

이진탐색트리에서 탐색을 진행한다면 탐색값과 노드를 비교하면서 탐색값이 작으면 왼쪽으로 이동, 크면 오른쪽으로 이동하며 NULL 또는 탐색값이 나올때 까지 반복하면 log(n)의 시간동안 찾을 수 있게된다.

 

 

하지만

BST를 구성하는데 만약 각각의 root가 들어갈 수 있는 값 중 가장 큰값

또는 가장작은값이면 binary search의 효과가 없어진다.

오른쪽 예시는 binary search tree가 의미없어지는 대표적인 경우이다.

이런 현상을 방지하기 위해서 밸런스를 맞추는데 이를

balanced search tree 라고 한다.

balanced search tree는 모든 subtree의 왼쪽과 오른쪽의 높이가 1이하로 차이나야 한다.

 

이런 성질을 만족하는 이진탐색트리를 AVL tree라고 한다.

AVL tree는 기존 이진탐색트리에서 balanced tree의 성질을 갖게해주는 rotating 작업이 추가로 필요하다.

 

삽입에서의 rotation은 다음과 같다.

LL rotation

LL rotation은 다음과 같다. 왼쪽의 level이 2인데 반해 오른쪽 level은 0이므로 avl tree의 균형이 무너졌다. 이럴 때는 오른쪽으로 rotation을 한 번을 해줍니다.

 

RL

왼쪽의 level은 2 오른쪽은 0인데 LL과는 방향이 다르다. 왼쪽 서브트리의 모습이 다르다 이번에는 두번째 노드를 left rotation을 하고, 전체 노드를 right rotate를 진행한다.

 

삭제의 경우도 rebalancing이 필요하다.

삭제의 경우 root노드를 제거하면 root와 가장 가까운값이 왼쪽노드의 가장 오른쪽값 또는 오른쪽노드의 가장 왼쪽값이 된다.(작은것중에 가장 큰것 또는 큰것중에 가장 작은것)

따라서 이를 고려하여 바꾸고 balancing을 진행한다.