레드-블랙 트리

https://stackoverflow.com/questions/20734

09-06-2019
|

문제

최근에 읽은 여러 책에서 이진 트리와 이진 검색에 대한 언급을 본 적이 있지만, 아직 컴퓨터 과학 공부를 시작하는 단계이기 때문에 실제로 알고리즘과 데이터를 다루는 수업을 들어본 적이 없습니다. 심각한 방식으로 구조.

나는 일반적인 소스(Wikipedia, Google)를 둘러보았고 (특히) Red-Black 트리의 유용성과 구현에 대한 대부분의 설명이 너무 조밀하고 이해하기 어려웠습니다.필요한 배경 지식을 갖춘 사람이라면 완벽하게 이해가 되겠지만 현재로서는 거의 외국어처럼 읽혀집니다.

그렇다면 프로그래밍하는 동안 수행하는 일반적인 작업 중 일부에서 이진 트리가 유용한 이유는 무엇입니까?그 외에도 어떤 트리를 선호하시나요(샘플 구현을 포함해 주세요) 그리고 그 이유는 무엇입니까?

해결책

레드 블랙 트리는 균형 잡힌 트리를 만드는 데 좋습니다.이진 검색 트리의 주요 문제점은 매우 쉽게 불균형하게 만들 수 있다는 것입니다.첫 번째 숫자가 15라고 상상해 보세요.그러면 그 이후의 모든 숫자는 점점 15보다 작아집니다.왼쪽에는 매우 무겁고 오른쪽에는 아무것도 없는 나무가 있을 것입니다.

Red Black 트리는 삽입하거나 삭제할 때마다 트리의 균형을 강제하여 이 문제를 해결합니다.이는 상위 노드와 하위 노드 간의 일련의 회전을 통해 수행됩니다.알고리즘은 약간 길긴 하지만 실제로 매우 간단합니다.CLRS(Cormen, Lieserson, Rivest 및 Stein) 교과서인 "알고리즘 소개"를 선택하고 RB Trees를 읽어 보는 것이 좋습니다.

구현도 그다지 짧지 않으므로 여기에 포함시키는 것이 최선이 아닐 수도 있습니다.그럼에도 불구하고 나무를 사용한다. 널리 많은 데이터에 액세스해야 하는 고성능 앱의 경우.삽입/삭제에 대한 오버헤드가 상대적으로 적으면서 노드를 찾는 매우 효율적인 방법을 제공합니다.다시 한 번 CLRS를 살펴보고 CLRS가 어떻게 사용되는지 읽어 보는 것이 좋습니다.

BST는 명시적으로 사용되지 않을 수 있지만 일반적으로 트리를 사용하는 한 가지 예는 거의 모든 최신 RDBMS에 있습니다.마찬가지로 파일 시스템은 일종의 트리 구조로 거의 확실하게 표시되며 파일도 마찬가지로 그런 방식으로 인덱싱됩니다.나무는 Google의 힘입니다.나무는 인터넷의 거의 모든 웹사이트에 힘을 실어줍니다.

다른 팁

나는 "그래서 프로그래밍하는 동안 수행하는 일반적인 작업 중 일부에서 이진 트리가 유용한 이유는 무엇입니까?"라는 질문에만 답하고 싶습니다.

이것은 많은 사람들이 동의하지 않는 큰 주제입니다.어떤 사람들은 이진 검색 트리나 유향 그래프와 같이 CS 학위에서 가르치는 알고리즘이 일상적인 프로그래밍에 사용되지 않으므로 관련이 없다고 말합니다.다른 사람들은 이러한 알고리즘과 데이터 구조가 모든 프로그래밍의 기초이며 직접 작성할 필요가 없더라도 이를 이해하는 것이 필수적이라고 말하면서 동의하지 않습니다.이는 좋은 면접 및 채용 관행에 대한 대화로 필터링됩니다.예를 들어, 스티브 예게 에 대한 기사가 있습니다 구글 인터뷰 중 이 질문에 대한 답변입니다.이 논쟁을 기억하십시오.경험있는 사람들은 동의하지 않습니다.

일반적인 비즈니스 프로그래밍에서는 이진 트리나 심지어 트리를 자주 생성할 필요가 없을 수도 있습니다.그러나 트리를 사용하여 내부적으로 작동하는 많은 클래스를 사용하게 됩니다.모든 언어의 핵심 조직 클래스 중 상당수는 트리와 해시를 사용하여 데이터를 저장하고 액세스합니다.

