이진 트리의 응용 프로그램은 무엇입니까?
이진 트리의 특정 응용 프로그램이 무엇인지 궁금합니다. 실제 사례를 제시해 주시겠습니까?
이진 트리 의 성능에 대한 논쟁 은 의미가 없습니다. 데이터 구조가 아니라 성능 특성이 다른 데이터 구조 패밀리입니다. 이 것은 사실이지만 불균형 이진 나무 보다 훨씬 더 수행 자체 균형 이진 트리 검색을위한 많은 이진 트리가 있습니다 (예 : 바이너리 시도 등) 하는 "균형" 아무 의미가 없습니다.
이진 트리의 응용
- 이진 검색 트리 - 여러 언어 라이브러리의 객체 및 객체 와 같이 데이터가 지속적으로 들어오고 나가는 많은 검색 응용 프로그램에서 사용됩니다 .
mapset - 이진 공간 파티션 -거의 모든 3D 비디오 게임에서 렌더링 할 객체를 결정하는 데 사용됩니다.
- 이진 시도 -라우터 테이블을 저장하기 위해 거의 모든 고 대역폭 라우터에서 사용됩니다.
- 해시 트리 -p2p 프로그램 및 해시를 확인해야하는 특수 이미지 서명에 사용되지만 전체 파일을 사용할 수는 없습니다.
- 힙 -효율적인 우선 순위 큐를 구현하는 데 사용되며, 여러 운영 체제의 프로세스 스케줄링, 라우터의 서비스 품질 및 A * (로봇 및 비디오 게임을 포함한 AI 애플리케이션에 사용되는 경로 찾기 알고리즘)에 사용됩니다. . 힙 정렬에서도 사용됩니다.
- 허프만 코딩 트리 ( Chip Uni )-.jpeg 및 .mp3 파일 형식에서 사용하는 것과 같은 압축 알고리즘에 사용됩니다.
- GGM 트리 -의사 난수 트리를 생성하기 위해 암호화 응용 프로그램에서 사용됩니다.
- 구문 트리 -표현식을 구문 분석하기 위해 컴파일러 및 (암시 적으로) 계산기로 구성됩니다.
- Treap- 무선 네트워킹 및 메모리 할당에 사용되는 무작위 데이터 구조.
- T- 트리 -대부분의 데이터베이스는 드라이브에 데이터를 저장하기 위해 특정 형태의 B- 트리를 사용하지만, 대부분의 데이터를 메모리에 유지하는 데이터베이스는 종종 T- 트리를 사용합니다.
이진 트리가 검색을 위해 n-ary 트리보다 자주 사용되는 이유는 n-ary 트리가 더 복잡하지만 일반적으로 실제 속도 이점이 없기 때문입니다.
m노드가 있는 (균형) 이진 트리 에서 한 레벨에서 다음 레벨로 이동하려면 한 번의 비교가 필요 log_2(m)하며 총 log_2(m)비교를 위해 레벨 이 있습니다 .
반대로, n-ary 트리는 다음 레벨로 이동하기 위해 log_2(n)비교 (바이너리 검색 사용) 가 필요 합니다. 이 때문에 log_n(m)총 수준의 검색이 필요합니다 log_2(n)*log_n(m)= log_2(m)비교는 총. 따라서 n-ary 트리는 더 복잡하지만 필요한 전체 비교 측면에서 이점이 없습니다.
그러나 n-ary 트리는 여전히 틈새 상황에 유용합니다. 즉시 떠오르는 예는 쿼드 트리 및 기타 공간 분할 트리입니다. 여기서 레벨 당 두 개의 노드 만 사용하여 공간을 분할하면 논리가 불필요하게 복잡해집니다. 제한 수준이 각 수준에서 수행되는 비교 횟수가 아니라 하드 드라이브에서 한 번에로드 할 수있는 노드 수인 많은 데이터베이스에서 사용되는 B- 트리 )
대부분의 사람들이 이진 트리에 대해 이야기 할 때, 이진 검색 트리 에 대해 생각하지 않는 것보다 더 흔하기 때문에 먼저 다룰 것입니다.
불균형 이진 검색 트리는 실제로 학생들에게 데이터 구조에 대해 교육하는 것 이상으로 유용합니다. 데이터가 비교적 임의의 순서로 나오지 않는 한 단순한 이진 트리의 균형 이 맞지 않기 때문에 트리가 최악의 형태로 쉽게 변질 될 수 있기 때문 입니다.
좋은 사례 : 한 번은 조작 및 검색을 위해 데이터를 이진 트리에로드 한 일부 소프트웨어를 수정해야했습니다. 데이터를 정렬 된 형식으로 작성했습니다.
Alice
Bob
Chloe
David
Edwina
Frank
다시 읽을 때 다음 트리로 끝났습니다.
Alice
/ \
= Bob
/ \
= Chloe
/ \
= David
/ \
= Edwina
/ \
= Frank
/ \
= =
이것은 퇴화 형태입니다. 해당 트리에서 Frank를 찾으면 6 개의 노드를 모두 검색해야 찾을 수 있습니다.
이진 트리는 균형을 잡을 때 검색에 정말 유용합니다. 여기에는 루트 노드를 통해 하위 트리를 회전하여 두 하위 트리 사이의 높이 차이가 1보다 작거나 같아야합니다. 한 번에 하나씩 위의 이름을 균형 트리에 추가하면 다음과 같은 시퀀스가 제공됩니다.
1. Alice
/ \
= =
2. Alice
/ \
= Bob
/ \
= =
3. Bob
_/ \_
Alice Chloe
/ \ / \
= = = =
4. Bob
_/ \_
Alice Chloe
/ \ / \
= = = David
/ \
= =
5. Bob
____/ \____
Alice David
/ \ / \
= = Chloe Edwina
/ \ / \
= = = =
6. Chloe
___/ \___
Bob Edwina
/ \ / \
Alice = David Frank
/ \ / \ / \
= = = = = =
항목이 추가됨에 따라 전체 하위 트리가 왼쪽으로 회전하는 것을 볼 수 있습니다 (3 단계와 6 단계 O(log N)에서 O(N). 어느 시점에서도 가장 높은 NULL ( =)은 둘 이상의 레벨만큼 가장 낮은 것과 다릅니다. 그리고, 위의 최종 트리에, 당신은 (세 개의 노드를보고 프랭크을 찾을 수 있습니다 Chloe, Edwina마지막으로하고 Frank).
물론, 이진 머릿단이 아닌 균형 잡힌 멀티 웨이 트리 를 만들 때 더욱 유용 할 수 있습니다 . 이는 각 노드가 하나 이상의 항목을 보유 함을 의미합니다 (기술적으로 N 항목과 N + 1 포인터를 보유합니다. 이진 트리는 1 항목과 2 포인터가있는 단방향 다중 경로 트리의 특별한 경우입니다).
3 방향 트리를 사용하면 다음과 같이 끝납니다.
Alice Bob Chloe
/ | | \
= = = David Edwina Frank
/ | | \
= = = =
일반적으로 항목 인덱스의 키를 유지 관리하는 데 사용됩니다. 노드가 정확히 디스크 블록 크기 (예 : 512 바이트) 인 하드웨어에 최적화 된 데이터베이스 소프트웨어를 작성했으며 단일 노드에 가능한 많은 키를 넣었습니다. 포인터 이 경우 실제로 인덱스 파일에서 별도의 고정 길이 레코드 직접 액세스 파일에 기록 수 있었다 (그래서 레코드 번호는 X단지에 추구로 볼 수 있습니다 X * record_length).
예를 들어 포인터가 4 바이트이고 키 크기가 10 인 경우 512 바이트 노드의 키 수는 36 개입니다. 총 36 개의 키 (360 바이트)와 37 개의 포인터 (148 바이트)는 총 508 바이트입니다. 노드 당 4 바이트가 낭비됩니다.
다 방향 키를 사용하면 2 단계 검색 (노드에서 올바른 키를 찾기 위해 작은 순차적 (또는 선형 이진) 검색과 결합 된 올바른 노드를 찾기위한 다 방향 검색)의 복잡성이 발생하지만 장점은 다음과 같습니다. 이보다 더 적은 디스크 I / O를 수행합니다.
메모리 내 구조 에서이 작업을 수행 할 이유가 없습니다. 균형 이진 트리를 고수하고 코드를 간단하게 유지하는 것이 좋습니다.
또한 데이터 세트가 작을 때 O(log N)오버 의 장점이 O(N)실제로 나타나지는 않습니다. 주소록에 15 명을 저장하기 위해 다 방향 트리를 사용하는 경우 아마 과잉 일 수 있습니다. 지난 10 년 동안 수십만 고객의 모든 주문과 같은 것을 저장할 때 장점이 있습니다.
big-O 표기법의 요점은 N무한대 에 접근 할 때 발생하는 상황을 나타내는 것 입니다. 어떤 사람들은 동의하지 않을 수도 있지만 데이터 세트가 특정 크기 이하로 유지되는 것이 확실하다면 다른 방법으로 거품 정렬을 사용하는 것이 좋습니다 :-)
이진 트리의 다른 용도와 관련하여 다음과 같은 많은 것들이 있습니다.
- 높은 키가 왼쪽 (또는 아래 또는 오른쪽 및 오른쪽)이 아닌 낮은 키보다 높 거나 같은 이진 힙 .
- 해시 테이블과 유사한 해시 트리;
- 컴퓨터 언어 컴파일을위한 추상 구문 트리;
- 데이터 압축을위한 허프만 트리;
- 네트워크 트래픽을위한 라우팅 트리.
검색 트리에 대해 생성 한 설명이 많으면 다른 것에 대해 자세하게 설명하고 싶지만 원하는 경우 조사하기에 충분해야합니다.
의 조직 모스 부호는 이진 트리입니다.
이진 트리는 각 노드에 최대 두 개의 자식 노드가 있으며 일반적으로 "왼쪽"과 "오른쪽"으로 구분되는 트리 데이터 구조입니다. 자식이있는 노드는 부모 노드이며 자식 노드는 부모에 대한 참조를 포함 할 수 있습니다. 트리 외부에서 "루트"노드 (모든 노드의 조상)에 대한 참조가있는 경우가 종종 있습니다. 데이터 구조의 모든 노드는 루트 노드에서 시작하여 왼쪽 또는 오른쪽 자식에 대한 참조를 반복하여 도달 할 수 있습니다. 이진 트리에서 모든 노드의 정도는 최대 2입니다.
이진 트리는 그림에서 볼 수 있듯이 트리에서 노드를 찾으려면 최대 6 회만 보이기 때문에 유용합니다. 예를 들어 노드 24를 검색하려면 루트에서 시작합니다.
- 루트의 값은 31이며 24보다 큽니다. 따라서 왼쪽 노드로 이동합니다.
- 왼쪽 노드의 값은 15이며 24보다 작으므로 오른쪽 노드로 이동합니다.
- 오른쪽 노드의 값은 23이며 24보다 작으므로 오른쪽 노드로 이동합니다.
- 오른쪽 노드의 값은 27이며 24보다 큽니다. 따라서 왼쪽 노드로 이동합니다.
- 왼쪽 노드의 값은 25보다 큰 24이므로 왼쪽 노드로 이동합니다.
- 노드의 값은 24이며 이는 우리가 찾고있는 핵심입니다.
이 검색은 다음과 같습니다. 
첫 번째 패스에서 전체 트리 노드의 절반을 제외 할 수 있음을 알 수 있습니다. 왼쪽 하위 트리의 절반은 두 번째입니다. 이것은 매우 효과적인 검색을 만듭니다. 이 작업이 40 억 개의 요소에서 수행 된 경우 최대 32 회만 검색하면됩니다. 따라서 트리에 포함 된 요소가 많을수록 검색 효율이 높아집니다.
삭제가 복잡해질 수 있습니다. 노드에 0 또는 1 개의 자식이있는 경우 삭제하려는 포인터를 제외하기 위해 일부 포인터를 이동하면됩니다. 그러나 자식이 2 개인 노드는 쉽게 삭제할 수 없습니다. 그래서 우리는 지름길을 취합니다. 노드 19를 삭제하려고한다고 가정하겠습니다.
왼쪽 및 오른쪽 포인터를 어디로 옮길 지 결정하는 것이 쉽지 않기 때문에 대체 포인터를 찾습니다. 왼쪽 하위 트리로 가서 가능한 한 오른쪽으로갑니다. 이것은 우리가 삭제할 노드의 다음으로 큰 값을 제공합니다.
이제 왼쪽 및 오른쪽 포인터를 제외한 18 개의 내용을 모두 복사하고 원래 18 개의 노드를 삭제합니다.
이러한 이미지를 만들기 위해 자체 균형 트리 인 AVL 트리를 구현하여 언제든지 트리가 리프 노드 (자식이없는 노드)간에 최대 한 수준의 차이를 갖도록합니다. 이렇게하면 O(log n)삽입 및 삭제에 약간의 시간이 소요 되므로 트리가 기울어지지 않고 최대 검색 시간이 유지 됩니다.
다음은 내 AVL 트리가 가능한 작고 균형을 유지 한 방법을 보여주는 샘플입니다.
In a sorted array, lookups would still take O(log(n)), just like a tree, but random insertion and removal would take O(n) instead of the tree's O(log(n)). Some STL containers use these performance characteristics to their advantage so insertion and removal times take a maximum of O(log n), which is very fast. Some of these containers are map, multimap, set, and multiset.
Example code for an AVL tree can be found at http://ideone.com/MheW8
The main application is binary search trees. These are a data structure in which searching, insertion, and removal are all very fast (about log(n) operations)
- Binary trees are used in Huffman coding, which are used as a compression code.
- Binary trees are used in Binary search trees, which are useful for maintaining records of data without much extra space.
One interesting example of a binary tree that hasn't been mentioned is that of a recursively evaluated mathematical expression. It's basically useless from a practical standpoint, but it is an interesting way to think of such expressions.
Basically each node of the tree has a value that is either inherent to itself or is evaluated by recursively by operating on the values of its children.
For example, the expression (1+3)*2 can be expressed as:
*
/ \
+ 2
/ \
1 3
To evaluate the expression, we ask for the value of the parent. This node in turn gets its values from its children, a plus operator and a node that simply contains '2'. The plus operator in turn gets its values from children with values '1' and '3' and adds them, returning 4 to the multiplication node which returns 8.
This use of a binary tree is akin to reverse polish notation in a sense, in that the order in which operations are performed is identical. Also one thing to note is that it doesn't necessarily have to be a binary tree, it's just that most commonly used operators are binary. At its most basic level, the binary tree here is in fact just a very simple purely functional programming language.
Applications of Binary tree:
- Implementing routing table in router.
- Data compression code
- Implementation of Expression parsers and expression solvers
- To solve database problem such as indexing.
- Expression evaluation
I dont think there is any use for "pure" binary trees. (except for educational purposes) Balanced binary trees, such as Red-Black trees or AVL trees are much more useful, because they guarantee O(logn) operations. Normal binary trees may end up being a list (or almost list) and are not really useful in applications using much data.
Balanced trees are often used for implementing maps or sets. They can also be used for sorting in O(nlogn), even tho there exist better ways to do it.
Also for searching/inserting/deleting Hash tables can be used, which usually have better performance than binary search trees (balanced or not).
An application where (balanced) binary search trees would be useful would be if searching/inserting/deleting and sorting would be needed. Sort could be in-place (almost, ignoring the stack space needed for the recursion), given a ready build balanced tree. It still would be O(nlogn) but with a smaller constant factor and no extra space needed (except for the new array, assuming the data has to be put into an array). Hash tables on the other hand can not be sorted (at least not directly).
Maybe they are also useful in some sophisticated algorithms for doing something, but tbh nothing comes to my mind. If i find more i will edit my post.
Other trees like f.e. B+trees are widely used in databases
One of the most common application is to efficiently store data in sorted form in order to access and search stored elements quickly. For instance, std::map or std::set in C++ Standard Library.
Binary tree as data structure is useful for various implementations of expression parsers and expression solvers.
It may also be used to solve some of database problems, for example, indexing.
Generally, binary tree is a general concept of particular tree-based data structure and various specific types of binary trees can be constructed with different properties.
In C++ STL, and many other standard libraries in other languages, like Java and C#. Binary search trees are used to implement set and map.
One of the most important application of binary trees are balanced binary search trees like:
These type of trees have the property that the difference in heights of left subtree and right subtree is maintained small by doing operations like rotations each time a node is inserted or deleted.
Due to this, the overall height of the tree remains of the order of log n and the operations such as search, insertion and deletion of the nodes are performed in O(log n) time. The STL of C++ also implements these trees in the form of sets and maps.
They can be used as a quick way to sort data. Insert data into a binary search tree at O(log(n)). Then traverse the tree in order to sort them.
your programs syntax, or for that matter many other things such as natural languages can be parsed using binary tree (though not necessarily).
Implementations of java.util.Set
On modern hardware, a binary tree is nearly always suboptimal due to bad cache and space behaviour. This also goes for the (semi)balanced variants. If you find them, it is where performance doesn't count (or is dominated by the compare function), or more likely for historic or ignorance reasons.
AST를 표현하기 위해 이진 트리를 사용하는 컴파일러는 postorder, inorder와 같이 트리를 구문 분석하기 위해 알려진 알고리즘을 사용할 수 있습니다. 프로그래머는 자체 알고리즘을 생각 해낼 필요가 없습니다. 소스 파일의 이진 트리가 n-ary 트리보다 높기 때문에 빌드하는 데 시간이 더 걸립니다. selstmnt : = "if" "("expr ")"stmnt "ELSE"stmnt 이진 트리에는 3 레벨의 노드가 있지만 n-ary 트리의 레벨은 1입니다 (chids).
그렇기 때문에 Unix 기반 OS가 느립니다.
참고 URL : https://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees
'Programing' 카테고리의 다른 글
| 'performance_schema.session_variables'테이블이 존재하지 않습니다 (0) | 2020.03.18 |
|---|---|
| 안드로이드의 목적은 무엇입니까 (0) | 2020.03.18 |
| OS X에서 NODE_ENV를 생산 / 개발로 설정하는 방법 (0) | 2020.03.18 |
| DateTime을 VarChar로 변환하는 방법 (0) | 2020.03.18 |
| 게터와 세터를 사용하는 파이썬적인 방법은 무엇입니까? (0) | 2020.03.18 |