레드-블랙 트리
최근에 읽은 여러 책에서 이진 트리와 이진 검색이 언급되는 것을 보았지만 아직 컴퓨터 과학 공부를 시작할 때 알고리즘과 데이터를 실제로 다루는 수업을 아직 듣지 않았습니다. 심각한 방식으로 구조.
나는 전형적인 소스 (Wikipedia, Google)를 둘러 보았고, (특히) Red-Black 트리의 유용성과 구현에 대한 대부분의 설명은 밀도가 높고 이해하기 어렵습니다. 나는 필요한 배경을 가진 사람에게는 완벽하게 이해되지만 현재 거의 외국어처럼 읽습니다.
그렇다면 프로그래밍 중에 수행하는 일반적인 작업 중 일부에서 바이너리 트리를 유용하게 만드는 것은 무엇입니까? 그 외에도 어떤 트리를 선호하고 (샘플 구현을 포함 해주세요) 그 이유는 무엇입니까?
레드 블랙 나무는 균형 잡힌 나무를 만드는 데 좋습니다. 이진 검색 트리의 주요 문제는 쉽게 불균형을 만들 수 있다는 것입니다. 첫 번째 숫자가 15라고 상상해보세요. 그 이후의 모든 숫자는 점점 더 작아집니다. 왼쪽은 매우 무겁고 오른쪽에는 아무것도없는 나무가 있습니다.
레드 블랙 트리는 삽입하거나 삭제할 때마다 나무가 균형을 이루도록 강제함으로써이를 해결합니다. 조상 노드와 자식 노드 사이의 일련의 회전을 통해이를 수행합니다. 알고리즘은 약간 길지만 실제로는 매우 간단합니다. CLRS (Cormen, Lieserson, Rivest 및 Stein) 교과서 "Introduction to Algorithms"를 선택하고 RB Trees를 읽어 보는 것이 좋습니다.
구현도 그렇게 짧지 않으므로 여기에 포함하는 것이 가장 좋지 않을 수 있습니다. 그럼에도 불구하고 트리는 많은 데이터에 액세스해야하는 고성능 앱에 광범위하게 사용됩니다 . 삽입 / 삭제의 상대적으로 적은 오버 헤드로 노드를 찾는 매우 효율적인 방법을 제공합니다. 다시 말하지만, CLRS가 어떻게 사용되는지 읽어보기 위해 CLRS를 살펴 보는 것이 좋습니다.
BST는 명시 적으로 사용되지 않을 수 있지만 일반적으로 트리 사용의 한 가지 예는 거의 모든 최신 RDBMS에 있습니다. 마찬가지로 파일 시스템은 일종의 트리 구조로 거의 확실하게 표시되며 파일도 마찬가지로 색인화됩니다. 나무는 Google을 강화합니다. 나무는 인터넷의 거의 모든 웹 사이트를 강화합니다.
"그러면 프로그래밍 중에 수행하는 일반적인 작업 중 일부에서 바이너리 트리를 유용하게 만드는 것은 무엇입니까?"라는 질문 만 다루고 싶습니다.
이것은 많은 사람들이 동의하지 않는 큰 주제입니다. 일부는 이진 검색 트리 및 방향성 그래프와 같은 CS 학위에서 가르치는 알고리즘이 일상적인 프로그래밍에 사용되지 않으므로 관련성이 없다고 말합니다. 다른 사람들은 이러한 알고리즘과 데이터 구조가 우리의 모든 프로그래밍의 기초이며 스스로 작성하지 않아도된다고하더라도이를 이해하는 것이 필수적이라고 말하면서 동의하지 않습니다. 이는 좋은 면접 및 채용 관행에 대한 대화로 필터링됩니다. 예를 들어, Steve Yegge 는 이 질문을 다루는 Google 인터뷰 기사를 가지고 있습니다. 이 논쟁을 기억하십시오. 경험 많은 사람들은 동의하지 않습니다.
일반적인 비즈니스 프로그래밍에서는 이진 트리 또는 트리를 아주 자주 만들 필요가 없을 수 있습니다. 그러나 내부적으로 트리를 사용하여 작동하는 많은 클래스를 사용합니다. 모든 언어의 많은 핵심 조직 클래스는 트리와 해시를 사용하여 데이터를 저장하고 액세스합니다.
더 높은 성과를 내거나 비즈니스 프로그래밍의 규범을 벗어난 상황에 참여한다면 나무가 즉각적인 친구가 될 것입니다. 다른 포스터가 말했듯이 트리는 모든 종류의 데이터베이스 및 인덱스에 대한 핵심 데이터 구조입니다. 데이터 마이닝 및 시각화, 고급 그래픽 (2d 및 3d) 및 기타 여러 계산 문제에 유용합니다.
3D 그래픽에서 BSP (이진 공간 분할) 트리 형태의 이진 트리를 사용했습니다 . 현재 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가 더 나은 솔루션이 될 수 있습니다.
트리의 order 속성은 순서대로, 깊이 우선, 너비 우선, 사전 주문, 사후 주문 등 여러 가지 순서가 지정된 반복 기능을 제공합니다. 이러한 반복 알고리즘은 조회하려는 경우 다른 상황에서 유용합니다.
빨강 검정 트리는 언어 라이브러리, C ++ Set 및 Map, .NET SortedDictionary, Java TreeSet 등의 거의 모든 순서가 지정된 컨테이너에서 내부적으로 사용됩니다.
그래서 나무는 매우 유용하며 당신은 그것을 알지도 못하는 사이에 아주 자주 사용할 수 있습니다. 내가 흥미로운 프로그래밍 실습으로 적극 권장하지만 직접 작성할 필요 는 없을 것입니다 .
Red Black Tree 및 B-tree는 모든 종류의 영구 저장소에 사용됩니다. 나무가 균형을 이루기 때문에 폭과 깊이 순회 성능이 완화됩니다.
거의 모든 최신 데이터베이스 시스템은 데이터 저장을 위해 트리를 사용합니다.
BST는 Micheal이 말한 것처럼 세상을 돌아 다니게합니다. 구현할 좋은 트리를 찾고 있다면 AVL 트리 (Wikipedia)를 살펴보십시오 . 밸런싱 조건이 있으므로 O (logn)가 보장됩니다. 이러한 종류의 검색 효율성은 모든 종류의 인덱싱 프로세스에 적용하는 것이 논리적입니다. 더 효율적일 수있는 유일한 것은 해싱 함수일 것입니다. 그러나 그것들은 추악하고 빠르며 서둘러집니다. 또한, 당신은 생일 역설 (비둘기 구멍 문제라고도 함)에 직면합니다.
어떤 교과서를 사용하고 있습니까? 우리가 사용하는 자바 데이터 구조 및 분석을 마크 앨런 와이즈에 의해. 나는 이것을 입력 할 때 실제로 내 무릎에 열려 있습니다. 여기에는 Red-Black 트리에 대한 훌륭한 섹션이 있으며, 언급하는 모든 트리를 구현하는 데 필요한 코드도 포함되어 있습니다.
빨강-검정 나무는 균형을 유지하므로 항목을 꺼내기 위해 깊이 이동하지 않아도됩니다. 절약 된 시간은 WORST의 경우 RB 트리를 O (log () n))로 만드는 반면, 불운 한 이진 트리는 lop sided 구성에 들어가 O (n)에서 검색을 나쁜 경우로 만들 수 있습니다. 이것은 실제로 또는 임의의 데이터에서 발생합니다. 따라서 시간이 중요한 코드 (데이터베이스 검색, 네트워크 서버 등)가 필요한 경우 RB 트리를 사용하여 정렬되거나 정렬되지 않은 목록 / 세트를 지원합니다.
그러나 RBTrees는 멍청이를위한 것입니다! AI를 수행하고 검색을 수행해야하는 경우 상태 정보를 많이 분기합니다. O (log (n))에서 새로운 상태를 포크하기 위해 지속적인 레드-블랙을 사용할 수 있습니다. 영구 빨강 검정 트리는 형태 적 작업 (삽입 / 삭제) 전후에 트리의 복사본을 유지하지만 전체 트리를 복사하지 않습니다 (일반적으로 O (log (n)) 작업). 나는 자바에 대한 영구 레드-블랙 트리를 오픈 소스했습니다.
내가 본 빨강-검정 나무에 대한 가장 좋은 설명은 Cormen, Leisersen 및 Rivest의 '알고리즘 소개'에있는 것입니다. 부분적으로 구현할만큼 충분히 이해할 수있었습니다 (삽입 만 해당). 또한 프로세스를 애니메이션화하고 트리 구조를 구축하는 알고리즘의 그래픽 표현을 살펴보고 단계별로 진행할 수있는 다양한 웹 페이지에 This One 과 같은 애플릿이 많이 있습니다 .
사람들이 어떤 나무를 사용하는지 묻기 때문에 Red Black 나무는 기본적으로 2-3-4 B- 트리 (즉, 순서 4의 B- 트리)라는 것을 알아야합니다. B- 트리는 이진 트리 (질문에서 질문 한대로)와 동일 하지 않습니다 .
다음 은 나중에 RBTree로 진화 한 대칭 이진 B- 트리로 알려진 초기 추상화를 설명하는 훌륭한 리소스입니다. 이해하기 전에 B- 트리를 잘 파악해야합니다. 요약하면 : Red Black 트리의 'red'링크는 B- 트리 노드 (키 범위 내의 값)의 일부인 노드를 나타내는 방법 인 반면 'black'링크는 B에서 수직으로 연결된 노드입니다. -나무.
따라서 다음은 B- 트리 측면에서 Red Black 트리의 규칙을 변환 할 때 얻을 수있는 것입니다 ( Red Black tree rule => B Tree equivalent 형식을 사용하고 있습니다 ).
1) 노드는 빨간색 또는 검은 색입니다. => b- 트리의 노드는 노드의 일부이거나 새 레벨의 노드가 될 수 있습니다.
2) The root is black. (This rule is sometimes omitted, since it doesn't affect analysis) => The root node can be thought of either as a part of an internal root node as a child of an imaginary parent node.
3) All leaves (NIL) are black. (All leaves are same color as the root.) => Since one way of representing a RB tree is by omitting the leaves, we can rule this out.
4)Both children of every red node are black. => The children of an internal node in a B-tree always lie on another level.
5)Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. => A B-tree is kept balanced as it requires that all leaf nodes are at the same depth (Hence the height of a B-tree node is represented by the number of black links from the root to the leaf of a Red Black tree)
Also, there's a simpler 'non-standard' implementation by Robert Sedgewick here: (He's the author of the book Algorithms along with Wayne)
Lots and lots of heat here, but not much light, so lets see if we can provide some.
First, a RB tree is an associative data structure, unlike, say an array, which cannot take a key and return an associated value, well, unless that's an integer "key" in a 0% sparse index of contiguous integers. An array cannot grow in size either (yes, I know about realloc() too, but under the covers that requires a new array and then a memcpy()), so if you have either of these requirements, an array won't do. An array's memory efficiency is perfect. Zero waste, but not very smart, or flexible - realloc() not withstanding.
Second, in contrast to a bsearch() on an array of elements, which IS an associative data structure, a RB tree can grow (AND shrink) itself in size dynamically. The bsearch() works fine for indexing a data structure of a known size, which will remain that size. So if you don't know the size of your data in advance, or new elements need to be added, or deleted, a bsearch() is out. Bsearch() and qsort() are both well supported in classic C, and have good memory efficiency, but are not dynamic enough for many applications. They are my personal favorite though because they're quick, easy, and if you're not dealing with real-time apps, quite often are flexible enough. In addition, in C/C++ you can sort an array of pointers to data records, pointing to the struc{} member, for example, you wish to compare, and then rearranging the pointer in the pointer array such that reading the pointers in order at the end of the pointer sort yields your data in sorted order. Using this with memory-mapped data files is extremely memory efficient, fast, and fairly easy. All you need to do is add a few "*"s to your compare function/s.
Third, in contrast to a hashtable, which also must be a fixed size, and cannot be grown once filled, a RB tree will automagically grow itself and balance itself to maintain its O(log(n)) performance guarantee. Especially if the RB tree's key is an int, it can be faster than a hash, because even though a hashtable's complexity is O(1), that 1 can be a very expensive hash calculation. A tree's multiple 1-clock integer compares often outperform 100-clock+ hash calculations, to say nothing of rehashing, and malloc()ing space for hash collisions and rehashes. Finally, if you want ISAM access, as well as key access to your data, a hash is ruled out, as there is no ordering of the data inherent in the hashtable, in contrast to the natural ordering of data in any tree implementation. The classic use for a hash table is to provide keyed access to a table of reserved words for a compiler. It's memory efficiency is excellent.
Fourth, and very low on any list, is the linked, or doubly-linked list, which, in contrast to an array, naturally supports element insertions and deletions, and as that implies, resizing. It's the slowest of all the data structures, as each element only knows how to get to the next element, so you have to search, on average, (element_knt/2) links to find your datum. It is mostly used where insertions and deletions somewhere in the middle of the list are common, and especially, where the list is circular and feeds an expensive process which makes the time to read the links relatively small. My general RX is to use an arbitrarily large array instead of a linked list if your only requirement is that it be able to increase in size. If you run out of size with an array, you can realloc() a larger array. The STL does this for you "under the covers" when you use a vector. Crude, but potentially 1,000s of times faster if you don't need insertions, deletions or keyed lookups. It's memory efficiency is poor, especially for doubly-linked lists. In fact, a doubly-linked list, requiring two pointers, is exactly as memory inefficient as a red-black tree while having NONE of its appealing fast, ordered retrieval characteristics.
Fifth, trees support many additional operations on their sorted data than any other data structure. For example, many database queries make use of the fact that a range of leaf values can be easily specified by specifying their common parent, and then focusing subsequent processing on the part of the tree that parent "owns". The potential for multi-threading offered by this approach should be obvious, as only a small region of the tree needs to be locked - namely, only the nodes the parent owns, and the parent itself.
In short, trees are the Cadillac of data structures. You pay a high price in terms of memory used, but you get a completely self-maintaining data structure. This is why, as pointed out in other replies here, transaction databases use trees almost exclusively.
If you would like to see how a Red-Black tree is supposed to look graphically, I have coded an implementation of a Red-Black tree that you can download here
IME, almost no one understands the RB tree algorithm. People can repeat the rules back to you, but they don't understand why those rules and where they come from. I am no exception :-)
For this reason, I prefer the AVL algorithm, because it's easy to comprehend. Once you understand it, you can then code it up from scratch, because it make sense to you.
Trees can be fast. If you have a million nodes in a balanced binary tree, it takes twenty comparisons on average to find any one item. If you have a million nodes in a linked list, it takes five hundred thousands comparisons on average to find the same item.
If the tree is unbalanced, though, it can be just as slow as a list, and also take more memory to store. Imagine a tree where most nodes have a right child, but no left child; it is a list, but you still have to hold memory space to put in the left node if one shows up.
Anyways, the AVL tree was the first balanced binary tree algorithm, and the Wikipedia article on it is pretty clear. The Wikipedia article on red-black trees is clear as mud, honestly.
Beyond binary trees, B-Trees are trees where each node can have many values. B-Tree is not a binary tree, just happens to be the name of it. They're really useful for utilizing memory efficiently; each node of the tree can be sized to fit in one block of memory, so that you're not (slowly) going and finding tons of different things in memory that was paged to disk. Here's a phenomenal example of the B-Tree.
ReferenceURL : https://stackoverflow.com/questions/20734/red-black-trees
'programing' 카테고리의 다른 글
| MVC Core 모든 작업에 대해 전역 인증을 강제 / 설정하는 방법은 무엇입니까? (0) | 2021.01.14 |
|---|---|
| 각도 CLI를 사용하여 특정 버전의 각도 설치 (0) | 2021.01.14 |
| mysql 테이블 열 기본값을 어떻게 변경합니까? (0) | 2021.01.14 |
| 두 가지 요소 중 하나가 있으면 무언가를하십시오. (0) | 2021.01.14 |
| PHP에서 헤더 ( 'Location ..')를 통해 리디렉션 후 'exit'를 호출해야하는 이유는 무엇입니까? (0) | 2021.01.14 |