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

learn more… | top users | synonyms

0
votes
0answers
11 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
23 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, ...
-1
votes
0answers
10 views

Proving number of internal nodes in the subtree rooted at any node x of Red Black trees

Reading Lemma 13.1 from the book Introduction to Algorithms, 3rd Edition To prove: A red black tree with n nodes has height at most 2 lg(n+1) First it attempts to prove : the subtree rooted at any ...
0
votes
1answer
24 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 ...
-2
votes
0answers
32 views

AVL-tree rotations

Let's suppose that I delete an item from an AVL-tree and the tree gets unbalanced. Is there more than 1 different set of rotations to get the tree balanced ? Take this example: I have this tree ...
0
votes
2answers
53 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. ...
-1
votes
0answers
32 views

Big O analysis of algorithm used to check for subtree of binary tree

This is the algorithm I used to check if a Binary tree is a subtree of another Assuming A is the pointer to root of Binary tree P and B is the pointer to the root of Binary tree T. Funtion ...
5
votes
4answers
484 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
51 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
95 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
95 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
74 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
128 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
489 views

Print bottom view of a binary tree

For a binary tree we define horizontal distance as follows: ...
1
vote
0answers
41 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
43 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
62 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
223 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
130 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
116 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
202 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
154 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
1k 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
123 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
223 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
42 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
93 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
664 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
319 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
286 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
95 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
56 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
370 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
729 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
60 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
85 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
302 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
522 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
387 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
214 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
2k 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 ...
7
votes
2answers
1k 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. ...
22
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
386 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
400 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
237 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
205 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
345 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 ...