Do you know, please, if **C++ STL** contains a **Binary Search Tree (BST)** implementation, or if I should construct my own BST object?

In case STL conains no implementation of BST, are there any libraries available?

**My goal** is to be able to find the desired record as quickly as possible: I have a list of records (it should not be more few thousands.), and I do a per-frame (its a computer game) search in that list. I use unsigned int as an identifier of the record of my interest. Whatever way is the fastest will work best for me.

`std::set`

and `std::map`

are usually implemented as red-black trees, which are a variant of binary search trees. The specifics are implementation dependent tho.

STL's set class is typically implemented as a BST. It's not guaranteed (the only thing that is is it's signature, `template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;`

) but it's a pretty safe bet.

Your post says you want speed (presumably for a tighter game loop).

So why waste time on these slow-as-molasses O(lg n) structures and go for a hash map implementation?

What you need is a way to look up some data given a key. With the key being an `unsigned int`

, this gives you several possibilities. Of course, you could use a `std::map`

:

```
typedef std::map<unsigned int, record_t> my_records;
```

However, there's other possibilities as well. For example, it's quite likely that a ** hash map would be even faster** than a binary tree. Hash maps are called

`unordered_map`

in C++, came in wide distribution with TR1 (`std::tr1::unordered_map`

), and will be part of the upcoming new C++ standard (`std::unordered_map`

), likely already supported by your compiler/std lib. If your keys are rather closely distributed, you might even use a simple ** array** and use the key as an index. When it comes to raw speed, nothing would beat indexing into an array. OTOH, if your key distribution is too random, you'd be wasting a lot of space.

If you store your records as ** pointers**, moving them around is cheap, and an alternative might be to keep your data sorted by key in a vector:

```
typedef std::vector< std::pair<unsigned int, record_t*> > my_records;
```

Due to its better data locality, which presumably plays nice with processor cache, a simple `std::vector`

often performs better than other data structures which theoretically should have an advantage. Its weak spot is inserting into/removing from the middle. However, in this case, on a 32bit system, this would require moving entries of 2*32bit POD around, which your implementation will likely perform by calling CPU intrinsics for memory move.

Similar Questions

So, here i have come up with Binary search tree prgram, where i am creating 2 binary trees tmp and tmp2, where i am trying to copy whole tmp2 to tmp, the node which is taken as input from user. But i

I'm trying to learn data structures myself and I'm struggling to understand how the remove method should work for a Binary Search Tree. I'm following the example from Data Structures and Algorithms -

I have programmed a binary search tree with method Add(). But it is not working. When I add number to the tree, root is still empty. Why? EDIT: Code on pastebin, here I am havig some problems with dis

I already have implemented display of binary search tree . Here's the code , which paints the binary tree in a jpanel . public void paint(Graphics g) { super.paint(g); System.out.println( in paint)

I've been trying to implement a binary search tree in C for a few hours now, and I narrowed down my main problem to the insertion function, which you see below. What appears to be the problem is that

I was trying to implement binary search tree but I think I have made a mistake in my insert function. Here's my code #include<iostream> #include<memory.h> #include <cstddef> using na

I have a binary tree that I need to search through. I'm not searching for one specific node of the tree, but rather over every node of the tree to gain information about them. I have a simple recursiv

i have implement binary search tree in c++ #include <iostream> #include <cstdlib> using namespace std; class binary{ private: struct tree{ tree *left; tree *right; int data; }; tree *root;

I implemented binary tree data structure in Haskell. My code: module Data.BTree where data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Eq, Ord, Read, Show) emptyTree :: a -> Tree a empt

I came across a problem stating For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be

