| 96 | |
| 97 | #[test] |
| 98 | fn delete_right_left_deviation() { |
| 99 | // right-hand deviation |
| 100 | let mut tree = Tree::default(); |
| 101 | for v in 0..100 { |
| 102 | tree.insert(v, v); |
| 103 | } |
| 104 | let mut height = 100; |
| 105 | for v in 0..100 { |
| 106 | tree.delete(&v); |
| 107 | height -= 1; |
| 108 | assert_eq!(height, tree.height()); |
| 109 | } |
| 110 | |
| 111 | // left-hand deviation |
| 112 | let mut tree = Tree::default(); |
| 113 | for v in (0..100).rev() { |
| 114 | tree.insert(v, v); |
| 115 | } |
| 116 | let mut height = 100; |
| 117 | for v in (0..100).rev() { |
| 118 | tree.delete(&v); |
| 119 | height -= 1; |
| 120 | assert_eq!(height, tree.height()); |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | #[test] |
| 125 | fn drop_clear() { |