DataStructure(54)
-
비선형 데이터구조, RedBlackTree #1 RedBlackTree의 규칙 및 수행과정
1. RedBlackTree의 규칙 모든 노드는 Red 또는 Black Root 노드는 언제나 Black 새로 추가되는 노드는 항상 Red Root 노드에서 Leaf 노드까지 가는 모든 경로에는 같은 수의 Black 노드가 있어야한다 어떤 경로에서도 Red 노드 2개가 연속으로 있어서는 안된다 모든 Null 노드는 Black이라고 가정한다 2. RedBlackTree 수행과정 2.1 Rebalance RedBlackTree에 노드를 추가할 때, RedBlackTree의 규칙에 위반되면 트리의 균형을 맞추기 위해 Rebalance 연산을 수행합니다. RedBlackTree의 Rebalance 연산에는 Black Aunt Rotate, Red Aunt Colorflip 연산이 존재합니다. Black Aunt..
2021.12.29 -
비선형 데이터구조, AVL Tree #2 AVL 트리 checkBalance & rebalance 메서드
이전글 https://yonghwankim-dev.tistory.com/199 비선형 데이터구조, AVL Tree #1 AVL 트리 소개 및 add 메서드 개요 이번글에서는 AVL 트리에 대해서 소개하겠습니다. AVL 트리가 무엇이고 회전(Rotate) 기능을 통하여 어떻게 트리의 균형(Balance)을 맞추는지 소개합니다. 1. AVL 트리란 무엇인가? AVL 트리는 이진 yonghwankim-dev.tistory.com 개요 이전글에서는 AVL 트리의 add 메서드를 구현하였습니다. 이번글에서는 트리가 균형을 맞추고 있는지 검사하는 checkBalance 메서드와 트리를 균형있게 맞추는 기능인 rebalance 메서드를 구현하겠습니다. 1. checkBalance 메서드 checkBalance 메서드..
2021.12.28 -
비선형 데이터구조, AVL Tree #1 AVL 트리 소개 및 add 메서드
개요 이번글에서는 AVL 트리에 대해서 소개하겠습니다. AVL 트리가 무엇이고 회전(Rotate) 기능을 통하여 어떻게 트리의 균형(Balance)을 맞추는지 소개합니다. 1. AVL 트리란 무엇인가? AVL 트리는 이진 탐색 트리를 기반으로 한 트리로써 이진 탐색 트리임에도 불구하고 균형(Balance)이 깨진 트리를 균형있게 맞추어 주는 트리입니다. 대표적인 특징은 왼쪽과 오른쪽의 높이의 차가 항상 1보다 같거나 작아야합니다. 아래의 그림은 균형이 깨진 이진 탐색 트리를 회전을 통하여 균형을 맞추는 그림입니다. 위의 이진 탐색 트리에서 12를 삽입후 8 노드는 왼쪽의 높이가 0이고 오른쪽의 높이가 2이기 때문에 왼쪽과 오른쪽의 높이차가 2가 되버립니다. 위와 같이 높이차가 2 이상인 서브 트리는 불균..
2021.12.27 -
비선형 데이터구조, 트리(Tree) #10 이진탐색트리의 회전(Rotate)
개요 이번글에서는 이진 탐색 트리의 회전에 대해서 소개하겠습니다. 1. 회전(Rotate) 소개 이진 탐색 트리의 대표적인 특징은 특정 노드를 기준으로 노드보다 작은 값은 왼쪽 자식에 위치하고 큰 값은 오른쪽 자식에 위치합니다. 따라서 이진 탐색 트리는 아래와 같이 저장될 수 있습니다. 위 그림의 이진 탐색 트리는 매우 안정적인 이진 탐색 트리입니다. 하지만 아래와 같은 트리도 이진 탐색 트리가 될 수 있습니다. 위와 같은 트리도 이진 탐색 트리가 되지만 탐색시 시간복잡도는 O(n)가 소요됩니다. 위와 같은 이진 탐색 트리는 균형이 잡혀 있지 않다고 합니다. 따라서 회전 기능은 균형 잡혀있지 않은 트리를 균형 있는 트리로 변환할 수 있도록 도와주는 기능입니다. 회전 기능에는 대표적으로 왼쪽 회전(Left..
2021.12.24 -
비선형 데이터구조, 트리(Tree) #4 이진 트리의 순회 및 표현식
이전글 https://yonghwankim-dev.tistory.com/116?category=974118 비선형 데이터구조, 트리(Tree) #3 이진 트리의 종류 1. 이진 트리(Binary Tree)의 종류 정 이진 트리(full binary tree) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다. 포화 이진 트리(perfect binary tree) 모든 내부 노드가 두 개의 자식 노드를 가지.. yonghwankim-dev.tistory.com 개요 이전글에서는 이진트리의 종류에 대해서 알아보았습니다. 이번글에서는 이진 트리를 순회하는 방법 3가지와 이진 트리의 순회를 활용하여 예시로 복잡한 수식을 트리 형태로 표현해보겠습니다. 1. 이진 트리의 순회(Traversal) 이진 트리..
2021.12.20 -
비선형 데이터구조, 힙(Heap) #2 이진 힙 정렬(Binary Heap Sort)
이전글 https://yonghwankim-dev.tistory.com/123 비선형 데이터구조, 힙(Heap) #1 이진 힙(Binary Heap) 1. 이진 힙(Binary Heap) 데이터구조란 무엇인가? 이진 힙은 아래와 같은 특성을 가지고 있는 이진 트리입니다. 이진 힙의 데이터 구조는 완전 이진 트리 기반 완전 이진 트리란 마지막 레벨을 제외 yonghwankim-dev.tistory.com 개요 이전글에서는 이진 힙의 구조를 알아보았습니다. 이번글에서는 이진 힙을 정렬하는 함수를 구현하겠습니다. 1. Binary Heap은 무엇인가? Binary Heap은 완전 이진 트리입니다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있고 마지막 레벨의 노드들은 전부 왼쪽에 위치해..
2021.12.16