Geek Answers Handbook

Std :: map and binary search tree

I read that the std card is implemented using the binary tree data structure.

BST is a sequential data structure (for example, elements in an array) that stores elements in a BST node and maintains elements in their order. E.g. if the element is smaller than the node, save it to the left of the node and if it is larger than the node, save it to the right of the node. With this approach, we achieve O (log n) complexity for various operations such as search, insert, etc.

However, the std card is an associated container. We have a key and a pair of values ​​to insert. Is it really implemented using BST and, if so, how? In BST, we have no key or value. This is a kind of standard container.

I'm a little confused. Please help me provide clarification. This does not affect my work, but I want to understand them better. Thank you for your help.

+4
source share
2 answers

A node on a map usually looks something like this:

struct node
{
    node* left;
    node* right;

    Key_type key;
    Value_type value;
};

You have a general idea of ​​how BST works, as you stated:

if the element is smaller than the node, save it to the left of the node, and if it is larger than the node, save it to the right of the node.

node "" key. , , . , , node, , , , . value , . , .

+9

++ , std::map. , a std::map , .

std::map - .

+1

More articles:


All Articles