When studying balanced trees, I ran into a problem - I can’t write / find an algorithm that works faster than O (N) to find the i-th ascending element of the tree.

There are many explanations on the net about how to do this in the general case — take the size of the left subtree and apply a series of operations, for example, discussed here: https://stackoverflow.com/questions/2329171/find-kth-smallest-element- in-a-binary-search-tree-in-optimum-way / 2329236 # 2329236

However, the general case is considered everywhere and there is an explanation that for a balanced tree this can be done as a logarithm.

Here I have a problem - when turning subtrees, I have to recalculate the sizes. Any ideas how to do this by saving the desired asymptotics?

Here is a fragment of the balancing itself:

private void rebalancing(Node node) { while (node != null) { updateNodeHeight(node); if (checkNodeHeight(node.left) >= 2 + checkNodeHeight(node.right)) { if (checkNodeHeight(node.left.left) >= checkNodeHeight(node.left.right)) { rightRotation(node); } else { leftRotation(node.left); rightRotation(node); } } else if (checkNodeHeight(node.right) >= 2 + checkNodeHeight(node.left)) { if (checkNodeHeight(node.right.right) >= checkNodeHeight(node.right.left)) { leftRotation(node); } else { rightRotation(node.right); leftRotation(node); } } node = node.parent; } }

    1 answer 1

    For any local operations with trees (including turning, re-hanging and the like) that start from the root of the tree (i.e., you do not apply the operation to an arbitrary node, without updating the entire path from node to root), any associative functions of subtrees (including the number of elements, their sum).

    This is done very simply: get a function that will count the size of its subtree for a given vertex as a parameter, assuming that the size of the subtree is correct for children. Then you just need to call this function for the peaks, which have changed some of the children.

    Add an invariant to the program: each vertex correctly calculates the size of its subtree. This invariant will be required everywhere except for the turning procedures. And when you turn along the edge, you are somehow re-supporting the children somehow between the peak and its parent. In children, the subtree sizes are still correctly calculated, which means that by recalculating for the vertex and the parent (in the right order - first for the one that became lower, and then for the other), we will correctly update the values ​​in them.

    This is only a constant number of operations on each turn, which obviously preserves the asymptotics.