# Tag Info

13

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

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

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