Questions tagged [binary-search-trees]
The binary-search-trees tag has no usage guidance.
157
questions
-3
votes
1
answer
8k
views
Constructing binary search tree from given data
The data are in alphabets.
U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A.
Perform pre, in and post order traversals.
I'm confused as how to construct it in the 1st place. Only sense i ...
- 1
1
vote
2
answers
729
views
Why do we use multiple data structures? [duplicate]
I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees.
Both runs in worst case O(n) in the same operations, so why don't we use only ...
- 133
2
votes
1
answer
1k
views
Should all internal node keys in B+ tree also be in the leaves?
I was reading about B+ tree insertion.
The algorithm takes following form:
Insert the new node as the leaf node.
If the leaf node overflows, split the node and copy the middle element to the parent ...
- 1,745
2
votes
1
answer
3k
views
Facts about internal and external path lengths of binary tree
While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.
My book specifies some ...
- 1,745
0
votes
0
answers
70
views
Find keys between $x$ and $y$ in binary search tree
Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
- 101
3
votes
1
answer
551
views
Binary Search Tree Traversal output validity and unique BST construction
I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :
Given x-order traversal output of BST, can we state if it is valid or invalid output?
(For ...
- 1,745
5
votes
1
answer
1k
views
What is the advantage of leaf trees vs. node trees?
In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine):
"...two different models ...
- 225