Traversals from the root in AVL trees and Red Black Trees

Question

We all know that for insertion() operation in AVL tree following can happen:

We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance we have to check heights of the ancestors of the newly inserted node and in doing so, we could end up traversing up to the root.

I completely agree with this.

But according to me the same can happen in Red Black tree because first we would traverse down the tree to appropriate node and then insert the key.Then there is a possibility that a series of rotation and flip color operations could make us traverse the path up to the root.

Now my question is : why following statement is right?

In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.

It came as a question, which of the following statements is right about AVL and Red Black trees and the option with given statement was marked correct in the answer key. I am trying to figure out mistake in my second observation?

Answer 1

For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a bottom-up fashion. This involves two passes through the tree: the first pass starting at the root and moving down the tree to find the right place to do the insertion, and the second pass starting at the insertion point and moving upward toward the root fixing the tree as necessary. Frequently, these two passes are implemented as one recursive function, where the first pass is going down the recursion, and the second pass is coming back out of the recursion.

For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary. Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

Note that, for trees like red-black trees, where you can implement insertion either way, the two different approaches (bottom-up/two-pass vs top-down/one-pass) do not necessarily yield exactly the same tree, but will yield trees that are equivalent. For example, the exact pattern of red and black nodes may vary slightly, but will still obey all the expected invariants of a red-black tree.