# Tag Info

25

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 ...

13

The wikipedia article has a nice concise description of when you would want to use the different types of depth-first search: Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly. ...

13

You need to do various things with trees, like translate between the data structure and some serial representation, like on a file or in a language. So, for example, suppose you have a parse tree like this: * / \ + \ / \ \ A B C You could serialize it as * + A B C by walking it in prefix order, or as A B + C * by walking it in postfix ...

12

A tree is suitable for decoding Morse code, that is converting from dots and dashes to letters. As long as you know where the breaks are between letters, this is entirely feasible. To go the other way, from letters to dots and dashes, there's no need to use a tree. Finding a letter in such a tree would be annoying. Just make a simple lookup table: a => "...

12

pre order traversal is a traversal, it visits every node in a binary tree Depth First Search is a search, it goes around an arbitrary graph looking for a certain node (that it works best in a non cyclic graph (a.k.a. tree) is irrelevant) this alone is a large enough difference to call them difference names

10

One way to do this would be to create a method on your tree that measures the depth of the tree at a given node. You don't have to store the value, and if you use such a getDepth() method only for testing, then there's no extra overhead for normal tree operations. The getDepth() method would recursively traverse its child nodes and return the maximum depth ...

10

The representation of the letters is determined (roughly) by "the frequency of use of letters in the English language . . ., and the letters most commonly used were assigned the shorter sequences of dots and dashes." You could build a tree with traversing to the left means adding a '.' and traversing to the right means adding a '-' to the previous code. You ...

10

The indentation in the code is important: if uncle.color == red: # Handle case else if z == z.p.right: # Handle case 2 # Handle case 3 The syntax is a bit quirky, because they squished the if to appear on the same line as the else, but case 2 is indented further inward compared to the remaining case 3, indicating that they do not belong ...

8

There are some self-balanced trees such as Red-Black tree and AVL tree. For more information see: Wikipedia: Self-balancing binary search tree Wikipedia: Red–Black tree Wikipedia: AVL tree or Chapter 13 of CRLS book

8

Just sort the players by team and number them starting from 0, so e.g. 0(000) T1a (team 1 player a) 1(001) T1b 2(010) T1c 3(011) T2a 4(100) T2b 5(101) T3a 6(110) T3b 7(111) T3c Then reverse the bits in each number to fill out your bracket sheet 0(000) T1a\______ 1(001) T2b/ \_______ 2(010) T1c\______/ \ 3(011) T3b/ \...

7

Using a binary tree for collision handling in a hash table isn't just possible - it has been done. Walter Bright is best known as the inventor of the D programming language, but also wrote an ECMAScript variant called DMDScript. In the past, a headline claim of DMDScript (or possibly an ancestor - I seem to remember the name DScript) was that its hashtables ...

7

Is it possible to do a binary search tree if the data does not possess natural ordering? I don't know what the word "natural" means in your context; it seems vague. Moreover, images, videos, executables and sound files all seem perfectly obviously orderable to me. Order them by byte ordinal comparison, in the event of a tie, the shorter file is smaller. ...

5

The point of having different algorithms to deal with binary trees is not to do things with trees. On this abstract level, one order is largely as good as any other, since you only get abstract symbols out of the procedure. But trees are typically used to represent interesting stuff, and that can make a big difference in the outcome. For instance, if the ...

4

It is important to note that hash tables only have average access time of O(1). This means a particular operation could be much worse. Additionally, there are several requirements for properly formed hash trees: Mostly empty - few hash algorithms perform well beyond 70% usage, and most recommend 50% usage. Collision handling is complex - either having to ...

4

Your code, as written, will produce a tree that looks like this: 5 / \ / \ 1 8 \ / 3 6 \ 9 A properly balanced tree looks like this: 6 / \ / \ 3 8 / \ \ 1 5 9 So, no. this is not balancing your binary tree. This is simply constructing a sorted binary tree with a balance that is totally dependent ...

4

Self-balancing trees are required to maintain their structure so that the keys are always sorted (that is, so an inorder traversal of the tree results in all the elements in order). If your rotations are producing a tree that is no longer in order, then your rotations are incorrect. Keys can move "vertically" (children can become parents, and vice-versa), ...

4

I'm doing pretty well so far but in some cases I find myself in a situation like this dictionary->left->key or maybe more: ptr->ptr->ptr->ptr (any number of times) Does this represent a problem? Yes and No. In itself, it is not a problem if you use the -> operator multiple times in an expression to reach the value you want to have. ...

3

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 ...

3

An order is just a relationship between two elements in a set. The relationship is not always "is greater than". For example the relationship "is the son of" is, mathematically speaking, an order. It is not the order you need for a binary search because it is not well defined for all the elements: what if I pick two siblings? This relation exist only for ...

3

Yes, there can be various BSTs consisting of the same numbers. Let's take the numbers 1, 2, 3. If the order you add them to the tree is 1, 2, 3 then the tree would have 1 as root, 2 as it's right node and 3 as 2's right node. If the order is 2, 1, 3 then the tree would have 2 as the root, 1 as the left node and 3 as the right node. If the order is 3, 1, 2 ...

3

The number of edges is constant. You should construct a Huffman tree, and use the cost of each leaf as the frequency.

2

A very simple balanced tree is an AA tree. It's invariant is simpler and thus easier implement. Because of its simplicity, its performance is still good. As an advanced exercise, you can try to use GADTs to implement one of the variants of balanced trees whose invariant is enforced by the type system type.

2

I can think of a variety of possible solutions, but they all involve a high memory overhead. Let k be the number of candidate parent nodes, ℓ the level of the distant child node (i.e. the distance from the root), c the child node, and p the candidate parent node(s). O(k) – Store directions to each node Each node has an ordered array of IDs (e.g. pointers) ...

2

The OOP way is to combine together polymorphism and recursion. A binary tree is defined as either empty or a set of value, left and right where both left and right are binary trees. To represent it properly left and right must be binary tree themselves, even if they are empty. To represent that in object oriented way, we'll have a tree base class and node ...

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 ...

2

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

Yes, but there isn't a standard name for it shorter than what you've already written. Wikipedia says: [...] by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost ...

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) } # ...

Only top voted, non community-wiki answers of a minimum length are eligible