더 높은 성과를 내는 노력이나 비즈니스 프로그래밍의 표준을 다소 벗어난 상황에 참여하고 있다면 나무가 즉각적인 친구가 될 것입니다.다른 포스터에서 말했듯이 트리는 모든 종류의 데이터베이스와 인덱스의 핵심 데이터 구조입니다.이는 데이터 마이닝 및 시각화, 고급 그래픽(2D 및 3D) 및 기타 여러 계산 문제에 유용합니다.

나는 다음과 같은 형태로 이진 트리를 사용했습니다. BSP(바이너리 공간 파티셔닝) 트리 3D 그래픽에서.저는 현재 Flash/Flex 애플리케이션에서 정보 시각화를 위해 대량의 지오코딩된 데이터와 기타 데이터를 정렬하기 위해 트리를 다시 살펴보고 있습니다.하드웨어의 경계를 넓히거나 더 낮은 하드웨어 사양에서 실행하려는 경우 항상 최상의 알고리즘을 이해하고 선택하면 실패와 성공의 차이를 만들 수 있습니다.

BST가 정확히 무엇에 좋은지 언급한 답변은 없습니다.

원하는 작업이 값으로만 조회하는 것이라면 해시테이블이 훨씬 더 빠릅니다. O(1) 삽입 및 조회(상각된 최상의 경우)입니다.

BST는 O(log N) 조회입니다. 여기서 N은 트리의 노드 수이고 삽입도 O(log N)입니다.

RB 및 AVL 트리는 이 속성 때문에 언급된 또 다른 답변처럼 중요합니다. 일반 BST가 순서대로 작성된 값으로 생성되면 트리는 삽입된 값 수만큼 높아져 조회 성능에 좋지 않습니다.

RB와 AVL 트리의 차이점은 삽입 또는 삭제 후 재조정에 필요한 회전에 있으며, AVL 트리는 재조정에 대해 O(log N)이고 RB 트리는 O(1)입니다.이러한 지속적인 복잡성의 이점에 대한 예는 영구 데이터 원본을 유지하는 경우입니다. 롤백 변경 사항을 추적해야 하는 경우 AVL 트리를 사용하여 O(log N) 가능한 변경 사항을 추적해야 합니다.

해시 테이블 대신 나무 한 그루의 비용을 기꺼이 지불하려는 이유는 무엇입니까?주문하다!해시 테이블에는 순서가 없습니다. 반면에 BST는 구조로 인해 항상 자연스럽게 순서가 지정됩니다.따라서 배열이나 다른 컨테이너에 많은 데이터를 던진 다음 나중에 정렬하는 경우 BST가 더 나은 솔루션이 될 수 있습니다.

트리의 순서 속성은 순서대로, 깊이 우선, 너비 우선, 사전 순서, 사후 순서 등 다양한 순서의 반복 기능을 제공합니다.이러한 반복 알고리즘은 다양한 상황에서 검색하려는 경우 유용합니다.

레드 블랙 트리는 언어 라이브러리, C++ Set 및 Map, .NET SortedDictionary, Java TreeSet 등의 거의 모든 주문 컨테이너에서 내부적으로 사용됩니다.

그래서 나무는 매우 유용하며, 당신도 모르게 나무를 꽤 자주 사용할 수도 있습니다.당신은 아마 결코하지 않을 것입니다 필요 흥미로운 프로그래밍 연습으로 적극 추천하고 싶습니다.

레드 블랙 트리와 B-트리는 모든 종류의 영구 저장소에 사용됩니다.트리가 균형을 이루기 때문에 폭과 깊이 순회 성능이 완화됩니다.

거의 모든 최신 데이터베이스 시스템은 데이터 저장을 위해 트리를 사용합니다.

Micheal이 말했듯이 BST는 세상을 돌아가게 만듭니다.구현할 좋은 트리를 찾고 있다면 다음을 살펴보십시오. AVL 트리 (위키피디아).균형 조건이 있으므로 O(logn)이 보장됩니다.이러한 종류의 검색 효율성은 모든 종류의 색인 프로세스에 적용하는 것을 논리적으로 만듭니다.더 효율적인 유일한 방법은 해싱 기능이지만, 그 기능은 매우 빠르고 빠르며 서두르게 됩니다.또한, 당신은 생일 역설 (비둘기 구멍 문제라고도 함).

