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

learn more… | top users | synonyms

3
votes
1answer
78 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
32 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 ...
1
vote
1answer
31 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
87 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
270 views

Print bottom view of a binary tree

For a binary tree we define horizontal distance as follows: ...
1
vote
0answers
35 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
40 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
51 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
0answers
177 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
116 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
74 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
145 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
133 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
906 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
108 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
179 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
38 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
83 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 ...
-1
votes
1answer
547 views

What is the size of the Perfect binary tree with n nodes in last level

I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be ...
5
votes
2answers
277 views

What linked list data structure adjustments would give me fast random lookup?

I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier. The linked list is created in ...
9
votes
1answer
252 views

How does one efficiently produce all binary sequences with an equal number of 0's and 1's?

A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary ...
-1
votes
1answer
83 views

Find node with key of at least n in a binary search tree

Working on a project for my Data Structures class. I've implemented a Red/Black tree in Java. One of the operations required of the data structure is "find a node which has a key of at least n". The ...
1
vote
0answers
48 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
8
votes
0answers
338 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 ...
0
votes
2answers
670 views

Balancing subproblems in resilience testing

You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, ...
2
votes
1answer
54 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
75 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 ...
7
votes
4answers
286 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
488 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
355 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
183 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
1k 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 ...
6
votes
2answers
985 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. ...
19
votes
1answer
3k 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
361 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
372 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
207 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
177 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
308 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
82 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
419 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
150 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 ...
11
votes
1answer
553 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 ...
2
votes
2answers
2k 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 ...
3
votes
1answer
740 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
170 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
63 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 ...
2
votes
1answer
2k 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
3k 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 ...