diff options
author | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-13 00:01:28 +0200 |
---|---|---|
committer | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-13 00:01:28 +0200 |
commit | a82b6c772089aa46e30c6c89ef48f514294df3cb (patch) | |
tree | e25d9b6fd1fefe8b6ac293a5c0b53293872a8f54 /doc/ref/general/bst.texi | |
parent | Add basic documentation for lens. (diff) | |
parent | Even more documentation. (diff) | |
download | calp-a82b6c772089aa46e30c6c89ef48f514294df3cb.tar.gz calp-a82b6c772089aa46e30c6c89ef48f514294df3cb.tar.xz |
Merge branch 'next' into datarewrite-structures
Diffstat (limited to 'doc/ref/general/bst.texi')
-rw-r--r-- | doc/ref/general/bst.texi | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/doc/ref/general/bst.texi b/doc/ref/general/bst.texi new file mode 100644 index 00000000..d2bba0ff --- /dev/null +++ b/doc/ref/general/bst.texi @@ -0,0 +1,37 @@ +@node Binary Search Tree +@section Binary Search Tree + +A simple ``read only'' binary search tree. + +@defun make-tree pred? lst +Constructs a new tree. @var{pred?} should be a procedure taking the +first element of @var{lst}, along with each element, and should return +a boolean value indicating if the specific element should go in the +left or right subtree. (left subtree is ``truthy'' values). + +This operation is done recursively. +@end defun + +@defun tree-node tree +Return the value of a tree node. +@end defun + +@defun left-subtree tree +Return all ``truthy'' children of tree node. +@end defun + +@defun right-subtree tree +Return all ``falsy children of tree node. +@end defun + +@defun length-of-longest-branch tree +Get the depth of a tree. +@end defun + +@defun tree-map proc tree +Apply proc onto the value of every node in tree, keeping the structure +of the tree. + +@b{Note:} this can cause the tree to no longer be a binary search +tree, but simply a ``formless'' binary tree. +@end defun |