a tree in which each node has no more than two children
7
votes
0answers
141 views
Google Code Jam Great Wall Problem
So, Google Code Jam round 1C has just wrapped up, and one of its problems seems rather elusive to me: https://code.google.com/codejam/contest/2437488/dashboard#s=p2
A quick summary of the problem is ...
2
votes
1answer
36 views
Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$
Given we change the rule to:
$-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$
I was wandering whether it's possible and how would it affect the trees' height, would it ...
2
votes
1answer
34 views
Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$
We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.
We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So ...
6
votes
2answers
100 views
Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?
The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
3
votes
2answers
68 views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad ...
3
votes
1answer
67 views
AVL tree with fixed height and as few elements as possible
I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.
In a ...
3
votes
1answer
70 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
0
votes
1answer
36 views
Constructing a binary tree with given traversals [duplicate]
I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.
for eg.
Post Order : DCBGFEA
In Order : BDCAFGE
This is how I am trying to ...
5
votes
2answers
150 views
Colour a binary tree to be a red-black tree
A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).
I was wondering if we can do something similar with Red-Black trees.
...
7
votes
1answer
313 views
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
2
votes
1answer
99 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
1
vote
1answer
112 views
What is the local minimum of a complete binary tree
I have this confusion. What is the local minimum of a complete binary tree?
Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a ...
2
votes
1answer
58 views
MinHeap represented by an array - two simple statements
I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.
These are the following statements:
Preface : Let A[n] be an array of min-heap (a min-heap ...
1
vote
1answer
82 views
Facebook Hackercup 2013: Balanced Smileys
On Facebook HackerCup 2013, they asked the following question:
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to express ...
1
vote
1answer
91 views
Calculating traversal position of a node in a full binary tree, given its path
Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in ...
2
votes
1answer
69 views
Height of AVL after entries
Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$
elements. After the insertion of $n^2$ elements, what would be its
height?
My idea: the height of an AVL tree ...
7
votes
0answers
350 views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
12
votes
2answers
144 views
Function that spreads input
I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:
$f$ should be bijective
Both $f$ and $f^{-1}$ should be calculable pretty fast
...
7
votes
1answer
189 views
How many max heaps are there?
How many different max-heaps can I form using a list of $n$ integers.
Example:
list [1,2,3,4]
and max-heap is 4 3 2 1 or
...
1
vote
2answers
256 views
Maximum number of nodes with height h
How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the ...
2
votes
1answer
371 views
What is the time complexity of calling successor $n$ times during tree traversal?
According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time ...
1
vote
1answer
95 views
Can you have a binary search tree with O(logn + M) property for the following case
Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I ...
0
votes
1answer
36 views
Can you have three consecutive black nodes in red-black search tree?
Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma ...
0
votes
1answer
335 views
Proof that a randomly built binary search tree has logarithmic height
How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
3
votes
2answers
485 views
Why is the minimum height of a binary tree $\log_2(n+1) - 1$?
In my Java class, we are learning about complexity of different types of collections.
Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
2
votes
1answer
85 views
Size of the universe for van Emde Boas Trees
In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde ...
1
vote
1answer
188 views
What is the depth of a complete binary tree with $N$ nodes?
This question assumes the definition of a complete binary tree to be†:
A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level ...
0
votes
1answer
295 views
Average number of full nodes in a binary search tree
Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.
Determine the values of $f(0)$ and $f(1)$.
Given that for $N > 1$,
...
2
votes
1answer
425 views
Average number of comparisons to locate item in BST
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items ...
1
vote
0answers
38 views
How to identify a binary tree uniquely if its Inorder, Preorder and Postorder traversal is given? [duplicate]
Possible Duplicate:
Which combinations of pre-, post- and in-order sequentialisation are unique?
I have three different tree traversal of a binary tree Inorder, Preorder and Postorder. I ...
2
votes
1answer
62 views
How to make a parse tree for the following propositional logic formula?
I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.
As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree ...
4
votes
1answer
654 views
Best-Case Running Time For Binary Search Tree Insertion
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:
The term best-case performance is used in computer science to ...
6
votes
1answer
306 views
Two definitions of balanced binary trees
I have seen two definitions of balanced binary trees, which look different to me.
A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the ...
2
votes
2answers
209 views
Binary Search Tree Property
In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:
Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
...
4
votes
1answer
222 views
From in-order representation to binary tree
Is there a way to reconstruct a binary tree just from its in-order representation?
I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and ...
7
votes
2answers
471 views
What is the average height of a binary tree?
Is there any formal definition about the average height of a binary tree?
I have a tutorial question about finding the average height of a binary tree using the following two methods:
The natural ...
3
votes
1answer
225 views
Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?
I've been given the following problem:
Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:
$\text{Insert}(x)$ – add $x$ to $S$
...
3
votes
2answers
373 views
How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?
Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves.
I think I can do this by induction.
For $h(t)=0$, the tree is ...
4
votes
2answers
217 views
Counting trees (order matters)
As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...
3
votes
1answer
131 views
Maintaining search indices with binary trees
There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.
For each word initially ...
11
votes
1answer
606 views
Why does the splay tree rotation algorithm take into account both the parent and grandparent node?
I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
8
votes
1answer
328 views
Proving a binary heap has $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:
Each new node is inserted via ...
9
votes
2answers
775 views
Proving a binary tree has at most $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?
For people who were following in the ...
6
votes
3answers
542 views
Logarithmic vs double logarithmic time complexity
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?
This is the case when one use for instance van Emde Boas ...
5
votes
1answer
370 views
What is the complexity of these tree-based algorithms?
Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: ...
11
votes
2answers
350 views
Creating a Self Ordering Binary Tree
I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
8
votes
1answer
1k views
Which combinations of pre-, post- and in-order sequentialisation are unique?
We know post-order,
post L(x) => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]
and pre-order
...
8
votes
1answer
884 views
AVL trees are not weight-balanced?
In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.
This question is to ask the same question, but for AVL trees.
The question is, ...
16
votes
2answers
1k views
Counting binary trees
(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)
Looking at Wikipedia page for Binary Trees, I've noticed this ...
14
votes
2answers
777 views
Not all Red-Black trees are balanced?
Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.
Of course, when we talk about red-black trees*(see ...
