데이터 구조8 AVL 트리 모든 노드에서 왼쪽과 오른쪽의 서브트리의 높이 차이가 1 이하를 유지하는 BST 위 BST는 어떤 노드에서 보더라도 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1이하이다. 이러한 상태를 유지하기 위해 모든 노드는bf(=balance factor)를 관리한다. 모든 노드의 bf의 절대값을 1이하가 되도록 하는 것이다. 트리의 좌우 균형이 무너지는 순간은 삽입/삭제 이후이다. 삽입/삭제후 균형이 무너지는 경우는 총 4가지 상황이 있고, 이 4가지상황에서 각각 어떻게 균형을 맞출 수 있는지 이해하자. LL 케이스 균형이 무너진 첫 번째 유형이다. 왼쪽 높이는 2인데 오른쪽 높이는 0 이라서 20노드를 기준으로 balance factor(left height - right height) 가 2가 되었다. 이럴.. 2021. 5. 30. 이진탐색(이분탐색)알고리즘 BinarySearchTree와 이진탐색 모두 조회에 있어 O(logN)의 성능을 보인다. 그러나 삽입&삭제 연산의 성능이 다르다. BST vs 이진탐색 알고리즘 성능비교 이름 조회 삽입 삭제 BST O(logN) O(logN) O(logN) 이분탐색 O(logN) N N 이진탐색 알고리즘(선형 자료구조)의 한계 이진탐색 알고리즘의 전제조건은 "데이터가 정렬되어 있어야한다" 라는 것이다. 이진탐색을 하기 위해서는 인덱스 접근을 빠르게 해야하므로 배열리스트를 이용할 수 밖에 없다. 배열 리스트에서의 데이터 삽입은 데이터들을 뒤로 밀어야하므로O(N)이다. 따라서 이진탐색 알고리즘(선형자료구조)에서의 삽입&삭제는 모두O(N)이다. 2021. 5. 30. BST 일반적인 삽입 과정 다음과 같은 BST에 50이라는 데이터를 삽입하려 한다. 삽입과정은 매우 재귀적이다 성능 트리의 밸런스가 잘 맞을 경우 → O(logN) 트리의 편향이 심할 경우 → O(N) 삽입 과정 •삽입하려는 노드와 루트노드를 비교한다 •삽입하려는 노드가 더 크다 → 오른쪽 서브트리에 반복(=재귀) •삽입하려는 노드가 더 작다 → 왼쪽 서브트리에 반복 (=재귀) 이 과정에서 서브트리가 비어있다면, 그 위치에 삽입한다 → 50이 더 크다. 그러므로 오른쪽 서브트리에 이 과정을 반복한다 → 50이 더 크다. 마찬가지로 오른쪽 서브트리에 반복한다 → 50이 더 작다. 왼쪽 서브트리에 반복한다 → 그런데 왼쪽 서브트리가 비어있다 → 왼쪽 노드로 삽입한다 → 완료 2021. 5. 29. BST 성능 = 높이 아래 이진탐색트리(BST)를 보고, 조회성능에 대해 생각해보자. 결과적으로 말하자면, 밸런스가 맞춰져 있다면 O(logN) 의 성능을 보이고, 편향된 정도가 심할수록 O(N)의 성능을 보인다. 편향된 BST = 리스트 ?? 이상하게 보일지 모르겠으나, 12를 루트노드로 갖는 BST라고 볼 수 있다 58을 찾기 위해선, 11번의 연산이 필요하다. 44를 찾기 위해선, 8번의 연산이 필요하다. 현재 조회과정은 O(N)의 성능을 보이며 결과적으로, [리스트] 자료구조 조회와 전혀 다를바가 없다! BST가 편향될 수록, 조회성능이 점점 O(N)에 수렴하게 된다. 밸런스가 맞춰진 BST의 성능 똑같은 데이터로 조금 다른 BST를 만들어보면 어떻게 될까? 58을 찾기 위해선 4번의 연산이 필요하다 44를 찾기 위해.. 2021. 5. 29. Binary Search Tree 조회 과정 BST 조회 과정 다음의 BST에서 41데이터를 찾는 과정을 살펴보자 성능 트리의 높이가 n 이라면 노드의 개수는 (2^n)-1 트리의 밸런스가 잘 맞을 경우 → O(logN) 트리의 편향이 심할 경우 → O(N) BST 성능 = 높이 조회 과정 41를 찾는다고 가정해 보자 노드와 비교해 41이 더 크면, 오른쪽 서브트리로 이동시키고 노드와 비교해 41이 더 작으면, 왼쪽 서브트리로 이동시킨다(재귀적) 데이터를 조회하는 과정에서 4번의 연산이 소요됐다. 한번에 한칸씩 내려가면서 결국 끝까지 가면 어떤 데이터든 찾을 수 있게 된다. 따라서, Binary Search Tree(BST)에서는 트리의 높이가 최대한 작아야 한다. 왜냐하면 트리의 높이가 곧, 조회성능과 비례하기 때문이다. 2021. 5. 29. Full Binary Tree vs Complete Binary Tree 2021. 5. 29. 트리의 순회 inorder(node) if node.left ≠ null then inorder(node.left) print node.value if node.right ≠ null then inorder(node.right) 대표적으로 3가지 순회 방법이 있다 전위 순회(preorder) 전위 순회의 방법 1. 노드를 방문한다. 2. 왼쪽 서브 트리를 전위 순회한다. 3.오른쪽 서블 트리를 전위 순회한다. 전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다. public void preorder(Node node){ System.out.println(node.value); if(node.left != null){ preorder(node.left); } if(node.right != .. 2021. 5. 29. 이진 탐색 트리(Binary Search Tree) 정렬된 상태로 데이터를 보관하는 이진트리 (binary tree) 이진탐색트리(Binary Search Tree)는 이진트리에서 다음의 규칙이 추가된 트리를 말한다. 모든 node에서 left child node가 자신보다 작고, right child node가 자신보다 크다 2021. 5. 29. 이전 1 다음
