--- a/src/lib.rs	Fri Jul 08 22:54:56 2022 -0700
+++ b/src/lib.rs	Sat Jul 09 15:40:10 2022 -0700
@@ -2,7 +2,7 @@
 use std::cmp::Ordering;
 
 // Min. order: 3
-const ORDER: usize = 5;
+const ORDER: usize = 4;
 
 #[derive(Debug)]
 struct Node<T> {
@@ -359,7 +359,172 @@
     pub fn delete(&mut self, entry: &T) -> Option<T> {
         match self.find_from(self.root, entry) {
             None => None,
-            Some((_, node, nodeentry)) => self.delete_recursive(self.root, Some(entry), None),
+            Some((_, node, nodeentry)) => {
+                let d = self.yank(self.root, entry);
+                d
+            }
+        }
+    }
+
+    // Yank-Refill-Rebalance strategy:
+    // 1. find element and remove it, leaving a hole in a node.
+    // 2. Fill hole by removing an element from one of the children, creating a new hole below.
+    //    Recursively bubble down the whole until a leaf is reached.
+    // 3. Rebalance: check if either child is below half capacity and rotate or merge nodes.
+
+    fn yank(&mut self, node: usize, entry: &T) -> Option<T> {
+        println!("yank {}", node);
+        for i in 0..ORDER-1 {
+            if let Some(val) = self.get(node, i) {
+                match Cmp::cmp(entry, val) {
+                    Ordering::Less => {
+                        let d = self.yank(self.get_child(node, i).unwrap(), entry);
+                        self.rebalance(node, i);
+                        return d;
+                    },
+                    Ordering::Equal => {
+                        let d = self.pop(node, i);
+                        self.rebalance(node, i);
+                        return d;
+                    },
+                    Ordering::Greater => {
+                        // Last element or no more entries
+                        if i == ORDER-2 || self.get(node, i+1).is_none() {
+                            let d = self.yank(self.get_child(node, i+1).unwrap(), entry);
+                            self.rebalance(node, i);
+                            return d;
+                        } else {
+                            continue
+                        }
+                    }
+                }
+            }
+        }
+        None
+    }
+
+    // Fill hole in node at entryix by rotating or merging children's elements.
+    fn pop(&mut self, node: usize, entryix: usize) -> Option<T> {
+        println!("pop {}/{}", node, entryix);
+        if self.is_leaf(node) {
+            let d = self.get_mut(node, entryix).take();
+            for i in entryix..ORDER-2 {
+                *self.get_mut(node, i) = self.get_mut(node, i+1).take();
+            }
+            return d;
+        }
+        // Invariant: every entry has two children unless in leaf node.
+        let (left, right) = (self.get_child(node, entryix).unwrap(), self.get_child(node, entryix+1).unwrap());
+        let (leftcount, rightcount) = (self.count_in(left), self.count_in(right));
+        // Replace with element from fuller child.
+        let d = self.get_mut(node, entryix).take();
+        if leftcount > rightcount {
+            *self.get_mut(node, entryix) = self.pop(left, leftcount-1);
+        } else {
+            *self.get_mut(node, entryix) = self.pop(right, 0);
+        }
+        // TODO: illegal "crossing"!
+        d
+    }
+
+    fn rebalance(&mut self, node: usize, entryix: usize) {
+        if self.is_leaf(node) {
+            return;
+        }
+        println!("rebalance {}/{}", node, entryix);
+        let (left, right) = (self.get_child(node, entryix).unwrap(), self.get_child(node, entryix+1).unwrap());
+        let (leftcount, rightcount) = (self.count_in(left), self.count_in(right));
+        if leftcount >= ORDER/2 && rightcount >= ORDER/2 {
+            return;
+        }
+        assert!(leftcount < ORDER-1 || rightcount < ORDER-1);
+        // Merge or rotate?
+        if leftcount + rightcount + 1 > ORDER-1 {
+            assert!(leftcount >= ORDER/2 || rightcount >= ORDER/2);
+            // Rotate
+            let piv = self.get_mut(node, entryix).take();
+            if leftcount > rightcount {
+                // Move one element from left to right child.
+                println!("before {:?}", self.v[right]);
+
+                *self.get_child_mut(right, ORDER-1) = self.get_child_mut(right, ORDER-2).take();
+                for i in (1..ORDER-1).rev() {
+                    // Shuffle right node.
+                    *self.get_child_mut(right, i) = self.get_child_mut(right, i-1).take();
+                    *self.get_mut(right, i) = self.get_mut(right, i-1).take();
+                }
+                *self.get_mut(right, 0) = piv;
+
+
+                *self.get_child_mut(right, 0) = self.get_child_mut(left, leftcount).take();
+                *self.get_mut(node, entryix) = self.get_mut(left, leftcount-1).take();
+                println!("after {:?}", self.v[right]);
+            } else {
+                println!("before {:?}", self.v[left]);
+                *self.get_mut(left, leftcount) = piv;
+                *self.get_child_mut(left, leftcount+1) = self.get_child_mut(right, 0).take();
+                //*self.get_child_mut(node, entryix) = self.get_child_mut(right, 0).take();
+                *self.get_mut(node, entryix) = self.get_mut(right, 0).take();
+
+                for i in 0..ORDER-2 {
+                    // Shuffle right node.
+                    *self.get_child_mut(right, i) = self.get_child_mut(right, i+1).take();
+                    *self.get_mut(right, i) = self.get_mut(right, i+1).take();
+                }
+                println!("after: {:?}", self.v[left]);
+                *self.get_child_mut(right, ORDER-2) = self.get_child_mut(right, ORDER-1).take();
+            }
+        } else {
+            // Merge
+            let piv = self.get_mut(node, entryix).take();
+
+            let mut newnode = Node::new();
+            let mut count = 0;
+            for i in 0..ORDER-1 {
+                newnode.entries[i] = self.get_mut(left, i).take();
+                newnode.children[i] = self.get_child_mut(left, i).take();
+                if newnode.entries[i].is_none() {
+                    break
+                }
+                count += 1;
+            }
+            // Copy right-most child
+            if count == ORDER-1 {
+                panic!("Encountered full left node in merge!");
+                // newnode.children[ORDER-1] = self.get_child_mut(left, ORDER-1).take();
+            }
+            newnode.entries[count] = piv;
+            count += 1;
+            let off = count;
+            for i in off..ORDER-1 {
+                newnode.entries[i] = self.get_mut(right, i-off).take();
+                newnode.children[i] = self.get_child_mut(right, i-off).take();
+                if newnode.entries[i].is_none() {
+                    break;
+                }
+                count += 1;
+            }
+            // Copy right-most child.
+            newnode.children[count] = self.get_child_mut(right, count-off).take();
+
+            // TODO: recycle nodes.
+            let newnodeix = self.v.len();
+            self.v.push(newnode);
+
+            // Replace lchild-piv-rchild in `node`.
+            *self.get_child_mut(node, entryix) = Some(newnodeix);
+            for i in entryix..ORDER-2 {
+                *self.get_mut(node, i) = self.get_mut(node, i+1).take();
+                if i > entryix { // Discard former right node.
+                    *self.get_child_mut(node, i) = self.get_child_mut(node, i+1).take();
+                }
+            }
+            *self.get_child_mut(node, ORDER-2) = self.get_child_mut(node, ORDER-1).take();
+
+            // Replace root if there is no active entry left.
+            if node == self.root && self.count_in(node) == 0 {
+                self.root = newnodeix;
+            }
         }
     }
 }
@@ -496,21 +661,4 @@
             }
         }
     }
-
-    #[test]
-    fn test_binary_node_search() {
-        let mut bt = BTree::new(10);
-        for i in 0..super::ORDER/2 {
-            bt.insert(i);
-        }
-
-        println!("{}", bt.debug_print());
-        assert_eq!(bt.binary_node_search(bt.root, &19), 15);
-        for i in 0..super::ORDER - 1 {
-            assert_eq!(
-                bt.binary_node_search(bt.root, &i),
-                std::cmp::min(i, super::ORDER/2)
-            );
-        }
-    }
 }