changelog shortlog graph tags branches changeset files revisions annotate raw help

Mercurial > core / lisp/lib/obj/tree/bro.lisp

changeset 698: 96958d3eb5b0
parent: 4ba88cac5bc7
author: Richard Westhaver <ellis@rwest.io>
date: Fri, 04 Oct 2024 22:04:59 -0400
permissions: -rw-r--r--
description: fixes 
     1 ;;; lib/obj/tree/bro.lisp --- Brother Tree
     2 
     3 ;; support for SBCL's 1-2 brother tree implementation.
     4 
     5 ;; ref: https://www.cs.ox.ac.uk/ralf.hinze/publications/Brother12.pdf
     6 
     7 ;; in general these are better than redblack trees
     8 
     9 ;; An element of type Tree T is called a brother tree iff:
    10 
    11 ;;   - a :: all nullary nodes have the same depth (height condition)
    12 
    13 ;;   - b :: each unary node has a binary brother (brother condition)
    14 
    15 ;; This implies that the root of a brother tree is not unary and that
    16 ;; a unary node has not a unary child. Put positively, a unary node
    17 ;; only occurs as the child of a binary node. 
    18 
    19 ;; -- Ralf Hinze, Purely Functional 1-2 Brother Trees
    20 
    21 ;;; Code:
    22 (in-package :obj/tree)