# Tag Info

4

You can test whether $a=b$ as follows: if it's not true that $a<b$ and not true that $b<a$, then it follows that $a=b$. (Disclaimer: this requires that it be possible to order all of the elements using $<$, i.e., $\le$ be a total order. I imagine you were assuming this. But if it's not, you're screwed anyway and the problem is not solvable -- ...

4

If what you mean is that you want to build a BST and you only have the $<$ operation, and you only know the algorithms with the $\leq$ operation, you can notice that : $$a \leq b \Leftrightarrow \neg (a > b)$$ $$\Leftrightarrow \neg(b < a )$$ Hence, using a negation in the right place, you can build your usual algorithm.

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

Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and Right. This means that starting from the root (a), we will traverse the whole left branch, then print a, and finally traverse the right branch. You started off correct; however, your mistake was that you put m beforee h. It is an easy mistake to ...

3

This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree.

3

You must refer to the definition of a Binary Heap: A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right. It is by definition that it is never unbalanced. The ...

2

Here is a natural approach to explore the extreme case. Let node $r$ be the root of a red-black tree. Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height. Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of ...

2

Apparently, you want to rebalance the AVL tree. You can either do a simple left rotation or a right-left rotation. I prefer not to mention right-right rotation since that term is misleading and ambiguous. You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look ...

2

The question is a little confusing, since a binary heap is usually implemented in an array, not a tree. The tree is used for visualization. Consider the following heap: It is given by the following array: $H=[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$ Since a complete binary tree corresponds to an array, the opposite also holds. New elements are added to the ...

2

Consider a constant set of $k$ insertions done directly at the max node, and the left and right sub-trees of the root node ($L$, $R$). If each rebalancing operation required only constant time, then only $O(\frac{log(n)}{k})$ of the inserted elements could be in $L$, since the maximal element is a leaf and the tree is balanced. While this simple analysis ...

1

It sounds like your pseudocode is equivalent to the following: Do search for low in the BST. Find this value or the next largest value. (assuming that the BST is somewhat balanced, this is $O(lg(n))$) In-order traverse until we reach an element that is greater than high, adding all values that we traverse to some running sum. (in order traversal of $m$ ...

1

That is not correct BST as Narek mentioned. BST should be - 20 / \ 10 26 For inorder traversal, start visiting tree from Top to bottom and left to right manner and print a node only when it is referenced 2nd time. So, inorder traversal here would be 10,20,26.

1

This can indeed be solved in $O(n)$ time. What you mentioned (checking value of root, calling recursively for left and right subtree) almost works, the issue is just that we don't know the size of the right subtree, so we cannot immediately recursively solve the left subtree as we don't know where it ends. But this is not an issue: Just recursively solve the ...

1

Actually any BST can be transformed into balanced BST using $\mathcal{O}(n)$ rotations. High level explanation: We convert given BST to right going chain(see fig-1 below). Then we convert that chain to balanced BST. First convert given BST into right-going chain. Which can be accomplished using $n-1$ right rotations as follow. Consider initial-right-chain ...

1

The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$. If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet ...

1

As per wikipedia (Tree Traversal), it is called Out-order traversal Though, you could also find reference to reverse in-order traversal, which means the same.

1

I don't think that it is possible to balance a tree in logarithmic time: An algorithm has to determine somehow, when it is finished In this case, establishing that the tree is balanced is necessary This operation alone is $\mathcal O(n)$ (count the height of left/right subtree) Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there ...

1

Do an inorder traversal of the BST...and store it in an array the array will be sorted. next construct a balanced binary search tree from this array. 1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) ...

1

You are correct $-$ the red-black tree you have drawn is not balanced. For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed. However ...

1

Because new nodes are inserted from right to left in a heap unlike binary search tree. While inserting nodes in a heap if there arises distortion in heap property, the new inserted node is bubbled up according to its key in the suitable position.

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