목록자료구조 (22)

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

Map Hash(Hash Table, Hash Function)

정의 map키(key) 역할을 하는 데이터와 값(value) 역할을 하는 데이터를 짝 지어(=연결 지어) 저장하는 데이터 구조를 말한다. 키는 저장된 데이터의 구별에, 값은 그 키와 연결되어 저장된 데이터를 뜻한다. 키는 데이터 구별에 사용되기 때문에 중복되지 않는다. map 인터페이스를 구현한 Concrete Class들에는 Hashmap HashTable등이 있다. 두 구현 클래스의 차이도 있겠지만 아래표로 간단하게 보고, 일단 Hash에 대해서 알아보자! Hash를 사용하는 대표적인 자료구조는 map(c++, java), dictionary(python)등이 있다. 이외에도 hash를 사용하는 곳은 많지만, 일단은 대표적인 자료구조인, map을 중심적으로 hash를 알아보자. Hash란 무엇인가? ..
자료구조 2023. 11. 7. 17:03
균형 이진 트리 비교(AVL Tree vs Red-Black Tree)

자료구조 2023. 11. 2. 00:07
Red-Black Tree (레드 블랙 트리) 데이터 삭제.

학습에 참고한 영상입니다. *https://www.youtube.com/watch?v=6drLl777k-E 데이터 삭제 이진탐색 트리의 한 종류이기 때문에 기본적인 이진 탐색트리 삭제 방법을 따른다. 데이터 삭제 후, 레드 블랙 트리의 속성 5가지를 만족하는지 확인한다. 이를 불만족 한 노드가 발생한다면, 재조정을 한다 속성 1. 모든 노드는 Red/Black 두 가지중 하나의 색상값을 가진다. 2. Root노드는 반드시 Black 색상이다. 3. 없는 상태(Null, None, Nill)을 나타내는 노드는 Black 색상을 갖는다. 4. Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다.(Black 노드는 Black/Red 어떤색이든 자식으로 가질 수 있다.) 5. 임의 노드에서 모든 Le..
자료구조 2023. 11. 2. 00:05
Red-Black Tree (레드 블랙 트리) 데이터 삽입

데이터 삽입 이진탐색 트리의 한 종류이기 때문에 기본적인 이진 탐색트리 삽입 방법을 따른다. 데이터 삽입 후, 레드 블랙 트리의 속성 5가지를 만족하는지 확인한다. 이를 불만족 한 노드가 발생한다면, 재조정을 한다 속성 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. 29. 06:20
이전 Prev 1 2 3 4 5 6 Next 다음