차이점을 좀 더 잘 이해하고 싶지만 내 수준까지 분류 할 수있는 출처를 찾지 못했습니다.AVL 트리보다 적색 검정 트리에서 삽입 및 삭제가 더 빨리 어떻게됩니까?
두 나무가 삽입 당 최대 2 회전을 필요로한다는 것을 알고 있습니다. 그럼 붉은 검정 나무에 삽입하는 것이 더 빠릅니까?
그리고 삽입은 어떻게 red-black의 O (1) 동안 avl 트리에서 O (log n) 회전을 필요로합니까?
음, 레벨이 정확히 무엇인지 모르겠지만, 간단히 말해서 빨강 - 검정 나무는 AVL 나무보다 덜 균형을 이룹니다. 빨강 - 검정 나무의 경우 루트에서 가장 먼 잎까지의 경로는 루트에서 가장 가까운 잎까지의 길이의 두 배에 불과하지만 AVL 나무의 경우 두 인접한 하위 트리 사이에 하나 이상의 레벨 차이가 없습니다. 이렇게하면 AVL 트리에서 삽입 및 삭제가 약간 비용이 많이 들지만 검색은 더 빨라집니다. 두 데이터 구조의 점근 적 및 최악의 경우의 동작은 동일합니다 (런타임 (회전 수 아님)은 두 경우 모두 삽입시 O (log n)이고, 언급 한 O (1)은 소위 amortized runtime입니다. .
두 데이터 구조의 짧은 비교는 this paragraph을 참조하십시오.
감사합니다. 나는 최대 회전을보고 있었지만 전체 평균은 보지 못했습니다. 몇 가지 예를 가지고 작업 한 후에 나는 당신이 말한 것을 분명하게 볼 수 있습니다. 나는 상각 된 런타임이 그것을 체크 아웃 할 것 인 지 모른다. – user2626445
붉은 검정 나무에서는 삽입 및 삭제가 더 빠르지 않습니다. 이것은 일반적인 암시이며 가정은 암갈색 나무가 AVL (.6 대 .7)보다 인서트 당 평균 회전 수가 약간 적다는 사실에 근거합니다.
Java에서 TreeMap (red-black)을이 TreeMapAVL 구현과 비교하여 직접 확인할 수 있으며 일반적인 가정이지만 잘못된 가정 대신 정확한 숫자를 얻을 수 있습니다. https://github.com/dmcmanam/bbst-showdown
나는이 바보가 누가이 질문에 투표했는지 모른다. –