CODEWITHSUNDEEP
data-structuresbinary-search-treeinvariants
CTMacUser
CTMacUser

Reputation: 2062

How can an AA-Tree always have 2 children per non-leaf node for arbitrary total-element counts?

I've been reading up on AA-Trees. One of their invariants is that every non-leaf node has two children. How can that work whenever the total element count happens to not be one less than a power of two?

For example, a three layer AA-Tree that is full will have seven nodes total (4 at Level 1, 2 at Level 2, and 1 at Level 3). If we have add an eighth node, then there has to be seven blanks at the new leaf level, with three of the (newly) Level 2 nodes with zero children and one of them with exactly one child. Are the sibling/horizontal nodes the key? At least one of the references I used doesn't distinguish actual-child right nodes and "sibling" right nodes when considering the two-children-per-non-leaf-node rule.

Yes, this question is similar to "Can a red node have just 1 black child in a red-black tree?," but for an AA-Tree instead of a red-black one.

Upvotes: 0

Views: 30

Answers (1)

trincot
trincot

Reputation: 350771

One of their invariants is that every non-leaf node has two children.

There are two different definitions of "leaf" in the texts on AA trees. One is where it has the traditional meaning, the other is where all nodes that have level 1 are called leaves. Note how the latter definition is broader and also includes nodes that have a red child which is also a leaf.

Sources that use the latter definition, would typically phrase the invariant as you quoted it.

Sources that stick to the traditional definition of leaf (as having absolutely no children, not even red), the said invariant is expressed in the following way: every node of level greater than one has two children.

For instance, this is a valid AA tree:

             4
            / \
           2   6--7

The nodes 2, 6 and 7 have level 1. The two-children requirement only applies to node 4, as it is the only node with a level greater than 1.

If we have add an eighth node, ...

Be aware that adding a node as a leaf is not always the last step in the insertion procedure. The tree may need some skewing and/or splitting to restore the invariants again.

At least one of the references I used doesn't distinguish actual-child right nodes and "sibling" right nodes

The difference between horizontal connectors and downward connectors to red nodes is just a visual one. In either case the red node is a child of the parent, but with AA trees it is common practice to depict the nodes in a way that puts all nodes with the same level at the same visual level, and so that means red links are drawn horizontally. But this is just a choice of representation.

I hope this clarifies it.

Upvotes: 0

Related Questions