a tree in which each node has no more than two children

learn more… | top users | synonyms

-2
votes
1answer
15 views

How do I interpret a binary tree generated using Huffman coding algorithm?

In the lecture note here, a binary tree was generated from the huffman algorithm. However it did not explain what this graph mean. From this binary tree, what can we say about the encoding for the ...
2
votes
0answers
49 views
+50

Inverting ranges with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows: You are given a series of commands that operate on an array initially all zeroes. ...
1
vote
1answer
40 views

Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
3
votes
1answer
61 views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: ...
1
vote
2answers
159 views

Dynamic programming to find the least possible balance of a full binary tree

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
3
votes
1answer
235 views

Binary Indexed Trees: Why does i & -i work?

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to ...
2
votes
1answer
30 views

Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

I was binary indexed trees and I came across this article. One part of the justification was the following: Given that the (binary search tree) tree is perfectly balanced, a node N will have ...
0
votes
1answer
38 views

What if traversal order of two of pre-order, in-order and post-order is same?

Supposing a tree T has the identical: Pre-order traversal and in-order traversal Pre-order traversal and post-order traversal In-order traversal and post-order traversal How does T look like? ...
5
votes
1answer
406 views

Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
0
votes
1answer
9 views

Estimate the running time of counting nodes in a binary tree

I am asked to write an efficient method that computes the number of nodes in T, and here is what I did: ...
2
votes
0answers
29 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
0
votes
2answers
89 views

Is randomly building a BST different from random sampling whole trees?

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution
-1
votes
1answer
17 views

Max heap conversion

In the binary tree shown below, which of the following trees is created after conversion into a (max) heap? There are 4 anwsers to choose : By definition, a max heap is a complete binary tree ...
0
votes
2answers
38 views

Elements in a less than a value in a subarray

Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k. Currently I am using segment tree with each node containing sorted array of leaf elements. ...
0
votes
0answers
69 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
1
vote
1answer
38 views

Smallest(k) in red-black tree. How is it O(logn)?

Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the 'k-th' smallest key in the red-black tree. ...
6
votes
3answers
649 views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...
1
vote
1answer
47 views

Proving correctness of an AVL-Tree colouring algorithm

I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, ...
1
vote
0answers
59 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
1
vote
1answer
63 views

Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.
0
votes
0answers
71 views

Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such ...
1
vote
1answer
48 views

What kind of order is binary tree ancestry?

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be ...
-2
votes
1answer
41 views

Inequality to be disproved

Suppose that a search for a key in a binary search tree ends up in a leaf. Consider three sets : A,the keys to the left of the search path B,the keys on the search path C, the keys to the right of the ...
0
votes
1answer
81 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
0
votes
0answers
17 views

How to insert and delete in vantage-point tree?

I'm trying to implement a vantage point tree, but am having trouble determining how insertion and deletion functions would be implemented. Can you describe these operations?
2
votes
1answer
77 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...
0
votes
1answer
81 views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
0
votes
2answers
61 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
8
votes
4answers
2k views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?
-1
votes
1answer
93 views

Number of Different AVL Tree

I studying the related question. http://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
3
votes
1answer
129 views

Unique keys in a binary search tree

I'm studying for my finals and I can across this statement. "For a fixed set of (unique) keys, any binary search tree containing those keys can be converted to any other BST on the same set of keys ...
-1
votes
1answer
199 views

insert and delete in order statistic tree

I am having trouble in understanding order-statistics tree . Definition : Every node in tree stores the number of descendants of itself . Can you please explain the Algorithm or pseudocode how to ...
0
votes
1answer
100 views

Is this a proper Max Heap Data Structure

I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the ...
0
votes
1answer
225 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
1
vote
1answer
742 views

Print bottom view of a binary tree

For a binary tree we define horizontal distance as follows: ...
1
vote
0answers
46 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
1answer
44 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
-1
votes
2answers
77 views

BST Successor Proof

I'm studying for my CS final and I can't seem to get the anywhere with one of the questions. This is the question: Prove that if a node in a BST has a successor, but has no right child, then its ...
1
vote
1answer
284 views

Finding minimum/maximum value in a Binary Indexed Tree

I know how a BIT works. But I was wondering if a BIT can be used to find the minimum/maximum element in the complete range, or more specifically, to find the minimum (or maximum) value after all the ...
0
votes
0answers
163 views

Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
2
votes
1answer
148 views

Tree flattening with layout guarantees

I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the ...
1
vote
1answer
270 views

Number of 1 child nodes in a binary tree

Does anybody know how would I approach calculating the maximum number of 1 child nodes (nodes that have exactly 1 child) in a binary tree with n nodes. Please don't give me the actual answer as this ...
1
vote
1answer
168 views

Does inserting and immediately removing a node change a red-black tree?

I have the following problem: Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it ...
2
votes
3answers
2k views

Printing The Longest Path from Root to Leaf in Binary Tree [duplicate]

I am stumped as to how to print the longest path from the root of a binary tree to a leaf, essentially traversing the height of the tree. I've got the following for finding the height of a binary ...
0
votes
2answers
152 views

Why the height of the weight balanced tree is logarithmic

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?
9
votes
1answer
302 views

Splay tree with odd number of rotations

When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do ...
1
vote
0answers
43 views

Inversion of BDD

How can I write an algorithm which inverts a 2-level BDD? It should take as input a 2L-level quasi-reduced BDD rooted at $r$ encoding a relation $R : B^L → 2^{B^L}$ and returns the 2L-level ...
1
vote
0answers
21 views

Can xor and xnor for quasi-reduced BDDs be implemented just like union? [duplicate]

Below is an algorithm for union of two quasi reduced BDDs p and q resulting in r. ...
2
votes
0answers
99 views

Difference between fully-reduced BDD and quasi-reduced BDD

I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for ...