어떤 교재를 사용하고 있나요?우리는 사용했었다 Java의 데이터 구조 및 분석 마크 앨런 와이스 지음.실제로 이 글을 쓰고 있는 동안 무릎 위에 이 책을 열어 두었습니다.Red-Black 트리에 대한 훌륭한 섹션이 있으며, 여기에 설명된 모든 트리를 구현하는 데 필요한 코드도 포함되어 있습니다.

레드-블랙 나무는 균형을 유지하므로 아이템을 꺼내기 위해 깊게 이동할 필요가 없습니다.절약된 시간은 최악의 경우 RB 트리를 O(log()n))로 만드는 반면, 불운한 이진 트리는 편향된 구성에 들어가 O(n)에서 검색을 나쁜 경우로 만들 수 있습니다.이는 실제로 또는 임의의 데이터에서 발생합니다.따라서 시간이 중요한 코드(데이터베이스 검색, 네트워크 서버 등)가 필요한 경우 RB 트리를 사용하여 정렬되거나 정렬되지 않은 목록/세트를 지원합니다.

하지만 RBTree는 멍청한 사람들을 위한 것입니다!AI를 수행하고 검색을 수행해야 하는 경우 상태 정보를 많이 포크하게 됩니다.지속적인 빨간색-검정을 사용하여 O(log(n))에서 새 상태를 분기할 수 있습니다.영구 레드 블랙 트리는 형태학적 작업(삽입/삭제) 전후에 트리의 복사본을 유지하지만 전체 트리를 복사하지는 않습니다(일반적으로 O(log(n)) 작업).Java용 영구 레드-블랙 트리를 오픈 소스로 제공했습니다.

http://edinburghhacklab.com/2011/07/a-java-implementation-of-pertant-red-black-trees-open-sourced/

내가 본 레드-블랙 트리에 대한 가장 좋은 설명은 Cormen, Leisersen 및 Rivest의 '알고리즘 소개'에 있는 설명입니다.부분적으로 구현하는 것만으로도 충분히 이해할 수 있었습니다(삽입만).다음과 같은 애플릿도 꽤 많이 있습니다. 이 하나 프로세스를 애니메이션화하고 트리 구조를 구축하는 알고리즘의 그래픽 표현을 보고 단계별로 살펴볼 수 있는 다양한 웹 페이지에서.

사람들이 어떤 트리를 사용하는지 묻기 때문에 Red Black 트리는 기본적으로 2-3-4 B-트리(즉, 4차 B-트리)라는 것을 알아야 합니다.B-트리는 ~ 아니다 (귀하의 질문에서 요청한 대로) 이진 트리와 동일합니다.

여기나중에 RBTree로 발전한 대칭 이진 B-트리로 알려진 초기 추상화를 설명하는 훌륭한 리소스입니다.이해하기 전에 B-트리를 잘 이해해야 합니다.요약:레드 블랙 트리의 '빨간색' 링크는 B-트리 노드(키 범위 내의 값)의 일부인 노드를 나타내는 방법인 반면, '검은색' 링크는 B-트리에서 수직으로 연결된 노드를 나타냅니다.

따라서 Red Black 트리의 규칙을 B-트리 측면에서 변환하면 다음과 같은 결과가 나옵니다(저는 다음 형식을 사용합니다). 레드 블랙 트리 규칙 => B 트리 동등물):

1) 노드는 빨간색이거나 검은색입니다.=> B-트리의 노드는 노드의 일부이거나 새 수준의 노드일 수 있습니다.

2) 뿌리는 검은색이다.(이 규칙은 분석에 영향을 주지 않기 때문에 생략되기도 합니다.) => 루트 노드는 내부 루트 노드의 일부 또는 가상 부모 노드의 하위 노드로 간주될 수 있습니다.

3) 모든 잎(NIL)은 검은색입니다.(모든 잎은 루트와 같은 색입니다.) => RB 트리를 표현하는 한 가지 방법은 잎을 생략하는 것이므로 이를 배제할 수 있습니다.

4) 모든 빨간색 노드의 두 자식 노드는 모두 검정색입니다.=> B-트리의 내부 노드의 자식은 항상 다른 수준에 있습니다.

