Tag Info

New answers tagged

1

Binary trees why use them? In programming you work a lot with collections of same type data. The two basic ways of storing this data are : linked lists and arrays. They both come with up and downsides: In a linked list it's easy to add elements at any position or remove elements. But access to a specific element is harder, because you have to go through ...


2

Any tree structure, where a node can have unlimited numbers of children, can be implemented using a binary tree. For each node in your tree, replace it with a node with a right and left pointer. The left pointer goes to the first of the node's children. The right node goes to the next sibling of the node. All the children of a given node are in a linked ...


2

Implementations differ, but traditionally nodes were allocated as needed and as such were generally thought of as non-contiguous. In practice, if the binary tree were being constructed from a data set (e.g., data read from a file), then the node allocations would usually wind up being contiguous, since they were typically allocated sequentially and not ...


21

No, binary trees are not for storing hierarchical data in the sense you're thinking of. The primary use case for n-ary trees, where n is a fixed number, is fast search capability, not a semantic hierarchy. Remember the old game where one person thinks of a number between 1 and 100, and the other has to guess it in as few guesses as possible, and if you ...


1

To calculate the height, you have to traverse tree, possibly by using recursion. To check that it is balanced, you have to traverse it exactly the same way. So these ways can probably be combined. I am tired and can't think of a good name for such a function right now, and I have a feeling the solution is ugly and there is probably a better way. But, it ...


2

If balanced means that the height is at most log_2(number_of_nodes) + 1, I suggest an algorithm could look like this: # define a tree tree := null | (left : tree, right : tree) # check if a tree is balanced is_balanced(tree) { maximum_height, number_of_elements = walk(tree) return maximum_height <= 1 + log_with_base_2(number_of_elements) } # ...



Top 50 recent answers are included