I'm trying to eliminate any memory leaks in in my Binary Search tree that I'm making so I made a simple recursive delete method. This is the method that first causes void BST::copy(const BST& othe

I'm working on a problem for class I'm stuck on. It involves adding a methods to the Binary Search Tree found here: http://algs4.cs.princeton.edu/32bst/BST.java.html I need to develop an iterative cei

I am working on some binary tree algorithms and need a find node with searchindex... function. The design for treenodes is basically class TreeNode { int index; // some identifier TreeNode *left; Tr

I have already put in the following methods for a binary search tree: import java.util.Collections; import java.util.NoSuchElementException; import java.util.ArrayList; public class MyTree { private c

I am having trouble finding the smallest element of a binary search tree. I have some code finished, but it is not working. public T getMinElement(TreeNode<T> node) { //TODO: implement this if (

Here is a code I wrote for a binary search tree. Unfortunately, when I run it, it does not give th edesired output. Can someone tell me what I am doing wrong. import java.util.ArrayList; public class

I am trying to define a simple binary search tree. It is stored in lists like so: [Key, Left Tree, Right Tree]. I'm having issue with my logic. This is what I have bstadd(K, [], [K,[],[]]). bstadd(K,

I want to implement a insertion method for a Binary search tree, and come up with a solution below. I know there are plenty of code examples but I wonder what is the problem in my implementation? Or i

I am doing homework and I am try to implement some binary search tree functions. I am also very new to programming, and do not have much experience with programming. I have the functions written out,

Hi all I am working on a class project using binary search trees. I am having trouble trying to find the nth node of the binary search tree. I understand the concept of using in order traversal and us

I've been trying to create a recursive method that will create a full binary search tree. This method returns a reference to the root of this tree. As parameters I'm passing the depth of the tree as w

I want to find the max depth of binary search tree. I found a code. int maxDepth(struct node* node) { if (node==NULL) { return(0); } else { // compute the depth of each subtree int lDepth = maxDepth(n

I am trying to connect the siblings of the binary search tree. You can find the logic in the Connect() method. My question is, is there any better way to do it? Am I overdoing by using two queues to i

I have an theoretical question about Balanced BST. I would like to build Perfect Balanced Tree that has 2^k - 1 nodes, from a regular unbalanced BST. The easiest solution I can think of is to use a so

I have to implement a binary search tree using C++ for one of assignments. I've created the class, and attempted to implement the InsertItem, PrintTree, DeleteTree methods for the class, I think I did

First, I have already read C++ Binary Search Tree status access violation error with adding nodes and Inserting in a binary search tree access violation error but am still having trouble fully impleme

I want to store some values in a balanced binary search tree using C#. I looked through the collections in the generics namespace and I haven't found an equivalent of the stl set. What generic collec

I'm having trouble writing code to determine if certain data is present in my tree, this is the BinaryTreeNode class class BinaryTreeNode { public: Data * nodeData; BinaryTreeNode * left; BinaryTreeNo

I'm currently having difficulty inserting a node into a binary tree using recursion. I've been dwelling on this problem for a few days now and thought it was time I came looking for answers! Node clas

This is a follow up to Is a list implementation of binary tree scalable? What can be the advantages or disadvantages of tree implementation done using linear array(stl vector) or stl deque rather tha

What exactly is the point of having a key-value pair in a binary search tree? Can someone give an example of one such instance? Because in the stl set container, I don't explicitly assign a key-value

I need help with a binary search tree. Here are the node and BST classes : public class Node { private int key; private Node parent; private Node leftChild; private Node rightChild; public Node(int ke

I have a binary tree of node containing an integer and a char. I'm working on Huffman Coding and I want to get the binary presentation of the nodes. A '0' is appended to the string for every left bran

I'm currently working on a school project. The assignment is to write the implementation of a templated binary search tree given the corresponding header file. My issue is that since it's templated,

Ok, I am trying to get a binary search tree to balance, and I know why it's not working, but I don't know how to fix it. This is what I have for my balancing methods. public void balance(){ if(isEmpt

My Binary Search Tree program doesn't seem to be deleting anything when I call the deleteNode method. The BST is built perfectly, its just deleting the node part that doesn't work. I call it from my m

For starters this is homework, I just really need help with a binary search tree. The program is to display polymorphism, using person as an abstract base class, and other types of people which inheri

Please help I've been trying to generate a random binary search tree of size 1024 and the elements needs to be random sortedset ... I'm able to write a code to create a binary search tree manually by

Im trying to build an array based, Binary Search Tree by following the algorithm at: http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/2532

http://pastebin.com/dN9a9xfs That's my code to print out the elements of a binary search tree. The goal is to display it in level order, with slashes connecting the parent to each child. So for instan

So I've stumped on this current problem I'm working on. Basically, I need to add an element to my array based binary search tree. According to my text it is similar to the compareTo method. I'm not ev

First i Wrote this record : type PNode = ^Tree; Tree = record key : Integer; left,right : PNode; end; function TForm1.TreeInit(key: Integer): PNode; var Head : PNode; begin Head := nil; New(Head); Hea

I'm implementing the insert function of a BST, below is my code: data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq) tinsert :: Tree a -> a -> Tree a tinsert Empty a = Branch a

Suppose I have a list of strings and a prefix tree of those strings, and I would like to locate a string given a key, which one is more faster? binary search or prefix tree search? Why and what's the

This question already has an answer here: What kind of tree implementation is STL set? 1 answer In cplusplus.com, in the reference page of std::set, you can read the following: Sets are typica

I have a problem with finding the second maximum element in a binary search tree. I do not know why but in some cases my programm crashes or gives incorrect answer (I don't know those cases). Help me

Here is a c++ function to create a BST tree from an array of integers? It's simple. Take first element ,make root. Take next array element and insert it into the tree. Why is the loop starting from i=

I'm implementing an AVL Tree (a self-balancing Binary Search Tree) in PHP and have things working pretty normally. I have in-order, pre-order, and level-order iterators working, but I can't figure out

I implemented a search function of elements of the list that it was a binary search returns the index of the element found. My curiosity is to have a method of the binary search you could print all oc

I was wondering if we can use a binary search tree to simulate heap operations (insert, find minimum, delete minimum), i.e., use a BST for doing the same job? Are there any kind of benefits for doing