CODEWITHSUNDEEP
algorithmdata-structurestreebinary-tree
Cratylus
Cratylus

Reputation: 54074

Confused on a fundamental operation on trees

How do we insert a key in a binary tree (not a BST)?
I mean a binary tree does not have some property of nodes like a BST so it seems that an insertion of a key could be anywhere in the tree.
Nevertheless by placing the key anywhere the binary tree could degenerate it to a "list" losing its O(logN) properties.
I have seen creation of binary trees using a merge scheme (example application is a Huffman Tree) but don't seem to have encountered an insert approach for a binary tree.
This question I believe extends to multiway trees since a binary tree would be a specific example case of a multiway trees (2 children nodes), right?
Am I wrong on this? Is there a specific approach to add a new key to a binary tree or are the applications of a binary tree so specific that a merge operation suffices and there is no need for insertion method? Perhaps I have missed the usage applications or concept of a BT completely?

Note: I am asking about binary trees. Not about binary search trees.

Update:
If insert could be in any place what is the meaning of term: Full Binary Tree?
This implies log properties that can not be achieved by inserting anywhere. Is "Full BT" a definition that is not meaningfull as well?

Upvotes: 1

Views: 263

Answers (3)

Will Ness
Will Ness

Reputation: 71065

Here's what all that means. In BST the insertion is guided by the element's properties (bigger than, smaller than, etc). In a general BT you will have to take care of the insertion process.

Let's say you want to use BT to implement unordered collection. Just label each node with two additional values, besides the data element that it carries: the amount of nodes on the left, and the amount on the right. Then let your insertion be guided by these two, achieving near perfect balance. For leaves, use Nodes without children initially, into which any new element can be inserted as a child, when it arrives.

Now you have a perfectly auto-balancing BT implementing an unordered collection of stuff, which can be inserted into in O(log(n)) time, and can be listed in no particular order. That's just one example.

Upvotes: 0

njlarsson
njlarsson

Reputation: 2330

The simplest scheme would probably be to maintain a complete tree as follows. Call the first inserted node 1, the second 2, the third 3, and so on. When you insert node i, make it the left child of node of i/2 if i is even, and the right child of (i-1)/2 if i is odd. For instance, you make the fifth node you insert into the right child of the second one. The sixth node you insert you make into the left child of the third one. If you need to remove a node, exchange it with the highest-numbered one first, so that you always remove from the end.

This tree can be represented by just laying out the nodes in an array starting at position 1, as is common for a binary heap. The children of node i are always 2i and 2i+1, unless these numbers are greater than the total number of nodes, in which case you are at the bottom of the tree.

Upvotes: 0

tskuzzy
tskuzzy

Reputation: 36446

Binary trees are a specific type of tree, satisfying the condition that each node has exactly 0, 1, or 2 children. Any tree satisfying this condition is labelled a binary tree.

As such, there is no "correct" way to insert an element into a binary tree. As long as it's a binary tree before, and a binary tree afterwards, the insertion is valid.

The term binary tree is more for classification than anything. In its pure "abstract" form, it is not terribly useful as a data structure. However it's helpful when characterizing other, more specific types of trees like the Huffman tree as you mentioned.

Upvotes: 2

Related Questions