-- |
-- Module      : Data.RedBlackTree
-- Copyright   : (c) 2017 Gabriel Aumala
--
-- License     : BSD3
-- Maintainer  : gabriel@criptext.com
-- Stability   : experimental
-- Portability : GHC
--
-- A Red Black Tree is a self balancing binary search tree in which each node has a
-- color: red or black. Everytime a node is inserted, the tree performs rotations
-- and repaints nodes to ensure the following properties about the tree:
--
-- 1. Each node is either red or black.
-- 2. The root node is black.
-- 3. All leaves (empty nodes at the bottom of the tree) are black.
-- 4. If a node is red, then both its children are black.
-- 5. Every path from a given node to any of its leaf nodes contains the same
-- number of black nodes (black height).
--
-- As long as these properties remain true, the tree is balanced. Balancing is
-- not perfect, but it is good enough to ensure O(log(n)) lookup and insertion.

module Data.RedBlackTree (
  -- * Data Structure definitions
  RedBlackTree,
  BinaryTreeNode (mergeNodes),

  -- * Creation
  emptyRedBlackTree,
  -- * Operations
  find,
  insert,
  getBlackHeight,

) where

import Data.RedBlackTree.BinaryTree
import Data.RedBlackTree.Internal
import Data.RedBlackTree.InsertionAlgorithm (insert)