붉은 나무의 단점은 무엇입니까?

내가 레드 - 블랙 나무에 대해 읽었던 모든 것에서 그것은 그들이 데이터를 저장하기위한 최상의 데이터 구조 인 것처럼 보입니다.붉은 나무의 단점은 무엇입니까?

나는 데이터베이스를 구축하려고하는데, 레드 - 블랙 트리 구현의 측면에서, 내가 더 조심해야 할 부분과해야 할 부분이 궁금합니다.

레드 - 블랙은 정말 완벽합니까?

출처

2011-05-10 Ilya GAzman

레드 - 블랙 트리는 모든 데이터 액세스에있어 완벽하지 않습니다. 그들은 그들의 위치를 가지고 있지만 해쉬 맵 (plain map)과 일반 오래된 목록과 같은 다른 방법이 많은 경우 더 좋습니다.

빨간 검은 나무의 한 가지 단점은 이진 트리이므로 O (lg (n))입니다. 여기서 해시 테이블은 O (1) 조회를 사용합니다.

출처

2011-05-10 15:03:18

해시 테이블이 조회를위한 O (1)이라는 것을 의미한다고 생각합니다. –

@ 브레인 : 당신 말이 맞아, 나는 일정한 시간을 생각하고 있었지만 확실하게 타이핑하지 않았다. 고마워. –

데이터 조회 및 업데이트 방법에 따라 다릅니다. 예를 들어 순서가 지정된 데이터가 필요하지 않은 경우 해시 맵은 대수 대신 일정 시간 조회/삽입이 (예상) 있기 때문에 가능성이 더 높습니다. 주문 된 데이터가 필요하더라도 적/검은 색 나무가 완벽하지 않을 수 있습니다 - 특히 디스크 기반 데이터베이스를 구현하는 경우가 아닙니다. 디스크 기반 I/O에서 순차 블록 읽기와 비교할 때 탐색이 비싸므로 목표는 디스크 액세스 수를 최소화하는 것입니다. 이러한 경우 B- 트리 (또는 B + 트리 또는 B * 트리)가 더 좋습니다.이 모든 것은 디스크에 저장 될 때 빠르게 수행되도록 설계되었습니다.

출처

2011-05-10 15:07:18

붉은 나무의 단점은 무엇입니까?

답변

관련 문제