5) 주어진 노드에서 그 자손 리프까지의 모든 단순 경로에는 동일한 수의 블랙 노드가 포함됩니다.=> B-트리는 모든 리프 노드가 동일한 깊이에 있어야 하므로 균형이 유지됩니다. 따라서 B-트리 노드의 높이는 레드 블랙 트리의 루트에서 리프까지의 블랙 링크 수로 표시됩니다. )

또한 Robert Sedgewick의 더 간단한 '비표준' 구현이 있습니다. 여기:(그는 그 책의 저자이다. 알고리즘 웨인과 함께)

여기에는 열이 많이 나지만 빛은 많지 않으므로 제공할 수 있는지 살펴보겠습니다.

첫 번째, 에서 RB 트리는 연속 정수의 0% 희소 인덱스에 있는 정수 "키"가 아닌 이상 키를 가져와 관련 값을 반환할 수 없는 배열과 달리 연관 데이터 구조입니다.배열의 크기도 커질 수 없습니다(예, realloc()에 대해서도 알고 있지만 내부적으로는 새 배열과 memcpy()가 필요함). 따라서 이러한 요구 사항 중 하나라도 해당되면 배열은 작동하지 않습니다. .배열의 메모리 효율성은 완벽합니다.낭비는 없지만 그다지 똑똑하거나 유연하지는 않습니다. realloc()은 견딜 수 없습니다.

두번째, 연관 데이터 구조인 요소 배열에 대한 bsearch()와 달리 RB 트리는 크기가 동적으로 증가(및 축소)될 수 있습니다.bsearch()는 알려진 크기의 데이터 구조를 색인화하는 데 적합하며 해당 크기는 그대로 유지됩니다.따라서 데이터의 크기를 미리 모르거나 새 요소를 추가하거나 삭제해야 하는 경우 bsearch()가 종료됩니다.Bsearch() 및 qsort()는 모두 클래식 C에서 잘 지원되고 메모리 효율성이 좋지만 많은 응용 프로그램에 충분히 동적이지 않습니다.빠르고 쉬우며 실시간 앱을 다루지 않는 경우에도 충분히 유연하기 때문에 제가 개인적으로 가장 좋아하는 것입니다.또한 C/C++에서는 비교하려는 struc{} 멤버를 가리키는 데이터 레코드에 대한 포인터 배열을 정렬한 다음 포인터를 순서대로 읽도록 포인터 배열의 포인터를 재정렬할 수 있습니다. 포인터 정렬이 끝나면 데이터가 정렬된 순서로 생성됩니다.메모리 매핑된 데이터 파일과 함께 이를 사용하는 것은 메모리 효율성이 매우 높고 빠르며 상당히 쉽습니다.당신이 해야 할 일은 비교 기능에 몇 개의 "*"를 추가하는 것뿐입니다.

제삼, 고정된 크기여야 하고 일단 채워지면 확장할 수 없는 해시테이블과 달리 RB 트리는 자동으로 자체적으로 성장하고 균형을 유지하여 O(log(n)) 성능 보장을 유지합니다.특히 RB 트리의 키가 int인 경우 해시 테이블의 복잡성이 O(1)이더라도 1은 매우 비싼 해시 계산이 될 수 있으므로 해시보다 빠를 수 있습니다.트리의 여러 1클럭 정수 비교는 해시 충돌 및 재해시에 대한 재해싱 및 malloc() 공간은 말할 것도 없이 100클럭+ 해시 계산보다 성능이 뛰어난 경우가 많습니다.마지막으로 ISAM 액세스와 데이터에 대한 키 액세스를 원하는 경우 트리 구현의 자연스러운 데이터 순서와 달리 해시 테이블에 고유한 데이터 순서가 없으므로 해시가 제외됩니다.해시 테이블의 일반적인 용도는 컴파일러의 예약어 테이블에 대한 키 입력 액세스를 제공하는 것입니다.메모리 효율성이 뛰어납니다.

