모각코 1일차 결과 (1.20)

self-balancing Binary Search Tree(BST) 에는 대표적으로 AVL Tree와 Red Black Tree 가 있다.

AVL Tree -> | left 서브트리의 height - right 서브트리의 height |가 1이하인 트리

AVL Tree의 예

AVL Tree가 아닌 예

AVL Tree를 구현하는 이유

대부분의 BST operations (e.g., search, max, min, insert, delete.. etc)는 O(h)의 시간이 소요된다. (h는 BST의 높이로 logn 정도)

그러나, BST가 skewed Binary tree가 될 경우, O(n)의 시간이 소요될 수가 있다.

따라서 left, right 서브트리의 height에 balance를 맞춰 O(logn)의 시간을 보장하기 위해 AVL Tree를 구현한다.

AVL Tree에서 balance를 유지하는 방법

left, right rotation을 이용한다.

Red-Black Tree -> 아래의 규칙들을 만족시키는 트리

1. 모든 노드는 red, black 중 하나이다.

2. 트리의 root 노드는 항상 black이다.

3. red인 노드는 이웃할 수 없다. (즉, red인 노드는 red인 parent와 red인 child를 가질 수 없다.)

4. 한 노드로 부터(root 노드 포함) 모든 descendant NULL 노드로 가는 path에는 항상 같은 수의 black 노드가 존재한다.

Red-Black Tree의 예

Red-Black Tree를 구현하는 이유

대부분의 BST operations (e.g., search, max, min, insert, delete.. etc)는 O(h)의 시간이 소요된다. (h는 BST의 높이로 logn 정도)

그러나, BST가 skewed Binary tree가 될 경우, O(n)의 시간이 소요될 수가 있다.

따라서 left, right 서브트리의 height에 balance를 맞춰 O(logn)의 시간을 보장하기 위해 AVL Tree를 구현한다.

Red-Black Tree에서 balance를 유지하는 방법

Recoloring, Rotation(left, right)

AVL Tree vs Red-Black Tree

AVL Tree가 Red-Black Tree에 비해 좀 더 균형잡힌 트리이나, insertion,및deletion 과정에서 많은 rotation이 발생할 수 있다.

따라서, 프로그램이 많은 insertion과 deletion 작업을 포함하고 있을 경우 Red-Black Tree를 사용하는 것이 효과적이다.

만약 프로그램이 적은 insertion과 deletion 작업을 포함하고 있고, 많은 search 작업을 포함하고 있을 경우 AVL Tree를 사용하는 것이 효과적이다.