AVL trees and the breadth of their application
Decided to describe in my opinion the most useful tree structure. AVL tree is a binary tree (each vertex is not more than 2 sons) in which each vertex has an identifier (and keeps the tree), identifiers obey the following rule: the left son ID<ID of the parent<ID right son.
Ie if you traverse a tree recursively from left to right will get sorted in ascending order the list of ID from right to left in descending order.
Moreover, the wood is balanced: the height of the left subtree differs from the height right high for 1.
I wonder what it means then to check existence of element in the tree takes log(N) N – number ID. It is necessary to go from the root down, and because the tree is maximally symmetric then its height is log(N)+1
The good news is that we're allowed to attach to the top any more useful data and then selection of arbitrary data by ID will take log(N) time.
The bad news is the same ID as follows from the definition it can not exist. Will have to make a feint ears, one way to do is for each vertex a list of vertices with the same ID, the other is to change the balancing algorithm.
Another property – you can quickly locate the elements of the array closest to the given one, but less of it, or more – for some tasks is very important.
I wonder this: obviously such a tree from a list of IDs to build, but also, it turns out that it is possible to quickly add and quickly remove items in a very short time <= log(N) (added)
Thus, to sort an array of N elements you can just add in the tree is N*log(N) and then around from left to right – i.e. N total time N*log(N) – and we made another very quick sort method of the array
By the way several transactions for convenience – since we are quickly looking for a vertex with the desired ID, then do the operations Set and Get to modify DATA in the top. Therefore, the update data corresponding to the specified ID in memory, we do the same for <=log(N)
I use an AVL tree is very often even in the standard hash CRC I store the CRC group in the tree, sorted arrays and lists, using to check for the existence of elements in the array, store the indices of the database, sorted search results (as described above), in the end, it is even possible to directly write to a file and to read for even more acceleration.
In General, this structure is not much more than a list, and allows you to make hundreds of times more operations, i.e. a good alternative to the 1-2 contact list.
Now a bit about how to add a tree full of descriptions very much in the public domain, so briefly:
We introduce in each node the number of balance which indicates which of the subtrees above – left or right.
When adding vertices to the tree it sometimes becomes not balanced. The adding procedure is simple – descend the tree to the bottom, using the rule
ID left son<ID of the parent<ID right son, i.e. if a new ID < ID tops go left, otherwise right. Adding son to the vertex, we must update the balance indicator out of our way which we were going – can do it in the course of descent, you can walk back up – if you come from the left subtree then the balance-- otherwise balance++
If on some level we have got the balance=0, then the subtree is balanced and you can finish the addition (the entire tree at the top shouldn't be counted as the height of subtree has not changed – it was balance=-1 became 0 and the left subtree prevailed, added to the right and aligned, or balance=1 is 0 right subtree prevailed, added to the left and leveled)
Well, the most interesting is the balancing of the subtree if at some step on the way back we got the balance=-2 or 2, it means that one half of the tree outweighed heavily and need to make a turn raise by 1 unit, for example, right and left extend. A whole turn is just to check the conditions and the repositioning of the links, I personally understood it for yourself on a piece of paper – it is possible to only have 3 options, and what you suggest for the best awareness – I will be here to paint with words what you can draw, and if you are really lazy, you to find in the Internet ready solutions.
Full contents and list of my articles on search engine will be updated here: http://habrahabr.ru/blogs/search_engines/123671/
Article based on information from habrahabr.ru
Ie if you traverse a tree recursively from left to right will get sorted in ascending order the list of ID from right to left in descending order.
Moreover, the wood is balanced: the height of the left subtree differs from the height right high for 1.
I wonder what it means then to check existence of element in the tree takes log(N) N – number ID. It is necessary to go from the root down, and because the tree is maximally symmetric then its height is log(N)+1
The good news is that we're allowed to attach to the top any more useful data and then selection of arbitrary data by ID will take log(N) time.
The bad news is the same ID as follows from the definition it can not exist. Will have to make a feint ears, one way to do is for each vertex a list of vertices with the same ID, the other is to change the balancing algorithm.
Another property – you can quickly locate the elements of the array closest to the given one, but less of it, or more – for some tasks is very important.
I wonder this: obviously such a tree from a list of IDs to build, but also, it turns out that it is possible to quickly add and quickly remove items in a very short time <= log(N) (added)
Thus, to sort an array of N elements you can just add in the tree is N*log(N) and then around from left to right – i.e. N total time N*log(N) – and we made another very quick sort method of the array
By the way several transactions for convenience – since we are quickly looking for a vertex with the desired ID, then do the operations Set and Get to modify DATA in the top. Therefore, the update data corresponding to the specified ID in memory, we do the same for <=log(N)
I use an AVL tree is very often even in the standard hash CRC I store the CRC group in the tree, sorted arrays and lists, using to check for the existence of elements in the array, store the indices of the database, sorted search results (as described above), in the end, it is even possible to directly write to a file and to read for even more acceleration.
In General, this structure is not much more than a list, and allows you to make hundreds of times more operations, i.e. a good alternative to the 1-2 contact list.
Now a bit about how to add a tree full of descriptions very much in the public domain, so briefly:
We introduce in each node the number of balance which indicates which of the subtrees above – left or right.
When adding vertices to the tree it sometimes becomes not balanced. The adding procedure is simple – descend the tree to the bottom, using the rule
ID left son<ID of the parent<ID right son, i.e. if a new ID < ID tops go left, otherwise right. Adding son to the vertex, we must update the balance indicator out of our way which we were going – can do it in the course of descent, you can walk back up – if you come from the left subtree then the balance-- otherwise balance++
If on some level we have got the balance=0, then the subtree is balanced and you can finish the addition (the entire tree at the top shouldn't be counted as the height of subtree has not changed – it was balance=-1 became 0 and the left subtree prevailed, added to the right and aligned, or balance=1 is 0 right subtree prevailed, added to the left and leveled)
Well, the most interesting is the balancing of the subtree if at some step on the way back we got the balance=-2 or 2, it means that one half of the tree outweighed heavily and need to make a turn raise by 1 unit, for example, right and left extend. A whole turn is just to check the conditions and the repositioning of the links, I personally understood it for yourself on a piece of paper – it is possible to only have 3 options, and what you suggest for the best awareness – I will be here to paint with words what you can draw, and if you are really lazy, you to find in the Internet ready solutions.
Full contents and list of my articles on search engine will be updated here: http://habrahabr.ru/blogs/search_engines/123671/
Комментарии
Отправить комментарий