Hot answers tagged

30

I found this post very helpful. To see the difference between Patricia tries and radix trees, it is important to understand: The notion of radix, since Patricia tries are radix trees with radix equal to 2. The way keys are treated: as streams of bits. Keys are compared $r$ bits at a time, where $2^r$ is the radix of the trie. Suppose that we insert the ...


28

Tree Examples (image): A: B: ‾‾ ‾‾ 1 1 / / \ 2 2 3 / 3 This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3. Tree B root׳s value is 1, ...


25

Yes, there is a difference between the three terms and the difference can be explained as: Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. 18 / \ 15 20 / \ 40 50 / \ 30 50 Complete Binary Tree: A Binary Tree is complete ...


22

A lot of research in this area has been done, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection. A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse ...


18

You seem to have an overly "data structures and algorithms" mindset. Not every tree is some kind of search tree. Data structures are often designed to correspond to or capture aspects of a domain model. S-expressions are almost exactly rose trees. (Or rather, I would say how they are typically thought of is as rose trees. Wikipedia is correct in saying ...


14

Hash tables can only tell you if an element is present or not. Here are somethings you can do with a binary tree that you can't do wiht a hash table. sorted traversal of the tree find the next closest element find all elements less than or greater than a certain value See this wikipedia article on K-d trees for an example of a real world data structure ...


13

I think that the original paper by Fenwick is much clearer. The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing and magical to me. Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit: E.g. as ...


13

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than,...


13

Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily produce the same result.


12

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree. After drawing some diagrams we can observe that the longest path will always occur between two leaf nodes( nodes having only one edge linked). This can also be proved by contradiction that if longest path is between two ...


11

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges: 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path) any node can serve as the root of the tree. Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ ...


11

Preproccessing: $O(n)$ For each node in the tree, we will keep the sum of all the values on the path from the root to the node. Additionally, we will prepare for LCA (lowest common ancestor) queries in $O(n)$ time. Query: $O(1)$ When asking for the sum on the path $A \rightarrow B$, Return $$\text{sumFromRoot}(A) + \text{sumFromRoot}(B) - 2 \cdot \text{...


11

One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming). A persistent data structure is a data structure that preserves the previous version of itself when it is modified. (Data structures that do not have this property ...


11

No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function". We assume that the for-loop ...


11

According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS. H. G. Kahrimanian, Analytical Differentiation by a Digital Computer, Symposium on Automatic Programming, 6–14, 1952 K.E. Iverson and L.R. Johnson, IBM Corp. research reports RC-390, RC-603, 1961 A.J. Perils and C. ...


10

This can be solved in a better way. Also, we can reduce the time complexity to O(n) with a slight modification in the data structure and using an iterative approach. For a detailed analysis and multiple ways of solving this problem with various data structures. Here's a summary of what I want to explain in a blog post of mine: Recursive Approach – Tree ...


10

There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to ...


10

This is the famous Steiner tree problem in graphs, which is known as NP-hard.


10

This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store ...


9

Let $X_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p_{0,0} = X_{0,t} = 1$. Clearly $$ X_{d,t} = \sum_{s=0}^t p_{d,t}. $$ Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at ...


9

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve. The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits ...


9

Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes. The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily ...


9

Counting argument The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes, o o o o o / / / \ \ \ o o o o o o . / \ ...


8

The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special. The complexity of the search operation is equal to the height of the tree. Different varieties of binary search trees differ in what guarantees on ...


8

This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated ...


8

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear: PROCEDURE A(n) 1 global = 0 2 for i from 1 to n: 3 B(i) 4 return global PROCEDURE B(i) 1 ...


8

The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is appropriate when the graph is only defined implicitly and may be infinite, or where you've decided in advance that you're only going to search to a fixed depth. An ...


8

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $1,2,\dots,n$. This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another ...


7

Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$: $$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr),~ n\geq h > 1,$$ with the initial conditions $a_{n,h} = 0$, if $h>n$ or $h\in\{0,1\}, n\neq h$, and $a_{0,0} =...


7

Given a graph $G$, a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$. There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree. Regular (sub)tree is just subgraph which is a tree - it doesn't have ...


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