Binary search tree

As explained in Learn C++ by Example

A binary search tree is a binary tree whose nodes are ordered so smaller elements lie to the left and larger elements lie to the right.

A binary search tree stores nodes with at most two child branches. Ordering places smaller elements on the left and larger elements on the right, allowing searches to discard half the tree at each step. section 7.2.1

Searching map keys

A map can store {1:a}, {3:c}, and {5:e} in a balanced binary search tree. Searching for {2:b} starts at {3:c}, moves left to {1:a}, and stops at the leaf. Balanced search, insertion, and removal take logarithmic complexity, O(log(n)). section 7.2.1

Figure 7.2 Three elements in a balanced binary search tree: nodes with smaller keys go on the left and larger keys on the right.

Use the tree diagram to see how smaller keys occupy the left side and larger keys occupy the right side. section 7.2.1

How Learn C++ by Example covers it

How deep it goes

Defines nodes, branches, ordering, balancing, and logarithmic operations through a small map example.

Examples

Uses map pairs {1:a}, {3:c}, and {5:e}, then traces a search for {2:b}.

What it assumes

Assumes familiarity with map elements and vector scanning while defining binary-tree terminology directly.

What you can do after

Understand why balanced ordered storage reduces map search, insertion, and removal from linear to logarithmic complexity.

How it connects

Connects binary trees with map, keys, balanced trees, vector search, and logarithmic complexity.

liveBookmanning.com

Read Learn C++ by Example on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Data StructuresA binary search tree is a binary tree whose node values obey an ordering rule in which left-subtree values are less than or equal to a node value and right-subtree values are greater.
• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA binary search tree is a binary tree organized by an ordering relation that places smaller and larger keys in designated subtrees.
• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionA binary search tree is a binary tree whose nodes are ordered so that values in the left subtree precede the node's value and values in the right subtree follow it.
• 

  liveBookmanning.com
  LatencyA binary search tree is an ordered tree data structure in which values in each subtree follow a binary-search ordering relative to its node.

Compare how 5 books explain binary search tree →

Related concepts

• binary treekind of · A binary tree is a tree data structure in which each node has at most two children.
• self-balancing binary search treeincludes · A self-balancing binary search tree automatically maintains bounded, typically logarithmic height as elements are inserted or removed.
• k-d treeincludes · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
• subtreehas part · A subtree is a tree formed by a node and all its descendants, together with the links connecting them.
• Mapimplements · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
• similarity searchuses · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.

This explainer was generated by Manning's knowledge graph from the text of Learn C++ by Example. The section links point to the parts of the book it draws on.