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

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

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

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


8

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


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


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


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

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it. A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP): If $k = 0$ or $k = 1$, the tree is simply a single node. If $k \ge 2$, the tree has a left subtree of ...


6

Yes every AVL tree is a BST also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child) so therefore every AVL is a binary tree as well. AVL tree is just a binary search tree that tries to do rotations when its needed (when the tree becomes unbalanced) in order to stay balanced, ...


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

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

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

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


5

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.


5

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty leaf hitting 2 black nodes. This is not allowed in a Red Black Tree because by definition a path from root to an empty leaf should contain the same amount of ...


5

The approach is to build a fully persistent version of the rope data structure. This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world") and version 2 ("hello"). To undo the last operation, you just start working from version 1 rather than version 2. In particular, yes, you can store these ...


4

EDIT: @Maxym's answer is correct after all and is actually equivalent. I had simply misinterpreted the notation. Leaving this answer anyway as the cited link provides a useful explanation. While @Maxym's answer is on the right track, his formula didn't quite work for me. After beating my head against the wall for quite some time, I found this link written ...


4

I found the answer myself. We know that $$b(x)=b(x')+b(y)[b(y)>0]+1$$ $$b(y′)=b(x)+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ thus $$b(y′)=b(x')+b(y)[b(y)>0]+1+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ where $$b(x')−b(x′)[b(x′)>0]=b(x')[b(x')\le0].$$ So, the new balance factors will look like this: $$b(y′)=b(y)+b(x')[b(x')\le0]−1$$ $$b(x′)=b(x)−b(y)[b(y)>0]−...


4

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree. Let $T_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0. In other words, it is a perfect binary tree of height $H$, ...


4

Short answer: it depends. The answer depends on what is the set of the possible elements of the AVL tree. Natural numbers, no duplicates allowed. Yes, there is an AVL tree requiring a rotation on the next insertion, whatever that is: 1 / \ 0 3 / \ 2 4 The next insertion has to be a natural $\geq 5$ and cause a rotation. ...


4

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties. In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, while the right subtree is a full maximal binary tree of height $2\log n$. The black height of the right subtree must be $\log n$ as well, therefore its ...


4

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL. In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a rope, which is a stronger kind ...


4

Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time. That is, there exists more than one valid red-black tree insertion algorithm, whose outputs are not always equal. The easiest way of seeing this is to focus on the correspondence between red-black trees and $(2, 4)$-B-trees. A black ...


4

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance. The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call ...


4

If you want to show that the height is $h=\mathcal O(\log(n))$ then I would suggest the following: Define $n_h$ as the minimum vertices in tree with height $h$ Then to get the minimum vertices for given height: $n_h = n_{h-1} + n_{h-3}\\ n_h \ge 2n_{h-3}$ Now from the inequality you know that: $n_{h-3} \ge 2*n_{h-6}$ (Just changing index) Placing it to ...


4

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other. The operation can be seen as a associative property: $T_1\;p\; (T_2\; q\; T_3) = (T_1\; p\; T_2)\; q\; T_3$ of the inorder traversal of the nodes in a binary tree. Both the left and right diagram have the inorder $\...


4

The obvious resource, Wikipedia, I did not find very helpful. When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After rotation the height of that subtree is the same as in the original subtree, so all nodes upwards are balanced. See the answer by colleague Raphael to "Does ...


4

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has ...


4

AVL trees are a kind of binary search trees. As such, they implement the following operations, among else: Initialize an empty tree. Add a value to the tree. Remove a value from the tree. Search a value in the tree. Try to use some of these operations to answer your question.


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