3

This can be proven by induction. What you describe is a Full binary tree, and it has a convenient induction definition: a single node (or leaf) is a full binary tree; a tree with two children that are full binary trees is a full binary tree. This permits a structural induction proof of the property you want: prove that it is true for a single node tree; ...


3

Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"? To be a bit stereotypical: yes. There are reasonable ways to approach the problem, but it's so dependent on use case that you will need to take a look at how your ...


3

GCC C++ case study Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly! As shown at https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661, in GCC 6.4: std::map uses BST std::unordered_map uses hashmap ...


3

$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k<n/3$ or $\ge2k+1>2n/3$. A version suitable for all $n$ can be proved as follows. Let $\...


3

Unfortunately, the approach of constructing automata for each formula and testing their equivalence is pretty much the best you can do. The problem of checking whether an LTL formula is valid, that is, whether it is satisfied in every computation, is PSPACE complete (this is an easy exercise, given that LTL satisfiability is PSPACE complete). Thus, checking ...


2

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675 As pointed out above by Raphael, there is a close relationship to treaps. You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree


2

A heap of height $h$ is complete up to the level at depth $h-1$ and needs to have at least one node on level $h$. Therefore the minimum total number of nodes must be at least $ \sum_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h. $, and this tight since an heap with $2^h$ nodes has height $h$.


2

There are two questions here: How do you implement a pointer data structure such as a red-black tree in a database? Should you implement a pointer data structure in your database to solve this problem in practice? The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For ...


2

$x_1=5, x_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.


2

Let us prove that in a binary tree with $n\gt1$ nodes, there is a node $u$ such that $\frac{n}3\le size(u)\le\frac{2n}3$. Proof: Run the following algorithm. Let $u$ be the root node of the given binary tree. Check the number of nodes in the left subtree and the right subtree of $u$. If the number of nodes in the left subtree is between $\frac n3$ and $\...


2

This approach does work. A "Binary-Indexed-Tree" is just an implicit balanced binary tree with some extra "compression". See this answer for the details on how and why this is done, but essentially the purpose is just to run in fewer cycles. Your approach works fine asymptotically and will probably even perform fine in practice. First, ...


2

Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.


2

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be: It is easy to see that it does not respect the fourth condition of the definition. In the claim, when it is said that: a key […] has exactly one child (which isn't null) it ...


1

It doesn't significantly increase the speed, the increase will just be a constant at best. Essentially, you still search the same tree, just in a different ordering, and that means you will still do $O(\log(n))$ operations to search a number. It might be useful to think of this as just two separate BSTs, one for odd numbers and one for even numbers. So, this ...


1

This is not a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem. Notice that in any path from the root to a leaf, say $v_1,\dots, v_k$ we must have that the number of green nodes is at most $1$ (by the first property). Also, notice that the number of blue nodes in the ...


1

It might be surprising to you, but "the mirror reflection of the right subtree around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself" could be, in fact, part of the definition of "a mirror reflection of the right subtree around ...


1

Perform an inorder traversal. This can be recursively defined as "traverse left subtree, visit root, traverse right subtree". Alternatively, follow the tree (visiting each node "between" left and right subtrees.)


1

Most of the time when binary trees are used, we first create in a way we define; heap, B+ tree, 2-3 tree and etc. So, the probability of being a balanced tree also depends on the tree building algorithm. for example, a list of length 2^n -1 convert into heap definitely give a balanced tree. Just a thought.


1

A binary tree is a rooted tree where every internal node has at most two children. A recursion tree is a rooted tree which traces the execution of a recursive procedure. It need not be binary.


1

It’s not true for trees with 3k+1 nodes. There is supposed to be a subtree with k+1/3 to 2k+2/3 nodes, that is k+1 to 2k nodes. Take a tree starting with only left nodes until we have a subtree of 2n+1, and then both sub trees have size n. The theorem fails. So assume n = 3k or n = 3k+2. n = 3k: We start with N = root of the tree. As long as N has a subtree ...


1

The space complexity is the amount of space used, which is essentially the size of your call stack in your deepest line of recursion. The runtime is indeed $O(N)$ but the space complexity is $O(H)$ where H is the height of the tree. Even following the link you provided, they state this:


1

Here are some ideas: Suppose that $\ell$ is a leaf of $T$ which doesn't belong to $S$. Then we can safely remove $\ell$. Suppose that $\ell$ is a leaf of $T$ which does belong to $S$. If its unique neighbor is also in $S$, then we can safely pair them up. Suppose that $\ell$ is a leaf of $T$ which belongs to $S$, but its unique neighbor $r$ doesn't belong ...


1

If the array has length $n = 1$ then the constructed tree consists just of a root. Therefore $a_1 = 0$. Similarly, $a_0 = 0$ (this is a corner case). Now suppose that $n \geq 2$. Without loss of generality, assume that $x = 1$, and so $y = n$. The array splits into two halves: $1,\ldots,r-1$ and $r+1,\ldots,n$. The first has length $r-1$, and the second has ...


1

There are some implementations of Balanced Binary Search Trees, also known as Self-balancing Binary Search Trees. One of the aspects that can be considered when balancing a tree is it's subtrees height difference. This height aspect aims to keep the tree as flat as possible. The more flat the tree is, the less levels it will have and the search will be ...


1

You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric ...


1

If the height is $0$ it is true. Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST. Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the ...


1

For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$. Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too. For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call ...


1

I know there's already an accepted answer, but for those who've got the same question and are still a little bit confused (as I was), or sth is unclear, watch this crystal clear explanation till the end.


1

A similar problem, named "Black Hole", appears as one of the problems of 2019 Russian Olympiad of schoolchildren in computer science. The problem asks for a program that interacts with a jury program simulating probe sensors and determines the radiation level of each black hole. The sensor mounted on the probe can answer the following queries: ...


1

"I find the non-recursive implementations using stacks are not easy to understand." One reason the complexity comes is due to "simulating" our own call-stack, which was done by compiler for the recursive method. The non-recursive variant may also include some optimization in addition to implementing what the recursive method does. "...


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