How to create left canonical binary search tree?

Question

I am studying about Data Structures and I have to build left canonical binary search tree also known as left-balanced binary search tree.

Example:

I have no idea where and how to start building that tree. Can anyone show me how to do it. Maybe on simple example with elements from 1, 2, 3,... to 10.

This tree is not balanced by the definition I know of - The left child of the root has no right subtree, and a left subtree of height 2 — Chris, Mar 09 '16 at 02:12
Left canonical is the same as left balanced. Left balanced binary search tree is a type of Huffman tree (Huffman coding) I think. — pbjerry10, Mar 09 '16 at 23:01
Still not quite balanced. See this: http://stackoverflow.com/questions/7275586/left-balanced-binary-trees Namely you need one additional node for Root->right->right. Will review your question though — Chris, Mar 11 '16 at 01:20

rkj · Accepted Answer · 2016-03-11T19:57:59.260

In practice, we first find the greatest power of two M = 2^n so that M ≤ N where N is the number of elements we wish to insert. The tree will hold M − 1 elements on all levels excluding the bottommost. The bottommost level itself will hold M elements divided between M/2 in the left subtree and M/2 in the right subtree.

We compute the remainder R = N − (M − 1) and then if R ≤ M/2

LT = (M − 2)/2 + R
RT = (M − 2)/2

else if R > M/2

LT = (M − 2)/2 + M/2
RT = (M − 2)/2 + R − M/2

EXAMPLE:

In example (2, 3, 7, 9, 11) we have N=5 elements and M=4, so R=5-(4-1)=2. Hence LT is 3 and RT is 1. Therefore, 9 becomes the median element used as root node, and 2,3,7 is put into the left subtree whereas 11 becomes the right tree. We recurse to compute the entire tree.

Source: http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/2535/pdf/imm2535.pdf

YOUR EXAMPLE:

You have elements: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

N = 10
M = 2^n where M ≤ N
M = 8
R = 10 - (8 - 1) = 3

So 3 ≤ M/2 is valid.

LT = (M - 2)/2 + R
LR = 6
RT = (M - 2)/2
RT = 3

So in left subtree there are elements 1, 2, 3, 4, 5, 6. In right subtree are elements 8, 9, 10 and 7 is median.

We draw root node 7.

We do the same then for LT elements 1, 2, 3, 4, 5, 6.

N = 6
M = 2^n where M ≤ N
M = 4
R = 6 - (4 - 1) = 3

So 3 ≤ M/2 is not valid.

LT = (M - 2)/2 + M/2
LT = 3
RT = (M - 2)/2 + R - M/2
RT = 2

In left subtree there are elements 1, 2, 3. In right subtree are elements 5, 6 and 4 is median.

We draw 4 as left child of 7.

We do the same then for LT elements 1, 2, 3 of element 1, 2, 3, 4, 5, 6.

N = 2
M = 2^n where M ≤ N
M = 2
R = 3 - (2 - 1) = 2

So 2 ≤ M/2 is not valid.

LT = (M - 2)/2 + M/2
LT = 1
RT = (M - 2)/2 + R - M/2
RT = 1

In left subtree there is element 1. In right subtree there is element 3 and 2 is median.

We draw 2 as left child of 4.

Logically then, 1 is left child of 2 and 3 is right child of 2.

By rule that if there are only two elements, right element is median (root node). So 6 is right child of 4 and 5 is left child of 6.

We do then same for the RT (right children of root node 7) with elements 8, 9, 10 where 9 is median and 8 is left child of 9 and 10 is right child of 9.

Final tree should look like this.

How to create left canonical binary search tree?

1 Answers1