Questions tagged [binary-trees]
a tree in which each node has no more than two children
391
questions
3
votes
1answer
42 views
Are all data structures in the von Neumann architecture based on the array, or array-like?
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
1
vote
1answer
30 views
question about the construction of BSTs using a repeated sequence of rotations
How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).
0
votes
0answers
6 views
Performing crossover on trees in genetic algorithm
I'm using genetic algorithm for solving a problem. Each chromosome is a B* tree (where each node has only 2 child nodes).
I'm wondering how to perform the crossover. I found an example which says ...
2
votes
1answer
96 views
Height of epsilon-balanced binary search tree
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:
For example, one can say, a BST is balanced, if each subtree has at
most epsilon * n nodes, ...
0
votes
1answer
30 views
Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
3
votes
1answer
106 views
Distinct Binary Heaps
I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.
My analysis : I started ...
2
votes
1answer
76 views
Algorithm to find longest path in a tree that is smaller than x
Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...
0
votes
0answers
20 views
AVL Tree confusion
I have some confusion with regards to AVL trees and the heights of various subtrees.
When initially reading the overview of the algorithms purpose(to keep the tree balanced) I thought it put limits ...
0
votes
1answer
32 views
Is the tree shown a valid red-black tree?
I have made a red-black tree and I think that it is not valid. Could someone please verify?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
1
vote
1answer
45 views
How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$
I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a ...
1
vote
0answers
33 views
Transforming an immutable binary tree without recursion [closed]
I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case ...
0
votes
0answers
30 views
If insertion/deletion from a binary tree is efficient, while maintaining ability to get item by index
I can't quite figure this out. Say you have a binary tree where the left or right nodes correspond to 0 or 1 and a group of levels form a chain which is the index of the node. So you have 10010 which ...
2
votes
2answers
46 views
Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:
The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.
We define "...
4
votes
1answer
50 views
Nodes in a binary search tree that span a range
I have a binary search tree of height $h$ with an integer in each leaf. I also have a range $[\ell,u]$. I want to find a set of nodes that span the range $[\ell,u]$, i.e., a set $S$ of nodes such ...
3
votes
1answer
65 views
Finding $k$-th element in prefix of size $i$
Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
11
votes
4answers
3k views
Can the pre-order traversal of two different trees be the same even though they are different?
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.
It is also mentioned that the in-order ...
2
votes
3answers
386 views
Do height-balanced binary trees have logarithmic depth?
A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.
Given a family of trees such that for every tree $t$ in the family, for every node $...
2
votes
0answers
18 views
Nested dissection vs kd-tree
Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
2
votes
2answers
149 views
Average codeword length in a Huffman tree is $\Omega(\log n)$
Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.
My try:
I think that the worst case is when the tree is full and all the ...
1
vote
1answer
36 views
Number of nil-links in a binary tree
In its section Properties of binary trees Wikipedia states:
The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is (n+1), where only ...
0
votes
0answers
23 views
Do parent pointers affect path-copying in a persistent binary tree?
I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
1
vote
1answer
106 views
Finding longest subset arithmetic progression with given difference
Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.
For example, given D = 5, with the set of numbers 1, 5, ...
1
vote
1answer
40 views
Self-balancing binary search tree optimized for insertion
I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable ...
0
votes
1answer
124 views
Bin packing first-fit problem in $O(n \log n)$ time
Suppose we have $n$ objects with weights $w_i \in (0,1]$ and we must
insert them into bins with the constraint that every bin must contain
objects which weight less than $1 \, kg$.
The first-...
1
vote
3answers
188 views
Why is Binary Heap never unbalanced?
My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
0
votes
0answers
25 views
Finding Binary Search Tree Height, What happens to duplicates?
I'm going over past exam papers with this question:
The answer to a). will be (height of 5):
For b.):
I assume the height function will be to find the height of the tree. So, I will have to compare ...
2
votes
1answer
46 views
Logic of multiple variables in ILP
Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
1
vote
2answers
115 views
Difficulty understanding the solution of heap problem in CLRS book?
I am reading the solution of this problem in CLRS:
Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.
Solution: All the nodes of height $h$ ...
1
vote
2answers
112 views
Random walks on Complete Binary Trees
Let $T$ be a complete binary tree of height $n$ and root $r$.
A random walk starts at $r$, and at each step uniformly at random moves on a neighbor.
There are $m$ random walkers all starting at $r$ ...
0
votes
0answers
79 views
Binary search on a path of minimum heap
WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H.
The function is executing a binary search on a path of a heap.
Assumption: We have the specific path because it ...
1
vote
1answer
341 views
AVL tree worst case height proof
The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.
1
vote
2answers
114 views
Build a balanced binary tree from list in linear time
I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in ...
0
votes
0answers
31 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
2
votes
1answer
62 views
Merging of two increasing binary trees why do we exchange left and right subtree
We say that a binary tree : $B(l, x, r)$ is increasing if $x$ is smaller than all the nodes of the binary tree and if $l$ and $r$ are also increasing trees.
One way to merge these kind of trees is as ...
1
vote
2answers
58 views
Minimal, “natural” set of operations to manipulate a binary tree
Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the ...
0
votes
0answers
51 views
Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers
So you can store a binary tree without pointers using a 1-D array:
Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :
The values of ...
2
votes
1answer
66 views
Prove number of nodes in heap
Consider a variation of the normal heap which we will call the x-heap
The x-heap of height $h$ has the following properties:
It will have $2^h$ nodes
A height of $0$ corresponds to the single root ...
1
vote
1answer
305 views
$O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree
I'm having trouble making an algorithm to fit these specs:
Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
Reading the leaves from left to right makes a sequence of integers (...
2
votes
1answer
39 views
Binary Tree Multithreaded Time Complexity
Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then ...
2
votes
1answer
71 views
Algorithm to find the two closest elements in a BST
For example, consider an AVL tree:
Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, ...
1
vote
1answer
77 views
Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.
Consider the following ...
0
votes
0answers
45 views
Binary tree for 2 elements
I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?
If I want to search for an element 2, it will make 2 comparisons. If I want to search for an ...
2
votes
0answers
35 views
Documentation of “bin number” trees
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
5
votes
2answers
401 views
What is the point of traversing a binary tree in preoder, inorder or postorder?
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
1
vote
1answer
60 views
AVL Rotations Abbreviations
I read that there are 4 types of rotations:
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
1
vote
1answer
59 views
Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
1
vote
1answer
44 views
Binary trees and preallocated nodes
I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the ...
1
vote
1answer
414 views
AVL Tree rotations : How to balance below AVL Tree with imbalance at root node
How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the ...
1
vote
1answer
59 views
Searching in a Binary Search Tree
I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.
For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59].
Binary Search Tree for S, with ...
1
vote
1answer
25 views
Running time based on smallest subtree
I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More ...