네번째, 목록에서 매우 낮은 것은 연결 또는 이중 연결 목록으로, 배열과 달리 자연스럽게 요소 삽입 및 삭제를 지원하고 크기 조정도 지원합니다.각 요소는 다음 요소로 이동하는 방법만 알고 있으므로 모든 데이터 구조 중에서 가장 느립니다. 따라서 데이터를 찾으려면 평균적으로 (element_knt/2)개의 링크를 검색해야 합니다.이는 목록 중간 어딘가에서 삽입과 삭제가 일반적인 경우, 특히 목록이 순환적이고 비용이 많이 드는 프로세스를 제공하여 링크를 읽는 데 시간이 상대적으로 적게 걸리는 경우에 주로 사용됩니다.내 일반적인 RX는 크기를 늘릴 수 있는 유일한 요구 사항인 경우 연결 목록 대신 임의로 큰 배열을 사용하는 것입니다.배열의 크기가 부족하면 더 큰 배열을 realloc()할 수 있습니다.STL은 벡터를 사용할 때 "은밀히" 이 작업을 수행합니다.조잡하지만 삽입, 삭제 또는 키 조회가 필요하지 않으면 잠재적으로 1,000배 더 빨라질 수 있습니다.특히 이중 연결 목록의 경우 메모리 효율성이 낮습니다.실제로 두 개의 포인터가 필요한 이중 연결 목록은 빠르고 정렬된 검색 특성이 전혀 없는 반면 레드-블랙 트리만큼 메모리 비효율적입니다.

다섯, 트리는 다른 데이터 구조보다 정렬된 데이터에 대해 많은 추가 작업을 지원합니다.예를 들어, 많은 데이터베이스 쿼리는 공통 상위를 지정하고 상위가 "소유"하는 트리 부분에 후속 처리를 집중함으로써 리프 값의 범위를 쉽게 지정할 수 있다는 사실을 활용합니다.트리의 작은 영역, 즉 부모가 소유한 노드와 부모 자체만 잠그면 되므로 이 접근 방식이 제공하는 멀티스레딩의 가능성은 분명합니다.

간단히 말해서, 나무는 데이터 구조의 캐딜락입니다.사용된 메모리 측면에서 높은 비용을 지불하지만 완전히 자체 유지 관리되는 데이터 구조를 얻게 됩니다.이것이 다른 답변에서 지적했듯이 트랜잭션 데이터베이스가 거의 독점적으로 트리를 사용하는 이유입니다.

Red-Black 트리가 그래픽적으로 어떻게 보이는지 보고 싶다면 다음과 같이 Red-Black 트리 구현을 코딩했습니다. 여기서 다운로드하세요

IME, RB 트리 알고리즘을 이해하는 사람은 거의 없습니다.사람들은 규칙을 반복해서 설명할 수 있지만 이해하지 못합니다. 왜 그 규칙과 그 규칙이 어디서 왔는지.나도 예외는 아니다 :-)

이러한 이유로 나는 AVL 알고리즘을 선호합니다. 이해하다.일단 이해하고 나면 이해가 되기 때문에 처음부터 코딩할 수 있습니다.

나무는 빠를 수 있습니다.균형 이진 트리에 백만 개의 노드가 있는 경우 하나의 항목을 찾으려면 평균 20번의 비교가 필요합니다.연결된 목록에 백만 개의 노드가 있는 경우 동일한 항목을 찾으려면 평균 50만 번의 비교가 필요합니다.

그러나 트리의 균형이 맞지 않으면 목록만큼 느릴 수 있습니다. 그리고 또한 저장하는 데 더 많은 메모리가 필요합니다.대부분의 노드에 오른쪽 자식이 있지만 왼쪽 자식은 없는 트리를 상상해 보세요.그것 ~이다 하지만 왼쪽 노드가 나타나면 왼쪽 노드에 넣을 메모리 공간을 확보해야 합니다.

어쨌든, AVL 트리 최초의 균형 이진 트리 알고리즘이며 이에 대한 Wikipedia 기사는 매우 명확합니다.레드-블랙 나무에 관한 Wikipedia 기사는 솔직히 진흙처럼 명확합니다.

이진 트리 외에도 B-트리는 각 노드가 많은 값을 가질 수 있는 트리입니다.B-트리는 ~ 아니다 이진 트리는 그 이름일 뿐입니다.메모리를 효율적으로 활용하는 데 정말 유용합니다.트리의 각 노드는 하나의 메모리 블록에 맞게 크기를 조정할 수 있으므로 디스크에 페이징된 메모리에서 수많은 다른 항목을 (천천히) 찾지 않아도 됩니다.여기에 놀라운 예가 있습니다. B-트리.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow