c++ * and & at the same time

Question

In my Data Structures in C++ class we're working on binary trees. Some of the code contains places where & and * are used at the same time (right next to each other) and it's very confusing.

void balance( AvlNode * & t )

is one example of a function definition in which this is used. What happens here with the * and &?

Edit: The answers to this have told me that I really know nothing about pointers and references, but the sources all say different things, like here for example calls * the dereference operator. Where can I find all of this information in one place? (not on stackoverflow preferably)

Answer 1

Read from right to left¹, reading & as a "reference to [a|an]" and * as a "pointer to [a|an]", so you get: "t is a reference to a pointer to an AvlNode".

---

^{1. For more complex cases, it's not always entirely right to left--it's from the name being declared outward to the type of the declaration. If you have multiple nested parentheses, you proceed right from name to a closing parenthesis, then left to the matching open parenthesis, then right from the place you last left off to the next closing parenthesis, and so on until you reach the outer-most level.}

Answer 2

The '&' character has a special meaning in C++ when it's used inside of a function declaration or definition. It means "pass the value by reference". When you "pass by reference" C++ will automatically create a reference of your variable when you pass it to the function, and then it will automatically dereference it inside the function.

So this function passes one variable t of type AvlNode * by reference. Hence, you have AvlNode * & t

So for example:

void balance( AvlNode * & t )
{...}

main()
{
   AvlNode * a = new AvlNode();
   balance(a);
}

is the same as:

void balance( AvlNode ** t_ptr )
{
   AvlNode * t = *t_ptr;
   ...
}

main()
{
   AvlNode * a = new AvlNode();
   balance(&a);
}