A *binary search tree* is a data structure that stores information in a logical hierarchy.

A binary search tree is comprised of a key and two indicators. The *key* represents the data you would like to store, such as string or scalar value. Typically represented with pointers, the indicators store the location (also called the address) of its two children. The *left* child contains a value that is smaller than its parent. Conversely, the *right* child contains a value greater than its parent.

The same list (example below) visualized as a balanced BST. It does not matter that the values are unsorted. Rules governing the BST will place each node in its “correct” position accordingly.

Implementation below:

import Cocoa /* A binary search tree is a data structure that stores information in a logical hierarchy. A binary search tree is comprised of a key and two indicators. The key represents the data you would like to store, such as string or scalar value. Typically represented with pointers, the indicators store the location (also called the address) of its two children. The left child contains a value that is smaller than its parent. Conversely, the right child contains a value greater than its parent. */ public class AVLTree <T: Comparable> { var key: T? var left: AVLTree? var right: AVLTree? var height: Int = 0 // Add item func append(element key: T) { // Check root guard self.key != nil else { self.key = key self.height = 0 return } // Check left side if key < self.key! { if self.left != nil { left?.append(element: key) } else { // New element let leftElement = AVLTree() leftElement.key = key leftElement.height = 0 self.left = leftElement } } // Check right side if key > self.key! { if self.right != nil { right?.append(element: key) } else { // New element let rightElement = AVLTree() rightElement.key = key rightElement.height = 0 self.right = rightElement } } } } // A simple array of unsorted integers let numbers: Array<Int> = [8, 2, 10, 9, 11, 1, 7] // Create a new BST instance var root = AVLTree<Int>() // Sort each item in the list for number in numbers { root.append(element: number) } print(root)

^{<Example from Swift Algorithms & Data Structures by Wayne Bishop>}