调整各节点的平衡因子
(&mut self)
| 273 | |
| 274 | // 调整各节点的平衡因子 |
| 275 | fn rebalance(&mut self) { |
| 276 | match self { |
| 277 | // 没数据，不用调整 |
| 278 | Null => (), |
| 279 | Tree(_) => match self.node().bfactor { |
| 280 | // 右子树重 |
| 281 | -2 => { |
| 282 | let lbf = self.node().left.node().bfactor; |
| 283 | if lbf == -1 || lbf == 0 { |
| 284 | let (a, b) = if lbf == -1 { |
| 285 | (0, 0) |
| 286 | } else { |
| 287 | (-1,1) |
| 288 | }; |
| 289 | |
| 290 | // 旋转并更新平衡因子 |
| 291 | self.rotate_right(); |
| 292 | self.node().right.node().bfactor = a; |
| 293 | self.node().bfactor = b; |
| 294 | } else if lbf == 1 { |
| 295 | let (a, b) = match self.node() |
| 296 | .left.node() |
| 297 | .right.node() |
| 298 | .bfactor { |
| 299 | -1 => (1, 0), |
| 300 | 0 => (0, 0), |
| 301 | 1 => (0,-1), |
| 302 | _ => unreachable!(), |
| 303 | }; |
| 304 | |
| 305 | // 先左旋再右旋，最后更新平衡因子 |
| 306 | self.node().left.rotate_left(); |
| 307 | self.rotate_right(); |
| 308 | self.node().right.node().bfactor = a; |
| 309 | self.node().left.node().bfactor = b; |
| 310 | self.node().bfactor = 0; |
| 311 | } else { |
| 312 | unreachable!() |
| 313 | } |
| 314 | }, |
| 315 | // 左子树重 |
| 316 | 2 => { |
| 317 | let rbf = self.node().right.node().bfactor; |
| 318 | if rbf == 1 || rbf == 0 { |
| 319 | let (a,b) = if rbf == 1 { |
| 320 | (0, 0) |
| 321 | } else { |
| 322 | (1,-1) |
| 323 | }; |
| 324 | |
| 325 | // 旋转并更新平衡因子 |
| 326 | self.rotate_left(); |
| 327 | self.node().left.node().bfactor = a; |
| 328 | self.node().bfactor = b; |
| 329 | } else if rbf == -1 { |
| 330 | let (a, b) = match self.node() |
| 331 | .right.node() |
| 332 | .left.node() |
no test coverage detected