调整各节点的平衡因子
(&mut self)
| 82 | |
| 83 | // 调整各节点的平衡因子 |
| 84 | fn rebalance(&mut self) { |
| 85 | match *self { |
| 86 | Null => (), // 没数据，不用调整 |
| 87 | Tree(_) => match self.node().bfactor { |
| 88 | // 右子树重 |
| 89 | -2 => { |
| 90 | let lbf = self.node().left.node().bfactor; |
| 91 | if lbf == -1 || lbf == 0 { |
| 92 | let (a, b) = if lbf == -1 { |
| 93 | (0, 0) |
| 94 | } else { |
| 95 | (-1,1) |
| 96 | }; |
| 97 | self.rotate_right(); // 不平衡，旋转 |
| 98 | self.node().right.node().bfactor = a; |
| 99 | self.node().bfactor = b; |
| 100 | } else if lbf == 1 { |
| 101 | let (a, b) = match self.node() |
| 102 | .left.node() |
| 103 | .right.node() |
| 104 | .bfactor { |
| 105 | -1 => (1,0), |
| 106 | 0 => (0,0), |
| 107 | 1 => (0,-1), |
| 108 | _ => unreachable!(), |
| 109 | }; |
| 110 | |
| 111 | // 先左旋再右旋 |
| 112 | self.node().left.rotate_left(); |
| 113 | self.rotate_right(); |
| 114 | self.node().right.node().bfactor = a; |
| 115 | self.node().left.node().bfactor = b; |
| 116 | self.node().bfactor = 0; |
| 117 | } else { |
| 118 | unreachable!() |
| 119 | } |
| 120 | }, |
| 121 | // 左子树重 |
| 122 | 2 => { |
| 123 | let rbf = self.node().right.node().bfactor; |
| 124 | if rbf == 1 || rbf == 0 { |
| 125 | let (a,b) = if rbf == 1 { |
| 126 | (0,0) |
| 127 | } else { |
| 128 | (1,-1) |
| 129 | }; |
| 130 | self.rotate_left(); |
| 131 | self.node().left.node().bfactor = a; |
| 132 | self.node().bfactor = b; |
| 133 | } else if rbf == -1 { |
| 134 | let (a, b) = match self.node() |
| 135 | .right.node() |
| 136 | .left.node() |
| 137 | .bfactor { |
| 138 | 1 => (-1,0), |
| 139 | 0 => (0,0), |
| 140 | -1 => (0,1), |
| 141 | _ => unreachable!(), |
no test coverage detected