Questions tagged [binary-trees]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
9k 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 $O(...
1
vote
1answer
369 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 ...
1
vote
1answer
319 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 ...
12
votes
1answer
17k 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 ...
10
votes
3answers
48k 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 ...
3
votes
1answer
398 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 ...
6
votes
1answer
28k views

What is the depth of a complete binary tree with $N$ nodes?

This question uses the following definition of a complete binary tree†: A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level ...
1
vote
1answer
2k 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$, $\qquad \...
3
votes
3answers
20k 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
467 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 want to ...
3
votes
1answer
5k 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 ...
5
votes
1answer
17k 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 ...
27
votes
1answer
48k 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 number ...
3
votes
2answers
481 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
586 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 ...
10
votes
2answers
4k 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 ...
5
votes
1answer
486 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$ $\...
4
votes
2answers
2k 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
516 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
376 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 ...
25
votes
1answer
5k 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 ...
17
votes
2answers
14k 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 ...
14
votes
2answers
6k 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 ...
9
votes
3answers
5k 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
493 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: ...
20
votes
2answers
830 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 ...
31
votes
1answer
9k 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 ...
22
votes
1answer
5k 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, ...
29
votes
2answers
11k 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 ...
30
votes
2answers
8k 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-...
35
votes
2answers
23k views

Hash tables versus binary trees

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
20
votes
5answers
553 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...

1
6 7 8 9
10