Balanced binary tree

As explained in Learn C++ by Example

A balanced binary tree is a binary tree whose height is kept sufficiently even across branches to support efficient operations.

A balanced binary tree keeps its branches sufficiently even. In a binary search tree, smaller keys go left and larger keys go right, so each comparison can discard roughly half the remaining nodes. section 7.2.1

Searching a map

For nodes {1:a}, {3:c}, and {5:e}, placing {3:c} at the top keeps the tree balanced. Searching for {2:b} compares with 3, moves left to 1, and stops. Search, insertion, and removal remain O(log(n)); an unbalanced chain can make searching much slower. 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.

View the three-node layout showing smaller keys on the left and larger keys on the right. section 7.2.1

Figure 7.3 Constant time complexity: O(n) grows much faster than logarithmic complexity, O(log(n)), as the number of elements is increased.

Compare how logarithmic growth scales against linear growth as the number of elements increases. section 7.2.1

How Learn C++ by Example covers it

How deep it goes

Explains branch ordering, rebalancing, and logarithmic complexity, while only briefly identifying red-black tree implementation.

Examples

Uses map nodes {1:a}, {3:c}, and {5:e} to demonstrate rebalancing and searching for {2:b}.

What you can do after

Evaluate why balanced map operations scale logarithmically instead of linearly in the worst case.

How it connects

Connects binary search trees, maps, red-black trees, vector search, and logarithmic complexity.

liveBookmanning.com

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

Related concepts

• heapincludes · A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.
• binary treecontrasts with · 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.

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.