AVL trees and their breadth
I decided to describe a little in my opinion the most useful tree structure. AVL tree is a binary tree (each vertex has no more than 2 sons) in which an identifier is assigned to each vertex (it is the tree that stores it), identifiers follow the following rule: ID of the left son <parent ID <ID of the right son.
Those. if you go around the tree recursively from left to right, we get a list of ID sorted in ascending order, from right to left - in descending order.
And the tree is as balanced as possible: the height of the left subtree differs from the height of the right one by a maximum of 1.
It is interesting in him that then to check the existence of an element in the tree goes log (N) N - the number of ID. After all, it is necessary to go down from the root, and since the tree is as symmetrical as possible, its height is log (N) +1
The good news is that no one forbids us to attach any more useful data to the top, and then sampling arbitrary data by ID will take log (N) time
The bad news is that the same ID as it follows from the definition cannot exist in it. You have to make a feint with your ears, one way to make a list of vertices with the same ID instead of each vertex, and another to change the balancing algorithm.
Another property is that you can quickly find the elements of an array that are closest to a given one, but less than it, or more - for some tasks it is very important.
The interesting thing is: obviously such a tree from the list of identifiers can be built, but it also turns out that you can quickly add to it and quickly remove elements in a very short time <= log (N) (addition)
')
Thus, to sort an array of N elements, you can simply add it to the tree - N * log (N) and then go around from left to right - N ie total time N * log (N) - and we made another very fast array sorting method
By the way, a few more operations for convenience - since we are quickly looking for a vertex with the desired ID, we will do the Set and Get operations to change the DATA field at the vertex. Thus, we update the data corresponding to the given ID in memory also for <= log (N)
I use the AVL tree very often: even in a standard CRC hash, I store CRC groups in the tree, sort arrays and lists, use to check for the existence of elements in the array, store database indices, sort the search results (as described above), eventually , it can even be directly written to a file and read for even greater acceleration.
In general, this structure is not much larger than the list, but allows you to do hundreds of times more operations, i.e. A good alternative to the 1-2 linked list.
Now it’s a little about how to add to the tree, there are a lot of full descriptions in free access, therefore, briefly:
Let's enter at each vertex the number of balance which shows which of the subtrees is higher - left or right.
When adding a vertex to a tree, it sometimes becomes unbalanced. The procedure for adding is simple - we go down the tree to the bottom, using the rule
ID of the left son <parent ID <ID of the right son, i.e. if the new ID <vertex ID is going to the left, otherwise to the right. Having added a son to the lower peak, we must update the balance indicator in our way that we went - we can do this as we descend, we can walk up and down - if we come from the left subtree, then balance--, otherwise balance ++
If at some level we got balance = 0, then the subtree is balanced and you can finish adding (the whole tree does not need to be recalculated because the height of the subtree has not changed - it was balance = -1 became 0 - the left subtree outweighed, added to the right and aligned, or balance = 1 became 0 - the right subtree outweighed, added to the left and aligned)
Well, the most interesting thing is balancing the subtree if at some step on the way back we got balance = -2 or 2, it means that one half of the tree outweighed strongly, and we need to make a certain turn - to raise by 1 link, for example, the right, and the left to lengthen. The whole turn comes down to checking the conditions and rearranging the links. I personally understood it on a piece of paper for myself - only 3 options are possible, which I advise you for better awareness - I will not specifically write here words that can be drawn, and if it’s too lazy, find in the internet ready-made solutions.
The full content and list of my articles on the search engine will be updated here: http://habrahabr.ru/blogs/search_engines/123671/
Those. if you go around the tree recursively from left to right, we get a list of ID sorted in ascending order, from right to left - in descending order.
And the tree is as balanced as possible: the height of the left subtree differs from the height of the right one by a maximum of 1.
It is interesting in him that then to check the existence of an element in the tree goes log (N) N - the number of ID. After all, it is necessary to go down from the root, and since the tree is as symmetrical as possible, its height is log (N) +1
The good news is that no one forbids us to attach any more useful data to the top, and then sampling arbitrary data by ID will take log (N) time
The bad news is that the same ID as it follows from the definition cannot exist in it. You have to make a feint with your ears, one way to make a list of vertices with the same ID instead of each vertex, and another to change the balancing algorithm.
Another property is that you can quickly find the elements of an array that are closest to a given one, but less than it, or more - for some tasks it is very important.
The interesting thing is: obviously such a tree from the list of identifiers can be built, but it also turns out that you can quickly add to it and quickly remove elements in a very short time <= log (N) (addition)
')
Thus, to sort an array of N elements, you can simply add it to the tree - N * log (N) and then go around from left to right - N ie total time N * log (N) - and we made another very fast array sorting method
By the way, a few more operations for convenience - since we are quickly looking for a vertex with the desired ID, we will do the Set and Get operations to change the DATA field at the vertex. Thus, we update the data corresponding to the given ID in memory also for <= log (N)
I use the AVL tree very often: even in a standard CRC hash, I store CRC groups in the tree, sort arrays and lists, use to check for the existence of elements in the array, store database indices, sort the search results (as described above), eventually , it can even be directly written to a file and read for even greater acceleration.
In general, this structure is not much larger than the list, but allows you to do hundreds of times more operations, i.e. A good alternative to the 1-2 linked list.
Now it’s a little about how to add to the tree, there are a lot of full descriptions in free access, therefore, briefly:
Let's enter at each vertex the number of balance which shows which of the subtrees is higher - left or right.
When adding a vertex to a tree, it sometimes becomes unbalanced. The procedure for adding is simple - we go down the tree to the bottom, using the rule
ID of the left son <parent ID <ID of the right son, i.e. if the new ID <vertex ID is going to the left, otherwise to the right. Having added a son to the lower peak, we must update the balance indicator in our way that we went - we can do this as we descend, we can walk up and down - if we come from the left subtree, then balance--, otherwise balance ++
If at some level we got balance = 0, then the subtree is balanced and you can finish adding (the whole tree does not need to be recalculated because the height of the subtree has not changed - it was balance = -1 became 0 - the left subtree outweighed, added to the right and aligned, or balance = 1 became 0 - the right subtree outweighed, added to the left and aligned)
Well, the most interesting thing is balancing the subtree if at some step on the way back we got balance = -2 or 2, it means that one half of the tree outweighed strongly, and we need to make a certain turn - to raise by 1 link, for example, the right, and the left to lengthen. The whole turn comes down to checking the conditions and rearranging the links. I personally understood it on a piece of paper for myself - only 3 options are possible, which I advise you for better awareness - I will not specifically write here words that can be drawn, and if it’s too lazy, find in the internet ready-made solutions.
The full content and list of my articles on the search engine will be updated here: http://habrahabr.ru/blogs/search_engines/123671/
Source: https://habr.com/ru/post/123951/
All Articles