Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
18

Claim: No, there is no such $\mu$. Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim. Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes. Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3] Now let $(T_h)_{i\geq 1}$ with $T_h ...


10

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


9

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

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

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


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

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


5

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


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

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


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

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

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


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

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


4

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


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

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


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

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


3

Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this: 1) Average insertion cost is constant for red-black trees (if you don't have to search), while it's logarithmic for AVL trees. Furthermore, it involves at most one complicated restructuring. It's ...


3

Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.


3

At the time of writing I was not absolutely sure what the problem was. This lead to a more general second answer. See details in discussion at the end of this answer. Apparently, the "idea that does not work" does not work because you do not know the index of an element $S_i$ in $F$ organized as a tree. This is what is addressed here. The problem is ...


3

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


3

Properties of Red Black Tree: 0) Every node is black or red. Ok, no problem. 1) Root is black. Ok, no problem. 2) All leaves (empty nodes) are black. Ok, no problem. 3) Every red node must have two black childs. Ok, no problem. 4) Every path from any node to leaf has equal number of black nodes. It seems problematic. So now comes problems: When you ...


3

Take a complete binary tree of height 2 (with 7 vertices), and add two children to the two left leaves. The tree is height-balanced but the root is not weight-balanced.


3

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of ...


3

There is a $\Omega(\lg \lg n)$ lower bound: you can't hope for an algorithm that is faster than $O(\lg \lg n)$ time. Let the height of the tree be $H$. AVL trees are balanced, so as a result the height is $H=\Theta(\lg n)$. Suppose we solve the height problem by visiting the nodes in a longest path, one by one. The longest path has length $H$, so this ...


3

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


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