Data Structures and Algorithms
Primary version
Primary version
  • Data Structures and Algorithms
  • Algorithms Analysis
    • Measuring Resource Consumption
    • Growth Rates
    • Asymptotic Notation
    • Analysis of Linear Search
    • Analysis of Binary Search
    • How to do an analysis in 5 steps
  • Recursion
    • Writing a recursive function
    • How do recursive functions work?
    • Analysis of a Recursive Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Concepts
      • Implementation - List and Nodes
      • Implementation - push_front(), pop_front()
      • Implementation - Iterators
      • Modification - Sentinel Nodes
  • Stacks and Queues
    • Stack Implementation
    • Queue Implementation
  • Table
    • A Simple Implementation
    • Hash Tables
      • Bucketing
      • Chaining
      • Linear Probing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
    • Quick Sort
    • Heap and Heap Sort
      • Priority Queues using Binary Heaps
      • Heapify and Heap Sort
  • Trees
    • Binary Trees
    • Binary Search Trees
    • BST Implemenation
    • Iterative Methods
    • Recursive Methods
  • AVL Trees
  • Red Black Trees
  • 2-3 Trees
  • Graphs
  • Introduction to Computational Theory
  • Appendix: Markdown
  • Appendix: Mathematics Review
Powered by GitBook
On this page

2-3 Trees

PreviousRed Black TreesNextGraphs

Last updated 6 years ago

A 2-3 Tree is a specific form of a B tree. A 2-3 tree is a search tree. However, it is very different from a binary search tree.

Here are the properties of a 2-3 tree:

  1. each node has either one value or two value

  2. a node with one value is either a leaf node or has exactly two children (non-null). Values in left subtree < value in node < values in right subtree

  3. a node with two values is either a leaf node or has exactly three children (non-null). Values in left subtree < first value in node < values in middle subtree < second value in node < value in right subtree.

  4. all leaf nodes are at the same level of the tree

Insertion

The insertion algorithm into a two-three tree is quite different from the insertion algorithm into a binary search tree. In a two-three tree, the algorithm will be as follows:

  1. If the tree is empty, create a node and put value into the node

  2. Otherwise find the leaf node where the value belongs.

  3. If the leaf node has only one value, put the new value into the node

  4. If the leaf node has more than two values, split the node and promote the median of the three values to parent.

  5. If the parent then has three values, continue to split and promote, forming a new root node if necessary

Example:

Insert 50

Insert 30

Insert 10

Insert 70

Insert 60