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

learn more… | top users | synonyms

-4
votes
0answers
15 views

what are balanced tree , can some one please give some information with examples

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1. A binary tree is ...
3
votes
1answer
36 views

Can the height of a binary search tree be less than that of a red-black tree?

This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne. "Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than ...
-1
votes
1answer
40 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
3
votes
0answers
47 views

Upper bound complexity for a tree's particular property

I want to determine if in a given binary tree whose nodes are integers, left subtree's (let's call it L) nodes are multiples of (at least one) right subtree's (R) node(s). I only require ...
3
votes
1answer
41 views

Delete a consecutive range of leaves from a binary tree

Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values). I want to delete a consecutive interval of ...
2
votes
1answer
27 views

Maximal number of rotations after deleting a node in an AVL tree

What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones. I know that it is $O(\log n)$ but I'm trying to find a more ...
1
vote
0answers
46 views

Minimize the depth of a tree of computation

Assume you have a binary tree of additions, where each two nodes are added together until the root is the sum of all the nodes. For example: ...
0
votes
1answer
23 views

Print Binary Tree Diameter Path [duplicate]

Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT. Print the Longest leaf to leaf path in a binary tree and its ...
1
vote
2answers
42 views

Maximal difference of height between two leaves in an AVL tree

What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference. I am not sure about my answer - I think that it is $O(\log n)$, given the ...
4
votes
3answers
58 views

Depth first or breadth first ordering in binary search trees?

Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array. The binary tree is full on ...
2
votes
1answer
53 views

Prove that every thin AVL tree may be converted to red-black tree

Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$. I am trying to prove that every thin AVL ...
-1
votes
1answer
55 views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
1
vote
2answers
96 views

AVL tree such that each insert causes rotation (single or double)

Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)? I have tried to come up with an example, but I ...
0
votes
1answer
24 views

Identify balanced and full binary search tree insert order

I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create ...
0
votes
1answer
33 views

Find the longest possible path in full binary tree

Given the depth of the tree, I need to calculate the longest possible path in the full binary tree (also known as the diameter). When attempting this problem, I experimented with what the depth has ...
0
votes
0answers
14 views

What is the weight-balanced tree rebalancing algorithm?

Is there a specific algorithm called the weight-balanced tree rebalancing algorithm? From what I understand, this could be rotating left and right?
1
vote
2answers
69 views

Effective finding height of avl tree

I am searching effective way to find out height of AVL tree. In each node there is balance factor ($bf$). $$bf(root)=height(root.left) - height(root.right). $$ And now we can find height in $O(\log ...
0
votes
1answer
52 views

Successor of 6 is 7 or 9? [closed]

What is the successor of 6 in this tree: 7 or 9?
1
vote
0answers
44 views
2
votes
0answers
39 views

Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
5
votes
2answers
69 views

Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
1
vote
1answer
11 views

How to Apply Binary Transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
2
votes
1answer
29 views

Sum of heights in a complete binary tree (induction)

I need to prove the following statement using induction on the number of nodes in the tree: The sum of heights of a complete binary tree is $\theta(n)$. Note: I've tried proving this using ...
0
votes
1answer
47 views

Example of height-balanced tree that is not weight-balanced

Following this question : Two definitions of balanced binary trees I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is ...
5
votes
1answer
74 views

Huffman Code VS Hu–Tucker Code

Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background. Huffman Code is the binary-code ...
1
vote
0answers
87 views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
1
vote
1answer
36 views

Proof that there are same number rotation moves in any binary tree with both children compulsory

I am working on this project where I am required to find the theoretical proof for following. I have a particular type of binary trees, where 1) each internal node will definitely have two children. ...
3
votes
0answers
99 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
1
vote
2answers
170 views

AVL Trees Height-Balance Property

An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1. Below is an example AVL tree. ...
0
votes
1answer
132 views

augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?

How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given. Example: contain of tree: $1, 4, 5, 3, 8, 45, 532$ $d=5$, answer: $yes$, there is pair $(5,8)$ $d=52$ ...
3
votes
1answer
42 views

Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$

I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how: Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
0
votes
1answer
52 views

Binary tree algorithm asymptotic analysis problem

Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child ...
1
vote
1answer
36 views

Bounds on the number of rotations in the insertion operation of a Red Black Tree

I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree. From ...
-1
votes
1answer
56 views

How to find a symmetric predecessor / successor [closed]

Lets say we have a binary tree $T$ and we want to insert key $k$. Now, assuming $k\not\in T$, how do we find the symmetric predecessor/successor of $k$? Does this relate to (pre/in/post)-order ...
1
vote
1answer
259 views

How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
4
votes
1answer
174 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
0
votes
1answer
34 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
1
vote
2answers
219 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
0
votes
1answer
66 views

Binary tree node value maximization

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be ...
2
votes
1answer
481 views

What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...
2
votes
2answers
38 views

Worst case bisection of binary tree

My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices. ...
0
votes
0answers
129 views

How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
1
vote
1answer
48 views

Are there any theorems/formulas that apply to the height of comparison trees?

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an ...
2
votes
0answers
32 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
0
votes
1answer
47 views

What does every root is at the same level mean

My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level. My conceptual understanding: All this time, I was led by my textbook to believe a root is ...
6
votes
1answer
227 views

Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
2
votes
1answer
372 views

How to solve a Simple Linear Equation using a binary tree data structure

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so: ...
-1
votes
1answer
64 views

What do you mean by minimum height of a Binary Search Tree? [duplicate]

I came across the term "minimum height of a Binary Search Tree" (in Java) in class, but I don't fully understand. Could someone please elaborate on: (a) What it is ? (b) How to ...
0
votes
0answers
121 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
1
vote
1answer
118 views

Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is ...