diff options
author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
---|---|---|
committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/hyper/pages/BSTREE.ht | |
download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz |
Initial population.
Diffstat (limited to 'src/hyper/pages/BSTREE.ht')
-rw-r--r-- | src/hyper/pages/BSTREE.ht | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/src/hyper/pages/BSTREE.ht b/src/hyper/pages/BSTREE.ht new file mode 100644 index 00000000..8ae762dc --- /dev/null +++ b/src/hyper/pages/BSTREE.ht @@ -0,0 +1,104 @@ +% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved. +% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk. +\newcommand{\BinarySearchTreeXmpTitle}{BinarySearchTree} +\newcommand{\BinarySearchTreeXmpNumber}{9.5} +% +% ===================================================================== +\begin{page}{BinarySearchTreeXmpPage}{9.5 BinarySearchTree} +% ===================================================================== +\beginscroll +\spadtype{BinarySearchTree(R)} is the domain of binary trees with +%-% \HDindex{tree!binary search}{BinarySearchTreeXmpPage}{9.5}{BinarySearchTree} +elements of type \spad{R}, ordered across the nodes of the tree. +%-% \HDindex{binary search tree}{BinarySearchTreeXmpPage}{9.5}{BinarySearchTree} +A non-empty binary search tree has a value +of type \spad{R}, and \spadfun{right} and \spadfun{left} +binary search subtrees. +If a subtree is empty, it is displayed as a period (``.''). + +\xtc{ +Define a list of values to be placed across the tree. +The resulting tree has \spad{8} at the root; +all other elements are in the left subtree. +}{ +\spadpaste{lv := [8,3,5,4,6,2,1,5,7]\bound{lv}} +} +\xtc{ +A convenient way to create a binary search tree is to +apply the operation \spadfun{binarySearchTree} to a list of elements. +}{ +\spadpaste{t := binarySearchTree lv\free{lv}\bound{t}} +} +\xtc{ +Another approach is to first create an empty binary search tree of integers. +}{ +\spadpaste{emptybst := empty()\$BSTREE(INT)\bound{e}} +} +\xtc{ +Insert the value \spad{8}. +This establishes \spad{8} as the root of the binary search tree. +Values inserted later that are less than \spad{8} get stored in +the \spadfun{left} subtree, others in the \spadfun{right} subtree. +}{ +\spadpaste{t1 := insert!(8,emptybst)\free{e}\bound{t1}} +} +\xtc{ +Insert the value \spad{3}. This number becomes the root of the +\spadfun{left} subtree of \spad{t1}. +For optimal retrieval, it is thus important to insert the +middle elements first. +}{ +\spadpaste{insert!(3,t1)\free{t1}} +} +\xtc{ +We go back to the original tree \spad{t}. +The leaves of the binary search tree are those which have empty +\spadfun{left} and \spadfun{right} subtrees. +}{ +\spadpaste{leaves t\free{t}} +} +\xtc{ +The operation +\spadfun{split}\spad{(k,t)} returns a \spadgloss{record} containing +the two subtrees: one with all elements ``less'' than \spad{k}, +another with elements ``greater'' than \spad{k}. +}{ +\spadpaste{split(3,t)\free{t}} +} +\xtc{ +Define \userfun{insertRoot} to insert new elements by +creating a new node. +}{ +\spadpaste{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x}} +} +\xtc{ +The new node puts the inserted value between its +``less'' tree and ``greater'' tree. +}{ +\begin{spadsrc}[\bound{x1}\free{x}] +insertRoot(x, t) == + a := split(x, t) + node(a.less, x, a.greater) +\end{spadsrc} +} +\xtc{ +Function \userfun{buildFromRoot} builds +a binary search tree from a list of elements \spad{ls} +and the empty tree \spad{emptybst}. +}{ +\spadpaste{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2}\free{x1 e}} +} +\xtc{ +Apply this to the reverse of the list \spad{lv}. +}{ +\spadpaste{rt := buildFromRoot reverse lv\bound{rt}\free{lv x2}} +} +\xtc{ +Have \Language{} check that these are equal. +}{ +\spadpaste{(t = rt)@Boolean\free{rt t}} +} +\endscroll +\autobuttons +\end{page} +% |