이진 탐색 트리의 한 종류로 스스로 균형을 잡는 트리이다. 이때 balance factor를 통해 균형을 유지하는게 핵심이다. 그럼 balance factor에 대해서 조금 더 자세히 알아보자. 노드의 balance factor란 임의의 노드 x에 대해서 그 노드의 왼쪽 서브트리의 높이와 그 노드의 오른쪽 서브트리의 높이의 차이를 구했을때, 그 높이 차이를 그 노드의 balance factor라고 한다. 여기서 AVL 트리의 특징은 트리의 모든 노드들의 balance factor가 -1, 0 ,1 값을 가진다는 특징이 있다. 또한 AVL 트리는 트리에 삽입 혹은 삭제후에 balance factor가 -1, 0, 1이 아닌 노드가 생기면 균형을 맞추는 작업을 수행한다. 즉, AVL 트리에서 삽입/삭제를 위..
이번 장에서는 균형 이진 탐색 트리로 많이 사용되는 RB tree를 C언어로 구현해본다. 여기서 구현하는 ADT(Abstract Data Type)은 ordered set, multiset이다. 구현해야 하는 기능들은 CSLR 13장의 수도 코드를 구현하면 되는데, 구현해야 할 기능들은 다음과 같다. new_tree() : RB tree 구조체를 생성한다. 이때, 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야한다. Tree를 생성할 때는 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야 한다. 이를 tree 구조체의 동적 할당이라고 한다. 또한 RB tree의 leaf 노드는 nil 노드라는 것으로 표시해야 하는데, nil 노드는 일종의..
이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성이 있다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다. 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다. 그리고 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. 또한 중복된 키를 허용하지 않는다. 이러한 이진 탐색 트리의 특성때문에 효율적인 검색이 가능하다. 검색 이진 탐색 트리에서 검색은 특정 요소의 위치를 찾는 것이다. 과정은 먼저 루트에서 시작하여, 검색 값을 루트와 비교하여 루트보다 작으면 왼쪽에 대해 재귀하고 크면 오른쪽으로 재귀한다. 일치하는 값을 찾을때까지 절차를 반복한다. 검색 값이 없으면 null을 반환한다. 이를 구현하면 다음과 같다. struct node* sear..
Red-Black Tree는 이진 탐색 트리의 한 종류로서, 스스로 균형을 잡는 트리를 의미한다. 즉, 이진 탐색 트리의 worst case의 단점을 개선하였으며, 모든 노드는 red 혹은 black이라는 특징을 가지고 있다. 또한 RB tree는 nil 노드라는 독특한 특징을 가지고있다. 이는 존재하지 않음을 의미하는 노드로, 자녀가 없을 때 자녀를 nil 노드로 표기한다. 그럼에도 불구하고 값이 있는 노드와 동등하게 취급을 해주기 때문에, RB tree에서 leaf 노드는 nil 노드인 것이다. RB Tree의 특성에는 다음과 같은 규칙이 있다. 모든 노드는 RED or BLACK이다. 루트 노드는 BLACK이다. 모든 NIL 노드는 BLACK이다. 노드가 RED이면, 그 노드의 자녀는 BLACK이다..
Trie는 문자열을 저장하고, 효유적으로 탐색하기 위한 트리 형태의 자료구조이다. 여기서 trie라는 이름은 retrieval tree에서 나온 단어이다. 즉, Trie는 radix tree, prefix tree, retrieval tree라고도 한다. Trie의 핵심 개념은 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라는 것이다. 예를들어, Datastructure라는 단어를 검색하기 위해서 제일 먼저 D를 찾고, 그 다음에 a, t .. 순서로 찾는 이러한 개념을 적용한 것이 Trie이다. 그렇다면 트라이의 장점은 무엇일까? 트라이의 장점은 문자열 검색을 빠르게 한다는 것이다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 ..
해시 테이블이란 검색하고자 하는 키 값을 입력받아서 해쉬 함수를 돌려서 반환받은 HashCode를 배열의 index로 환산해서 데이터에 접근하는 방식의 자료 구조이다. F(key) -> HashCode -> Index -> Value 이때, 해시 함수는 어떠한 특정한 데이터를 이용해서 입력받은 키 값으로 그 값이 얼마나 큰지에 상관없이 동일한 해시 코드를 만들어준다. 그리고 해시 테이블의 가장 큰 장점은 검색 속도가 매우 빠르다는 점이다. O(1). 왜냐하면, 해시 코드의 값 자체가 배열의 인덱스로 활용되기 때문에 해시 코드로 배열의 위치에 다이렉트로 접근할 수 있기 때문이다. 그러나 해시 테이블도 고민이 있다. 바로 hash algorithm이 좋지 않을 경우, 한 배열의 인덱스에 여러 개의 값이 할당..
배열이란 메모리 상에 데이터를 연속적으로 배치한 자료구조이다. 문자열이란 문자, 단어 등으로 구성된 문자들의 집합을 말한다. 파이썬에서 예를 들면, 다음과 같다. 이때, 주의할 점은 숫자를 따옴표로 감싸면 이 또한 문자열이 된다는 것이다. "Life is too short, You need Python" "a" "123" 인용 https://wikidocs.net/13 02-2 문자열 자료형 문자열(string)이란 문자, 단어 등으로 구성된 문자들의 집합을 말한다. 예를 들면 다음과 같다. ```plaintext Life is too short, You need… wikidocs.net https://chunggaeguri.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%A..
이진 트리(Binary Tree) 자식 노드가 최대 2개인 노드들로 구성된 트리로, 각 자식 노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 나눌 수 있다. 또한 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉘어질 수 있다. Full Binary Tree : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. Complete Binary Tree (완전 이진 트리) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 왼쪽부터 노드가 순서대로 채워진 이진트리이다. Perfect Binary Tree (포화 이진 트리) : Full Binary Tree 이면서, Complete Binary Tree 인 경우이다. 모든 leaf node의 레벨이 동일하고, 모든 레벨이 가득 채워져..
순환성이 없는 무방향 그래프이다. 특징 특정하지 않는한 어떤 노드든지 root가 될 수 있다. 가장 바깥쪽 노드는 leaf node이다. node A에서 node B로 가는 경로는 반드시 존재하며 유일하다. (단 1개) 노드개수 = 간선개수 + 1 자료구조에서의 트리 부모 -> 자식 관계가 있는 방향 그래프이며, root는 하나다.
구성요소 Vertext(node) edge 그래프 종류 방향성 무방향 그래프(양방향 그래프) 방향 그래프 순환성 순환 그래프(Cyclic Graph) 비순환 그래프(Acyclic Graph) 방향성 비순환 그래프(DAG. Directed Acyclic Graph) VCS (Version Control System) 버전 관리 시스템으로 대표적으로 git과 github가 있다. 또한 이는 대표적인 방향성 비순환 그래프이다. 연결 요소(Connected Component) 아래 그림은 연결요소가 3개인 그래프이다. 코드로 그래프를 나타내는 방법 인접행렬 인접리스트 인접행렬 vs 인접리스트 둘 중에 뭘 써야할까? 여기에서 시간과 공간 사이의 trade off를 알 수 있다. 메모리 공간 인접행렬 노드가 n개이..
