Week 5 of Data structures - Binary search trees
이제 막바지에 다다라서 5주차에 접어들었다.
이번에는 sort 알고리즘 중 Binary search trees에 관한 내용을 알아본다.
주로 사용되는 곳은 사전같은 것으로 주어진 글자를 통해 알파벳순으로 정렬되어 있어 찾을때 용이하다.
또한 한 학급에서 가장 비슷한 키를 찾을때에도 사용될 수 있다.
Local search의 정의를 보면 key를 통해 데이터로 접근하며 이 때 값들은 정렬이 되어있는 상태여야 한다.
예시를 보면 위와 같이 정렬된 배열에 RangeSearch를 시행하면 해당 범위에 상응하는 값들을 찾아 반환을 해주고 NearestNeighbors를 사용하면 인접값들을 반환해준다.
Insert와 delete를 통해 key값을 추가하거나 삭제할 수도 있다.
위와 같은 배열에서 Inseart(3)을 하게 되면 오름차순의 순서에 맞게 해당하는 자리에 배치하게 되고 delete(10)을 하면 값이 삭제됨과 동시에 한자리씩 당겨지게 된다.
간단한 예시로 위와 같은 명령이 있을 때 결과는,
3, 5, 10, 12 가 최종 배열이므로 그 중 7에 가까운 값들은 5, 10이 됨을 간단히 알 수있다.
도식화된 배열을 보면 위와 같다.
먼저 hash table의 API 연산여부를 확인해보면 위와 같음을 알 수 있다. hash 값에 따라 chaining이 될 가능성이 크기에 RangeSearch와 NearestNeighbors는 불가하다.
배열에서는 모두 가능한 상태이나 배열의 특성상 빈자리가 있으면 안되기 때문에 위와 같은 특성이 나타난다.
Sorted array에서는 정렬이 된 상태이므로 더 빨리 해당 범위에 해당하는 값을 찾기가 쉽고,
근접값들을 찾기에도 수월하다.
대신 값을 추가하거나,
지울 때에는 배열의 특성에 따른다.
Linked list의 경우 해당 범위를 찾는 것또한 배열과 크게 다르지 않으며,
근접값도 마찬가지이다.
대신 값을 추가하거나,
삭제할때 O(1)에 가능한 특징을 가진다.
위에서 각 데이터 구조마다 장단점들을 살펴보았는데 모든 조건을 충족하는 구조는 없었기에 이들을 모두 만족할 만한 구조를 찾아야 한다.
따라서 Binary search tree에 대해 살펴본다.
Binary search의 방법은 데이터의 중앙으로부터 시작하여 방향을 판단 후 다시 그 절반에 접근하기를 반복하며 원하는 위치에 도달할 때까지 진행할 수 있는 방법이다.
위는 15를 찾을 때의 예시이며 큰 차이가 없어보일 수 있으나 구조가 커질 수록 해당 알고리즘의 장점이 부각된다.
위의 배열을 트리모양으로 도식화한 모습이다.
트리의 구조를 보면 우선 루트(root)가 존재하며 왼쪽과 오른쪽에 각각 작고, 큰 값(key)들이 존재하게 된다.
따라서 해당 노드의 key가 있고 상단에는 부모노드가 있으며 아래에는 자녀노드가 있다.
그리고 search tree의 특성으로 중요한 것은 자기 자신보다 왼쪽에 존재하는 자식노드들보다는 키값이 크며 오른쪽의 자식노드들보다는 키값이 작다.
퀴즈가 나왔는데 어떤 것이 search tree 특성을 만족하냐인데 답은 B가 되겠다.
A는 루트의 자식노드들간의 순서가 바로 맞지 않음을 알 수 있고 C는 루트인 5보다 오른쪽에 위치한 자식노드들 중 4가 존재하기에 만족하지 않음을 찾았다.
그리하여 binary search tree를 활용하여 기본 동작들에 대해 이해해보고자 한다.
우선 find 함수는 key k, Root R에 대해 루트 R을 가진 트리내에 k값을 찾는 역할을 수행한다.
예시로 위와 같은 트리가 존재할 때 Find(6)를 수행하면,
루트인 7의 왼쪽으로 내려가서 다시금 4의 오른쪽으로 내려가서 최종적으로 6을 찾게 된다.
이를 pseudo code로 서술하면 위와 같을 것이며,
만약 없는 키값을 찾게된다면 마지막에 도달한 값을 반환한다고 한다.
위의 내용을 포함한 수정된 find 함수이다.
이웃요소에 대한 내용을 확인할 때에는,
Next라는 함수를 사용하게 되며 N의 노드가 있을 때 이 다음으로 가장 큰키를 반환한다고 한다.
첫번째 예시를 보면 오른쪽에만 자식노드를 가지고 있다면 가장 하위의 값을 반환하게 될 것이고,
만약 오른쪽 자식노드들이 없다면 자기자신이 반환될 것이라고 한다.
Next에 대한 pseudo code이다.
Left Descendant의 pseudo code이다.
Right Ancestor의 pseudo code이다.
위 내용에 대한 퀴즈가 나왔는데 질문이 현재 Next 함수의 세세한 버그를 찾으라고 나오는데 2번 보기에 있듯 N 자신이 가장 큰 값일 때 에러가 나타난다고 한다.
Range search의 input과 output이며,
RangeSearch(5, 12)를 수행할 때 위와 같은 순서로 찾게 된다고 한다.
이에 대한 pseudo code이다.
Insert도 간단히 표현이 가능하고,
위의 트리에 적합한 자리에 추가할 수 있음을 알 수 있다.
Insert의 pseudo code이고,
Delete의 input과 output이다.
하지만 이때 문제가 발생하는데 트리구조에서 자식노드가 있는 와중에 부모노드만 덜렁 삭제가 불가하다는 점이며,
이때에는 삭제하고자 하는 값을 최상단으로 올린 후 그 자리에 자식노드를 그대로 올리면 된다.
Delete의 pseudo code이다.
바로 퀴즈가 등장하고 1을 제거했을 때 이후 트리의 모습으로 적절한 것을 고르는 문제이다.
답은 C가 되며, 1의 다음 순서로 올바른 2가 올라옴과 동시에 그 자리는 밑의 자식노드가 차지한 것을 볼 수 있다.
이번에는 runtime에 관해 알아본다.
Binary search tree의 운용시간은 어떻게 되는지 질문을 던지며 시작한다.
위와 같은 트리에서 Find(5)를 수행한다면 5가 맨 밑에 존재하기에 복잡도는 O(Depth)가 된다.
바로 퀴즈가 나오고 각 노드에 표시된 알파벳대로 어떤 순서로 소요시간이 많이 걸리는지 알아본다면 A < D < B < C 가 됨을 확인할 수 있다.
여기 새로운 예시가 등장하는데 위의 구조는 뭔가 깊이가 깊어 연산에 좋지 않을 것같으며,
동일한 키값들로 구성한 다른 트리는 깊이가 얕기에 훨신 효율적으로 연산이 가능함을 짐작할 수 있다.
이를 Balance라고 하며 왼쪽과 오른쪽의 subtree들이 균형감있게 형성이 되어야 복잡도가 O(log(n))로 수렴할 수 있다.
그렇다면 Insert와 delete로 인한 balance 붕괴는 어떻게 해결할 수 있냐는 문제가 등장하는데,
이는 Rebalancing 기법으로 해결이 가능하다. 말 그대로 트리를 재건축하는 과정이다.
그 중 Rotations를 보게 되면 A, B, C, X, Y의 키 값 순서가 위와 같을 시 상위노드로 차지하는 키값이 달라지게 된다.
이에 대한 RotateRight의 pseudo code이다.
이제 막바지에 다다라서 5주차에 접어들었다.
이번에는 sort 알고리즘 중 Binary search trees에 관한 내용을 알아본다.
주로 사용되는 곳은 사전같은 것으로 주어진 글자를 통해 알파벳순으로 정렬되어 있어 찾을때 용이하다.
또한 한 학급에서 가장 비슷한 키를 찾을때에도 사용될 수 있다.
Local search의 정의를 보면 key를 통해 데이터로 접근하며 이 때 값들은 정렬이 되어있는 상태여야 한다.
예시를 보면 위와 같이 정렬된 배열에 RangeSearch를 시행하면 해당 범위에 상응하는 값들을 찾아 반환을 해주고 NearestNeighbors를 사용하면 인접값들을 반환해준다.
Insert와 delete를 통해 key값을 추가하거나 삭제할 수도 있다.
위와 같은 배열에서 Inseart(3)을 하게 되면 오름차순의 순서에 맞게 해당하는 자리에 배치하게 되고 delete(10)을 하면 값이 삭제됨과 동시에 한자리씩 당겨지게 된다.
간단한 예시로 위와 같은 명령이 있을 때 결과는,
3, 5, 10, 12 가 최종 배열이므로 그 중 7에 가까운 값들은 5, 10이 됨을 간단히 알 수있다.
도식화된 배열을 보면 위와 같다.
먼저 hash table의 API 연산여부를 확인해보면 위와 같음을 알 수 있다. hash 값에 따라 chaining이 될 가능성이 크기에 RangeSearch와 NearestNeighbors는 불가하다.
배열에서는 모두 가능한 상태이나 배열의 특성상 빈자리가 있으면 안되기 때문에 위와 같은 특성이 나타난다.
Sorted array에서는 정렬이 된 상태이므로 더 빨리 해당 범위에 해당하는 값을 찾기가 쉽고,
근접값들을 찾기에도 수월하다.
대신 값을 추가하거나,
지울 때에는 배열의 특성에 따른다.
Linked list의 경우 해당 범위를 찾는 것또한 배열과 크게 다르지 않으며,
근접값도 마찬가지이다.
대신 값을 추가하거나,
삭제할때 O(1)에 가능한 특징을 가진다.
위에서 각 데이터 구조마다 장단점들을 살펴보았는데 모든 조건을 충족하는 구조는 없었기에 이들을 모두 만족할 만한 구조를 찾아야 한다.
따라서 Binary search tree에 대해 살펴본다.
Binary search의 방법은 데이터의 중앙으로부터 시작하여 방향을 판단 후 다시 그 절반에 접근하기를 반복하며 원하는 위치에 도달할 때까지 진행할 수 있는 방법이다.
위는 15를 찾을 때의 예시이며 큰 차이가 없어보일 수 있으나 구조가 커질 수록 해당 알고리즘의 장점이 부각된다.
위의 배열을 트리모양으로 도식화한 모습이다.
트리의 구조를 보면 우선 루트(root)가 존재하며 왼쪽과 오른쪽에 각각 작고, 큰 값(key)들이 존재하게 된다.
따라서 해당 노드의 key가 있고 상단에는 부모노드가 있으며 아래에는 자녀노드가 있다.
그리고 search tree의 특성으로 중요한 것은 자기 자신보다 왼쪽에 존재하는 자식노드들보다는 키값이 크며 오른쪽의 자식노드들보다는 키값이 작다.
퀴즈가 나왔는데 어떤 것이 search tree 특성을 만족하냐인데 답은 B가 되겠다.
A는 루트의 자식노드들간의 순서가 바로 맞지 않음을 알 수 있고 C는 루트인 5보다 오른쪽에 위치한 자식노드들 중 4가 존재하기에 만족하지 않음을 찾았다.
그리하여 binary search tree를 활용하여 기본 동작들에 대해 이해해보고자 한다.
우선 find 함수는 key k, Root R에 대해 루트 R을 가진 트리내에 k값을 찾는 역할을 수행한다.
예시로 위와 같은 트리가 존재할 때 Find(6)를 수행하면,
루트인 7의 왼쪽으로 내려가서 다시금 4의 오른쪽으로 내려가서 최종적으로 6을 찾게 된다.
이를 pseudo code로 서술하면 위와 같을 것이며,
만약 없는 키값을 찾게된다면 마지막에 도달한 값을 반환한다고 한다.
위의 내용을 포함한 수정된 find 함수이다.
이웃요소에 대한 내용을 확인할 때에는,
Next라는 함수를 사용하게 되며 N의 노드가 있을 때 이 다음으로 가장 큰키를 반환한다고 한다.
첫번째 예시를 보면 오른쪽에만 자식노드를 가지고 있다면 가장 하위의 값을 반환하게 될 것이고,
만약 오른쪽 자식노드들이 없다면 자기자신이 반환될 것이라고 한다.
Next에 대한 pseudo code이다.
Left Descendant의 pseudo code이다.
Right Ancestor의 pseudo code이다.
위 내용에 대한 퀴즈가 나왔는데 질문이 현재 Next 함수의 세세한 버그를 찾으라고 나오는데 2번 보기에 있듯 N 자신이 가장 큰 값일 때 에러가 나타난다고 한다.
Range search의 input과 output이며,
RangeSearch(5, 12)를 수행할 때 위와 같은 순서로 찾게 된다고 한다.
이에 대한 pseudo code이다.
Insert도 간단히 표현이 가능하고,
위의 트리에 적합한 자리에 추가할 수 있음을 알 수 있다.
Insert의 pseudo code이고,
Delete의 input과 output이다.
하지만 이때 문제가 발생하는데 트리구조에서 자식노드가 있는 와중에 부모노드만 덜렁 삭제가 불가하다는 점이며,
이때에는 삭제하고자 하는 값을 최상단으로 올린 후 그 자리에 자식노드를 그대로 올리면 된다.
Delete의 pseudo code이다.
바로 퀴즈가 등장하고 1을 제거했을 때 이후 트리의 모습으로 적절한 것을 고르는 문제이다.
답은 C가 되며, 1의 다음 순서로 올바른 2가 올라옴과 동시에 그 자리는 밑의 자식노드가 차지한 것을 볼 수 있다.
이번에는 runtime에 관해 알아본다.
Binary search tree의 운용시간은 어떻게 되는지 질문을 던지며 시작한다.
위와 같은 트리에서 Find(5)를 수행한다면 5가 맨 밑에 존재하기에 복잡도는 O(Depth)가 된다.
바로 퀴즈가 나오고 각 노드에 표시된 알파벳대로 어떤 순서로 소요시간이 많이 걸리는지 알아본다면 A < D < B < C 가 됨을 확인할 수 있다.
여기 새로운 예시가 등장하는데 위의 구조는 뭔가 깊이가 깊어 연산에 좋지 않을 것같으며,
동일한 키값들로 구성한 다른 트리는 깊이가 얕기에 훨신 효율적으로 연산이 가능함을 짐작할 수 있다.
이를 Balance라고 하며 왼쪽과 오른쪽의 subtree들이 균형감있게 형성이 되어야 복잡도가 O(log(n))로 수렴할 수 있다.
그렇다면 Insert와 delete로 인한 balance 붕괴는 어떻게 해결할 수 있냐는 문제가 등장하는데,
이는 Rebalancing 기법으로 해결이 가능하다. 말 그대로 트리를 재건축하는 과정이다.
그 중 Rotations를 보게 되면 A, B, C, X, Y의 키 값 순서가 위와 같을 시 상위노드로 차지하는 키값이 달라지게 된다.
이에 대한 RotateRight의 pseudo code이다.
댓글
댓글 쓰기