If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node.
Notice this tree is complete, so the leaves level always toward left.
1 1
2 10
3 11
4 100
5 101
…
Just get binary of size, ignore the msb, from left to right scan bit by bit, 0 is go left, 1 is go right, until you finish the bits.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment