There are actually many such patterns, who have two purposes: saving memory, and keeping nodes togeather, primarily for paging performance.
One very simple version is simply to allocate blocks of three, a parent and two children, and this block has four "child" blocks, two for each child. This cuts your allocations by a third. This isn't much of an optimization, until you scale it up, allocations of 7, 15, 31, 63... if you can get it so that as many keys as possible fit onto a single memory system page, then you minimize the time spent waiting for the hard drive. If your keys are each 32 bytes, and a page is 4K, then you can store up to 125 keys, which means you only have to load one page from the hard drive for each 7 rows of the tree. At that point, you load the "child" page, and then follow another 7 rows. A regular binary tree may only have one node per page, which means you spend 7x as much time simply waiting for the harddrive as you iterate the tree. Quite slow. Rotates are a little tricky as you have to actually swap the data, not the pointers as is common with tree implementations. Also, it has a waste to use a LOT of space when the tree becomes larger.
---------
| O |
| / \ |
| O O |
_---------_
__/ \ / \__
/ | | \
--------- --------- --------- ---------
| O | | O | | O | | O |
| / \ | | / \ | | / \ | | / \ |
| O O | | O O | | O O | | O O |
--------- --------- --------- ---------
Another far more complex "pattern" is to cut the tree in half vertically, so the top is one "subtree", and it has many children "subtrees", and store each "subtree" linearly. And you repeat this recursively. This is a very strange pattern, but ends up working vaguely similar to the above pattern, except it's "cache-oblivious", which means it works with any page size, or cache hierarchy. Quite cool, but they're complex, and virtually everything runs on one of three well known architectures, so they aren't popular. They're also extremely difficult to insert/remove from
Another very simple variant is to put the whole tree into an array accessed via indecies, which saves total memory, but only the top is cache friendly, lower levels are worse cache wise than a regular binary tree. Effectively, the root is at index i=0, and the left child is at (n*2+1 = 1), and the right child is at (n*2+2 = 2). If we're at a node at index 24, it's parent is ((n-1)/2 = 12), and it's left and right children are 49 and 50 respectively. This works great for small trees, because it requires no overhead for pointers whatsoever, The data is stored as a continuous array of values, and the relationships are inferred by the index. Also, adding and removing children always happens near the right end, and normal binary tree insertion/rotation/erasure applies. These also have an interesting mathematical novelty, that if you convert the index plus one to binary, that corresponds with the location in the tree. If we're thinking about the node at index 24, 24+1 in binary is 11001 -> The first 1 always means the root, and from there each 1 means "go right" and each 0 means "go left", which means to get to index 24 from the root you go right, left, left, right, and you're there. Additionally, since there's 5 binary digits, you know it's in the fifth row. Neither of these observations are particularly useful, other than they sort of imply that the root node is a right child, which is vaguely interesting. (If you expand to other-bases, the root is alway the rightmost child). That being said, it's still often useful to implement the root as a left node if you work with bidirectional iterators.
0
/ \
/ \
1 2
/ \ / \
3 4 5 6
[0][1][2][3][4][5][6]
