11.2. 2-3 Trees¶
11.2.1. 2-3 Trees¶
11.2.1.1. 2-3 Tree¶
- A 2-3 Tree has the following properties:
A node contains one or two keys
Every internal node has either two children (if it contains one key) or three children (if it contains two keys).
All leaves are at the same level in the tree, so the tree is always height balanced.
The 2-3 Tree has a search tree property analogous to the BST.
11.2.1.2. 2-3 Tree Example¶
The advantage of the 2-3 Tree over the BST is that it can be updated at low cost.
