트리

편향 이진탐색트리를 해결하기 위한 방법(2) RED-BLACK TREE

2023.04.13

이전에 포스팅 했던 편향 이진 탐색 트리를 해결 하기 위한 방법 중 하나인 AVL TREE 가 아닌 또 다른 해결 방법인 RED-BLACK TREE에 대해서 알아보자. RED-BLACK TREE 레드-블랙 트리도 처음 공부할 때, 많이 헷갈릴 수 있다. 특히 나중에 해결하기 위한 방법으로 Recoloring 과 Restructuring 방식 두 가지가 나오는데, 언제 적용해야 하는지가 분명하지만 이상하게도 자주 헷갈린다! 이를 쉽게 구분하기 위한 개인적인 팁도 제공해보려고 한다. 먼저 RED-BLACK TREE 의 특징에 대해서 알아보자. RED-BLACK TREE 특징 모든 노드는 빨간색 or 검은색 이다. 루트 노드는 무조건 검은색이다. RED-BLACK 트리에 존재하는 NIL은 검은색이다. 빨간색 ..

Computer Science/Data Structure

편향 이진탐색트리를 해결하기 위한 방법(1) AVL TREE

2023.04.10

AVL(Adelson-Velsky and Landis)TREE AVL의 full form은 발명자의 이름이다. 먼저 AVL 트리의 특징에 대해서 살펴보자. 특징 이진탐색트리의 속성을 그대로 가진다. 왼쪽, 오른쪽 서브트리의 높이 차이가 최대 1이어야 한다. 높이 차이가 1보다 커지면 Rotation을 통해 균형을 맞춘다. Rotation 방식을 설명하기 전에, 먼저 높이 차이를 비교하는 BF에 대해서 먼저 이해할 필요가 있다. BF(Balance Factor) $ BF(K) = K_{leftHeight} - K_{rightHeight} $, K = Node 수식처럼 노드의 왼쪽 높이와 오른쪽 높이를 비교하는 요소를 BF 라고 한다. 만약 height의 의미가 이해가 안된다면, 트리의 특징에서 height..

편향 이진탐색트리를 해결하기 위한 방법(2) RED-BLACK TREE

편향 이진탐색트리를 해결하기 위한 방법(1) AVL TREE

티스토리툴바