레드-블랙 트리 삽입 계산기

① 모든 노드는 빨강 아니면 검정, ② 뿌리는 검정, ③ 모든 잎(NIL)은 검정, ④ 빨강 노드의 자식은 둘 다 검정, ⑤ 어느 노드에서 잎까지 내려가든 지나는 검정 노드 수가 같다입니다. ④와 ⑤가 함께 걸리면 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 못해 높이가 2·log₂(n+1) 이하로 묶입니다.

고치기 쉬운 성질만 깨지게 만들기 위해서입니다. 검정으로 넣으면 그 경로의 검정 노드 수만 하나 늘어 «모든 경로의 검정 수가 같다»가 곧바로 깨지는데, 이건 나무 전체에 걸린 성질이라 되돌리기 어렵습니다. 빨강으로 넣으면 깨질 수 있는 것은 «빨강이 잇달음» 하나뿐이고, 그 언저리에서 색을 바꾸거나 돌려 고칠 수 있습니다.

삼촌(부모의 형제)의 색이 갈림길입니다. 삼촌이 빨강이면 부모와 삼촌을 검정으로, 할아버지를 빨강으로 칠하고 할아버지에서 다시 보는 것으로 끝나 회전이 없습니다. 삼촌이 검정이면 회전이 필요하며, 새 노드가 안쪽 자식이면 먼저 부모를 돌려 바깥쪽으로 만든 뒤 할아버지를 돌립니다. 삽입 한 번에 회전은 많아야 두 번입니다.

한 줄로 정리하기 어렵습니다. 무작위 수열 2만 개로 재어 보면 단일 회전 기준으로 레드-블랙이 적은 경우가 77%지만 더 많은 경우도 8% 있고, 높이는 같은 경우가 97%로 대부분입니다. «AVL이 더 낮다»는 최악의 경우 한계(1.44·log₂n 대 2·log₂n) 이야기라 1부터 차례로 넣는 것처럼 치우친 입력에서 또렷하게 드러납니다.

AVL의 LR·RL 회전은 이름은 하나지만 실제로는 단일 회전을 두 번 하는 것입니다. 그대로 1로 세면 레드-블랙이 억울하게 많아 보이므로, 이 도구는 LR·RL을 2로 쳐서 맞춘 값으로 견줍니다. 맞추기 전에는 레드-블랙이 더 많아 보이는 경우가 85%로 나왔는데, 자료구조의 성질이 아니라 세는 방법의 문제였습니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.