BST

Short for: Binary Search Tree

Data structure is made up of nodes. Usually looks something like this:

type bstNode<'T> =
  { Value: 'T
    Left: bstNode<'T> option
    Right: bstNode<'T> option }

Rules

• Every node can have up to 2 children. No more.
• Every node in the .Left branch has a lower value than .Value
• Every node in the .Right branch has a higher (or equal) value than .Value
• Every node is immutable

Benefits

Main benefit is the speed of operations.

Terminology

• A container of a single value and pointers to the next containers is called a “node”.

• The nodes referenced by a node are called “child nodes” and “parent nodes”

• The D node lacks parent, and is therefore called the “root node”.

• The A, C, E, G nodes lacks children, and is therefore are called the “leaf nodes”.

graph TD
    D==>B
    D==>F
    B==>A
    B==>C
    F==>E
    F==>G