Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [binary-tree]

55 questions
22
votes
6 answers

Which self balancing binary tree would you recommend?

I'm learning Haskell and as an exercise I'm making binary trees. Having made a regular binary tree, I want to adapt it to be self balancing. So: Which is most efficient? Which is easiest to implement? Which is most often used? But crucially, which…
dan_waterworth
  • 7,287
  • 2
  • 34
  • 45
21
votes
4 answers

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please correct me if I am wrong? Thanks in advance!
Srikanth Kandalam
  • 313
  • 1
  • 2
  • 4
13
votes
3 answers

Usefulness of pre and post order traversal of binary trees

This may be very naive, but I was wondering, it the context of binary trees (plain, sorted and balanced), of all the traversal types: depth-first pre-order depth-first in-order depth-first post-order breadth-first what's the actual utility of pre…
Shivan Dragon
  • 4,583
  • 5
  • 24
  • 31
12
votes
3 answers

Do binary trees serve a specific purpose in storing hierarchical data? What is their canonical use?

I understand the structure of binary trees and how to traverse them. However, I am struggling to realize their actual uses, purposes in programs and programming. When I think about 'real life' examples of hierarchical data they almost certainly have…
sw123456
  • 249
  • 1
  • 8
12
votes
2 answers

Is it possible to speed up a hash table by using binary search trees for separate chaining?

I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and if yes then how? It would be easier to…
Aviral
  • 139
  • 1
  • 1
  • 5
7
votes
1 answer

Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?

For the Red-black tree insertion fixup the book distinguishes between 6 cases, 3 of which are symmetric. The cases are (z is the node being inserted): Case 1: z's uncle is red Case 2: z's uncle is black and z is a right child Case 3: z's uncle is…
Bar
  • 173
  • 1
  • 4
6
votes
1 answer

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html I read that…
Meena
  • 161
  • 1
  • 2
5
votes
2 answers

Do you get the benefits of a B-Tree in a managed language?

My understanding is that one of the key features of a B-Tree (and a B+Tree) is that it is designed such that the size of its nodes are some multiple of the block size of whatever media the data is stored on. Considering that, in a memory managed…
Steven Evers
  • 28,200
  • 10
  • 75
  • 159
4
votes
1 answer

Is it worth parsing an infix algebraic expression to postfix and then an expression tree?

I am trying to make a simple expression parser, in which users type an expression in infix notation (for example ln((1+2)(3-4))) to apply some calculations. To make this possible I need to tokenize the expression as a expression tree. I've read in…
JulianSoto
  • 43
  • 5
4
votes
1 answer

Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present Perform in-order operation Perform post-order operation where…
9a3eedi
  • 2,101
  • 3
  • 23
  • 29
4
votes
2 answers

Is this the right strategy to convert an in-level order binary tree to a doubly linked list?

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question. This is the strategy I had - Simply do a pre-order traversal of the tree,…
ankit
  • 860
  • 7
  • 11
3
votes
2 answers

Speed of MySQL type index access vs. binary jump search on a huge file?

I am dead set on moving over to a MySQL database for some huge data sets I'm working with but right now I don't have the time. In the meantime I am curious about a technical performance issue regarding speed between the two methods. Obviously…
Robert Oschler
  • 809
  • 1
  • 10
  • 15
3
votes
2 answers

Is the TreeSet class in java a Red Black Binary Search Tree?

I simply wanted to know if the internal implementation of the TreeSet class in java is Red Black Binary Search Tree. Ideally, I would think that it is a threaded RB-BST, since it supports iteration over the elements stored in it, and this would be…
ShayakSarkar
  • 79
  • 3
3
votes
2 answers

Deleting a node and returning the deleted node's value in a Binary Search Tree?

Hi I have a programming project where I'm basically using a Binary Search Tree to implement a min/max priority queue. I'm having trouble with the popMin/popMax methods. I get how to get the minimum/maximum node and remove a node, but I'm having…
Justin
  • 77
  • 6
3
votes
3 answers

Binary Search Tree without Natural Ordering

This is kind of a multi-part question. Is it possible to do a binary search tree if the data does not possess natural ordering? Would you be forced to impose artificial ordering to such data? Like images? Or executable files? Or video? or sound…
adv
  • 347
  • 1
  • 9
1
2 3 4