목록자료구조 (22)

오늘도 더 나은 코드를 작성하였습니까?

Red-Black Tree (레드 블랙 트리)

정의 이진탐색 트리의 한 종류로서 균형 잡힌 트리이다. 이진탐색 트리의 조건을 기본적으로 만족하면서, 아래의 5가지 조건을 만족해야 된다. * 자식이 없는 상태(Null, None, Nill)을 나타내는 노드가 존재한다. 1. 모든 노드는 Red/Black 두 가지중 하나의 색상값을 가진다. 2. Root노드는 반드시 Black 색상이다. 3. 없는 상태(Null, None, Nill)을 나타내는 노드는 Black 색상을 갖는다. 4. Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다.(Black 노드는 Black/Red 어떤색이든 자식으로 가질 수 있다.) 5. 임의 노드에서 모든 Leaf 노드까지의 경로에서 시작 노드를 제외한, Black node의 개수(Black Height)는 동일하..
자료구조 2023. 10. 26. 18:53
균형을 유지하는 AVL-Tree

정의 AVL Tree(Adelson-Velsky and Landis 만든 사람 이름) * 이진탐색 트리의 일종이기 때문에 이진탐색 트리의 특성을 모두 만족한다. - 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. - AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이만 난다. - 삽입, 삭제 시점에 특정 노드를 기준으로 양쪽의 두 서브 트리의 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다 이진트리에서 데이터가 아래와 같이 한쪽으로 편향되어서 저장이 된다면, O(n) 시간복잡도가 걸린다. 이것을 해결하기 위..
자료구조 2023. 10. 25. 18:05
이진탐색트리 BST(Binary Search Tree) Feat. kotlin

참조한 자료 유튜브 - https://www.youtube.com/watch?v=i57ZGhOVPcI 정의 *이진 트리(binary tree)- 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조 이진 탐색 트리(BST: binary search tree) 이진 트리중 아래와 같은 특징을 지니는 트리 - 모든 노드는 값(value)을 가진다. - 값은 대소관계가 존재한다. 즉 비교 가능하다. - 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. - 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. - 좌우. 서브 트리는 각각이 다시 이진 탐색 트리 이다. search / insert / delete *search 는 In..
자료구조 2023. 10. 24. 20:32
B Tree 데이터 삭제

* 나무위키의 내용 및 *아래 링크의 유튜브 영상을 보고 본 글은 제 학습의 결과를 정리한 내용입니다. https://www.youtube.com/watch?v=H_u28u0usjA 데이터 삭제 1. 모든 데이터는 leaf-node에서 삭제를 진행한다. - internal node를 삭제해야 된다면, lower_bound (삭제 해야되는 노드 보다 작은 값 중 가장 큰것) upper_bound (삭제 해야되는 노드 보다 큰 값 중 가장 작은 것) * 항상 lower_bound / upper_bound는 B tree 특성상 항상 leaf 노드에 존재한다. 둘 중에 1개를 골라 internal node와 위치를 바꾼뒤 삭제를 진행한다면, B tree의 key 정렬 조건을 위배하지 않는다. 15를 삭제 하려고..
자료구조 2023. 10. 11. 19:27
이전 Prev 1 2 3 4 5 6 Next 다음