diff options
author | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-12 10:23:59 +0200 |
---|---|---|
committer | Hugo Hörnquist <hugo@lysator.liu.se> | 2023-09-12 10:25:14 +0200 |
commit | 108a0454d05c744c4a05e298cfc8cbf157952414 (patch) | |
tree | ca99bed5d49eabfb644c3b1c0a397b1354efdaf3 /doc/ref/general/bst.texi | |
parent | Change overarching structure of info document. (diff) | |
download | calp-108a0454d05c744c4a05e298cfc8cbf157952414.tar.gz calp-108a0454d05c744c4a05e298cfc8cbf157952414.tar.xz |
Rework file tree structure for info files.
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 |