| 122 | } |
| 123 | |
| 124 | func TestAVLDelete(t *testing.T) { |
| 125 | t.Run("LLRotation-Test", func(t *testing.T) { |
| 126 | tree := bt.NewAVL[int]() |
| 127 | if tree.Delete(5) { |
| 128 | t.Errorf("There is no node, whose value is 5") |
| 129 | } |
| 130 | |
| 131 | tree.Push(5) |
| 132 | tree.Push(4) |
| 133 | tree.Push(3) |
| 134 | tree.Push(2) |
| 135 | |
| 136 | if !tree.Delete(5) { |
| 137 | t.Errorf("There is a node, whose value is 5") |
| 138 | } |
| 139 | |
| 140 | if tree.Delete(50) { |
| 141 | t.Errorf("There is no node, whose value is 50") |
| 142 | } |
| 143 | |
| 144 | root := tree.Root |
| 145 | if root.Key() != 3 { |
| 146 | t.Errorf("Root should have value = 3") |
| 147 | } |
| 148 | if root.Height() != 2 { |
| 149 | t.Errorf("Height of Root should be = 2") |
| 150 | } |
| 151 | |
| 152 | if root.Left().Key() != 2 { |
| 153 | t.Errorf("Left child should have value = 2") |
| 154 | } |
| 155 | if root.Left().(*bt.AVLNode[int]).Height() != 1 { |
| 156 | t.Errorf("Height of Left child should be 1") |
| 157 | } |
| 158 | |
| 159 | if root.Right().Key() != 4 { |
| 160 | t.Errorf("Right child should have value = 5") |
| 161 | } |
| 162 | if root.Right().(*bt.AVLNode[int]).Height() != 1 { |
| 163 | t.Errorf("Height of Right should be 1") |
| 164 | } |
| 165 | }) |
| 166 | |
| 167 | t.Run("LRRotation-Test", func(t *testing.T) { |
| 168 | tree := bt.NewAVL[int]() |
| 169 | |
| 170 | tree.Push(10) |
| 171 | tree.Push(8) |
| 172 | tree.Push(8) |
| 173 | tree.Push(6) |
| 174 | tree.Push(7) |
| 175 | |
| 176 | if !tree.Delete(10) { |
| 177 | t.Errorf("There is a node, whose value is 10") |
| 178 | } |
| 179 | |
| 180 | if tree.Delete(5) { |
| 181 | t.Errorf("There is no node, whose value is 5") |