X-Git-Url: https://git.distorted.org.uk/~mdw/runlisp/blobdiff_plain/8996f767e047eefa8af4d01b1434b54f4c169b79..10427eb21d77a0edeb2f17e434515b91b420cdfb:/lib.c

diff --git a/lib.c b/lib.c
index 523ca23..36751ab 100644
--- a/lib.c
+++ b/lib.c
@@ -436,7 +436,7 @@ void *treap_lookup(const struct treap *t, const char *k, size_t kn)
  * This is similar to `treap_lookup', in that it returns the requested node
  * if it already exists, or null otherwise, but it also records in P
  * information to be used by `treap_insert' to insert a new node with the
- * given key it's not there already.
+ * given key if it's not there already.
  */
 void *treap_probe(struct treap *t, const char *k, size_t kn,
 		  struct treap_path *p)
@@ -509,7 +509,7 @@ void treap_insert(struct treap *t, const struct treap_path *p,
      * subtree of U, then we rotate like this:
      *
      *			|		    |
-     *			U		    N
+     *			U		   (N)
      *		      /   \		  /   \
      *		   (N)	    Z	--->    X       U
      *		  /   \			      /   \
@@ -519,7 +519,7 @@ void treap_insert(struct treap *t, const struct treap_path *p,
      * of U, then we do the opposite rotation:
      *
      *		    |				|
-     *		    U				N
+     *		    U			       (N)
      *		  /   \			      /   \
      *		X      (N)	--->	    U	    Z
      *		      /   \		  /   \
@@ -594,7 +594,7 @@ void *treap_remove(struct treap *t, const char *k, size_t kn)
      *		      /   \		  /   \
      *		    L	    R	--->	X      (N)
      *		  /   \			      /   \
-     *		X	Y		    Y	    Z
+     *		X	Y		    Y	    R
      *
      * or
      *
@@ -608,8 +608,10 @@ void *treap_remove(struct treap *t, const char *k, size_t kn)
      * Again, these transformations clearly preserve the ordering of nodes in
      * the binary search tree, and the heap condition.
      */
-    else if (l->wt > r->wt) { *nn = l; n->left = l->right; nn = &l->right; }
-    else { *nn = r; n->right = r->left; nn = &r->left; }
+    else if (l->wt > r->wt)
+      { *nn = l; nn = &l->right; l = n->left = l->right; }
+    else
+      { *nn = r; nn = &r->left; r = n->right = r->left; }
 
   /* Release the key buffer, and return the node that we've now detached. */
   free(n->k); return (n);
@@ -691,9 +693,9 @@ void *treap_next(struct treap_iter *i)
    *
    *   * If the current node's right subtree is not empty, then the next node
    *	 to be visited is the leftmost node in that subtree.  All of the
-   *	 nodes on the stack are ancestors of the current nodes, and the right
+   *	 nodes on the stack are ancestors of the current node, and the right
    *	 subtree consists of its descendants, so none of them are already on
-   *	 the stack, and they're all greater than the current node, and
+   *	 the stack; and they're all greater than the current node, and
    *	 therefore haven't been visited.  Therefore, we must push the current
    *	 node's right child, its /left/ child, and so on, proceeding
    *	 leftwards until we fall off the bottom of the tree.