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, ...
14
To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question
For some kinds of binary search trees, including red-black trees but
not AVL trees, the "fixes" to the tree can fairly easily be predicted
on the way down and performed during a single top-down pass, making
the second pass unnecessary. Such insertion ...
11
The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.
Consider the segment tree given below.
Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to ...
11
I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures!
There are some cases where you can't use B-trees at all.
One prominent case is std::map from C++ STL. The standard requires that insert does not invalidate existing iterators
No iterators or references are invalidated....
9
A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t>=2 called the minimum degree of the B-tree.
Every node other than the root must have at least t-1 keys. Every internal node other ...
9
Suppose you had an empty array:
0 0 0 0 0 0 0 0 0 0 (array)
0 0 0 0 0 0 0 0 0 0 (cumulative sums)
And you wanted to make a range update of +5 to [3..7]:
0 0 0 5 5 5 5 5 0 0 (array)
0 0 0 5 10 15 20 25 25 25 (desired cumulative sums)
How could you store the desired cumulative sums using 2 binary indexed trees?
The trick ...
9
If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $...
9
When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:
$$C_i = \frac{1}{i+1} { 2i \choose i }$$
are the Catalan numbers. Using Stirling's approximation, we find:
$$\log C_{2n} = 2n - O(\log n)$$
So to represent a ...
9
You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.
Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it ...
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
A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for java.util.Map). So let's just look at maps for a moment.
If you think about a linguistic dictionary, it's ordered by "word",...
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
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
Yes, this is possible.
You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.
One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the ...
7
If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:
L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
n = q.pop
if k < L.size:
n.left = node{value=L[k]}
k++
q.add(n.left)
if k < L.size:
n....
7
Adding to aelguindy's answer: You just can't put n unsorted items into any kind of data structure, and then enumerate them in sorted order, in better than O (n log n) total time - because if you could, then you could sort an array in better than O (n log n) time.
If we define a "sorted" data structure as any data structure that can be enumerated in sorted ...
6
I assume that we start labeling heights from $0$.
Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-...
6
You can continue as same as line 4 the process like that:
$$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>\cdots$$
As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of ...
answered Jun 22 '14 at 5:28
Jonathan Prieto-Cubides
2,1313 gold badges15 silver badges26 bronze badges
6
Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:
Procedure NN(node), given query q
if(node is leaf)
Search all points, in node, update current best
else {internal node}
if( cut_coord(q) <= node's cut-value )
NN(left-child)
if( cut-coor(q) + ...
6
In a nutshell: IDA* traverses all paths of lengths iteratively larger and it stops only when expanding (as opposed to generating) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.
...
6
This is an interesting question. Certainly worth asking.
The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.
As I was writing this answer, I discovered that the wikipedia article
on ...
6
Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected ...
6
This is a nice question.
In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without ...
5
I have seen three ways to characterize B-tree so far:
With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer).
The simplest B-tree occurs when $t=2$. Every internal node then has either 2, 3, or 4 children, and we have a 2-3-4 tree.
The text referenced in Nasir’s answer closely follows B-tree ...
5
¡Nice question really!
The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because ...
5
Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$.
Of course there are plenty of other ...
5
For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a bottom-up fashion. This involves two passes through the tree: the first pass starting at the root and moving down the tree to find the right place to do the insertion, and the second pass starting at the insertion point ...
5
BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.
Probably you have not encountered need yet.
For example ternary tree with comparing >, =, < gives theoretical improve $O(log_3 n)$, but self balancing trees in basic form do not accept duplicates, so there is more overhead ...
5
Okay I understood the issue.
Properties of B+ Tree.
All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
All the leaves are in same depth, and here d = 2.
Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.
All ...
Only top voted, non community-wiki answers of a minimum length are eligible