引子
上一篇文章结束的时候，我亲手立下了flag，要手写2-3树。经过卧薪尝胆半个月后，终于放弃了。因为2-3树只是B树的某个状态，写了半天就写某个类的一个状态貌似很没有什么可吹嘘的。为了能够在一群老不要脸的80年程序员中吹吹牛，所以花了好几天的时间，写了一棵B树出来。现在终于可以放心的说：我心里还是有点B树的。
B树
B树的全名 是Balance Tree
特点
- 每个节点可用拥有超过2个元素
- 每个节点可以拥有超过2个子节点
- 依然有二叉搜索树的性质
- 平衡。每个节点的所有子树高度都是一致的。
- 高度不会特别高
性质
- m阶B树，是说一个节点最多拥有m个子节点，也就是拥有m-1个元素
- 根节点的元素个数x必须满足 x >= 1 && x <= m - 1
- 非根节点的元素个数x必须满足 x<= m - 1 && x >= [m/2] -1 [m/2]表示向上取整
非根节点的子子节点个数y为 y>=[m/2] && y <= m
操作
业余时间真的不多，所以我只写了添加与删除的逻辑。
添加
新添加的元素必然添加到叶子节点
上溢
1 上溢节点中元素个数必须是m
2 求得中间位置k
3 将k位元素移动到父节点中k'
4 将k左右的节点分别作为k'的左右节点
5 如果k'所在的节点仍然上溢，则仍然需要做相同的处理
看图
假设我们当前的树的m值为3，也就是说当前树是2-3树，添加节点过程如下图所示
添加节点.jpg
删除
- 如果删除的元素是叶子节点元素，则直接删除
- 如果删除的元素是中间节点元素，则需要找到前驱节点的最大值，或者后稷节点的最小值。将最大值或最小值覆盖当前节点，然后把最大值最小值删除掉（所以，真正的删除都是发生在叶子节点上）
下溢
节点中元素个数小于[m/2]-1时，是下溢状态（元素个数必然是[m/2]-2，特殊的对于root节点来说，下溢状态是元素个数为0
下溢的处理过程分两种情况
借元素
可以从兄弟节点中借到元素时，步骤如下：
1.找到临近的兄弟节点中元素个数是>=[m/2]（左或右选兄弟节点一个即可），注意从左兄弟中借的是最大的元素，从右兄弟中借的是最小的元素。
2.将父节点元素放入当前节点，把借到的元素放到父元素中的位置。
3.如果是从左兄弟节点借到的元素，此元素有右子节点，则把此右子节点放到当前节点的子节点中第一的位置。
4.如果是从右兄弟节点借到的元素，此元素右左子节点，则把此左子节点放到当前节点的子节点中最后的位置
合并节点
当兄弟节点都无法借给当前节点元素的时候，选择将 左兄弟节点 与 父节点中的元素，以及当前节点合并为一个新节点，放到当前的位置
Talk is cheap
代码还没写注释，后面补吧
Tree类
public class Tree<T extends Comparable> {
private int degree;
private Node<T> root;
public Tree(int degree){
this.degree = degree;
}
public void add(T value){
if(this.root == null){
List<T> elementList = new ArrayList<>();
elementList.add(value);
this.root = new Node<>(this.degree, elementList);
this.root.setRoot(true);
}else{
Fission<T> fission = this.innerAdd(this.root, value);
if(fission != null){
List<T> elementList = new ArrayList<>();
elementList.add(fission.getValue());
this.root = new Node<T>(this.degree, elementList);
List<Node<T>> subNodeList = new ArrayList<>();
subNodeList.add(fission.getLeftPart());
subNodeList.add(fission.getRightPart());
this.root.setSubNodeList(subNodeList);
this.root.setRoot(true);
}
}
}
private Fission<T> innerAdd(Node<T> node, T value) {
if(node.isLeaf()){
node.insertElement(value);
if(node.overflow()){
return node.fission();
}else{
return null;
}
}else{
int index = node.bisect(value);
Node<T> subNode = node.getSubNodeList().get(index);
Fission<T> fission = this.innerAdd(subNode, value);
if(fission != null){
node.merge(fission);
if(node.overflow()){
return node.fission();
}else{
return null;
}
}
return null;
}
}
public void remove(T value){
if(this.root != null){
this.innerRemove(this.root, value);
if(this.root.underflow()){
this.underflowRoot();
}
}
}
private void innerRemove(Node<T> node, T value){
if(node.hasElement(value)){
if(node.isLeaf()){
node.removeElement(value);
}else{
int index = node.bisect(value);
T deletedValue = this.deleteLeftLargest(node.getSubNodeList().get(index));
node.replaceElement(index, deletedValue);
this.underflowSubTree(node, node.getSubNodeList().get(index), index);
}
}else{
if(node.isLeaf() == false){
int index = node.bisect(value);
Node<T> subNode = node.getSubNodeList().get(index);
this.innerRemove(subNode, value);
if(subNode.underflow()){
this.underflow(node, subNode, index);
}
}
}
}
private boolean underflowSubTree(Node<T> parentNode, Node<T> node, int inParentIndex){
boolean underflow = false;
if(node.isLeaf()){
if(node.underflow()){
this.underflow(parentNode, node, inParentIndex);
underflow = true;
}
}else{
int subIndex = node.getSubNodeList().size() - 1;
underflow = this.underflowSubTree(node, node.getSubNodeList().get(subIndex), subIndex);
if(underflow && node.underflow()){
this.underflow(parentNode, node, inParentIndex);
underflow = true;
}
}
return underflow;
}
private T deleteLeftLargest(Node<T> node){
T leftLargest = null;
if(node.isLeaf()){
leftLargest = node.removeLastElement();
}else{
Node<T> lastNode = node.getSubNodeList().get(node.getSubNodeList().size() - 1);
leftLargest = this.deleteLeftLargest(lastNode);
}
return leftLargest;
}
private void underflowRoot(){
Node<T> newRoot = new Node<T>(this.degree);
for(Node<T> subNode : this.root.getSubNodeList()){
newRoot.appendElement(subNode.getElementList());
newRoot.appendSubNodeList(subNode.getSubNodeList());
}
newRoot.setRoot(true);
this.root = newRoot;
}
private void underflow(Node<T> parentNode, Node<T> node, int inParentIndex){
Node<T> leftBro = null;
Node<T> rightBro = null;
if(inParentIndex > 0){
leftBro = parentNode.getSubNodeList().get(inParentIndex - 1);
}
if(inParentIndex < parentNode.getSubNodeList().size() - 1){
rightBro = parentNode.getSubNodeList().get(inParentIndex + 1);
}
if(leftBro != null && leftBro.isRich()){
T lastElement = leftBro.removeLastElement();
T fromParent = parentNode.replaceElement(inParentIndex - 1, lastElement);
node.insertElement(fromParent);
if(leftBro.isLeaf() == false){
Node<T> leftBroLastNode = leftBro.removeLastSubNode();
node.insertSubNode(0, leftBroLastNode);
}
}else if(rightBro != null && rightBro.isRich()){
T firstElemnt = rightBro.removeFirstElement();
T fromParent = parentNode.replaceElement(inParentIndex, firstElemnt);
node.insertElement(fromParent);
if(rightBro.isLeaf() == false){
Node<T> rightBroFirstNode = rightBro.removeFirstSubNode();
node.insertSubNode(node.getSubNodeList().size(), rightBroFirstNode);
}
}else{
if(leftBro != null){
T parentValue = parentNode.removeElement(inParentIndex - 1);
List<T> moreElementList = new ArrayList<>();
moreElementList.add(parentValue);
moreElementList.addAll(node.getElementList());
leftBro.appendElement(moreElementList);
parentNode.removeSubNode(inParentIndex);
if(node.isLeaf() == false){
leftBro.appendSubNodeList(node.getSubNodeList());
}
}else if(rightBro != null){
T parentValue = parentNode.removeElement(inParentIndex);
List<T> moreElementList = new ArrayList<>();
moreElementList.add(parentValue);
moreElementList.addAll(rightBro.getElementList());
node.appendElement(moreElementList);
parentNode.removeSubNode(inParentIndex + 1);
if(node.isLeaf() == false){
node.appendSubNodeList(rightBro.getSubNodeList());
}
}else{
throw new IllegalStateException();
}
}
}
}
Node类
public class Node <T extends Comparable>{
private int maxElementNum;
private int minElementNum;
private List<T> elementList;
private List<Node<T>> subNodeList;
private boolean root;
public Node(int degree){
this(degree, null);
}
public Node(int degree, List<T> elements){
this.maxElementNum = degree - 1;
this.minElementNum = new BigDecimal(degree).divide(new BigDecimal(2), RoundingMode.CEILING).intValue() - 1;
this.elementList = elements;
this.subNodeList = new ArrayList<>();
this.root = false;
}
public boolean isRoot() {
return root;
}
public void setRoot(boolean root) {
this.root = root;
}
public void setSubNodeList(List<Node<T>> subNodeList){
this.subNodeList.clear();
this.subNodeList.addAll(subNodeList);
}
public List<T> getElementList(){
return this.elementList;
}
public List<Node<T>> getSubNodeList(){
return this.subNodeList;
}
public boolean isLeaf(){
return this.subNodeList.isEmpty();
}
public boolean isRich(){
return this.elementList.size() > this.minElementNum;
}
public void insertElement(T value) {
int index = this.bisect(value);
this.insertElement(index, value);
}
public void insertElement(int index, T value){
this.elementList.add(index, value);
}
public boolean overflow(){
return this.elementList.size() > this.maxElementNum;
}
public boolean underflow(){
return this.root ? this.elementList.size() < 1 : this.elementList.size() < this.minElementNum;
}
public Fission fission(){
int mid = (this.elementList.size() - 1 ) / 2;
T value = this.elementList.get(mid);
List<T> leftElementList = new ArrayList<>();
leftElementList.addAll(this.elementList.subList(0, mid));
Node<T> leftPart = new Node<T>(this.maxElementNum + 1, leftElementList);
List<T> rightElementList = new ArrayList<>();
rightElementList.addAll(this.elementList.subList(mid + 1, this.elementList.size()));
Node<T> rightPart = new Node<T>(this.maxElementNum + 1, rightElementList);
if(this.isLeaf() == false){
leftPart.setSubNodeList(this.subNodeList.subList(0, mid + 1));
rightPart.setSubNodeList(this.subNodeList.subList(mid + 1, this.subNodeList.size()));
}
return new Fission(value, leftPart, rightPart);
}
public void merge(Fission<T> fission) {
int index = this.bisect(fission.getValue());
this.elementList.add(index, fission.getValue());
this.subNodeList.set(index, fission.getLeftPart());
this.subNodeList.add(index + 1, fission.getRightPart());
}
public int bisect(T value){
if(this.elementList.isEmpty()){
return 0;
}
int left = 0;
int right = this.elementList.size() - 1;
while(left < right){
int mid = left + (right - left)/2;
T midValue = this.elementList.get(mid);
if(midValue.compareTo(value) >= 0){
right = mid;
}else{
left = mid + 1;
}
}
if(this.elementList.get(left).compareTo(value) >= 0){
return left;
}else if(this.elementList.get(right).compareTo(value) >= 0){
return right;
}else{
return this.elementList.size();
}
}
public boolean hasElement(T value) {
return this.elementList.contains(value);
}
public void removeElement(T value){
this.elementList.remove(value);
}
public T removeLastElement() {
return this.elementList.remove(this.elementList.size() - 1);
}
public T removeElement(int index){
return this.elementList.remove(index);
}
public T replaceElement(int index, T replaceValue){
return this.elementList.set(index, replaceValue);
}
public Node<T> removeLastSubNode() {
return this.subNodeList.remove(this.subNodeList.size() - 1);
}
public void insertSubNode(int index, Node<T> newNode) {
this.subNodeList.add(index, newNode);
}
public T removeFirstElement() {
return this.elementList.remove(0);
}
public Node<T> removeFirstSubNode() {
return this.subNodeList.remove(0);
}
public void appendElement(List<T> moreElementList){
this.elementList.addAll(moreElementList);
}
public void appendSubNodeList(List<Node<T>> moreNodeList){
this.subNodeList.addAll(moreNodeList);
}
public Node<T> removeSubNode(int index) {
return this.subNodeList.remove(index);
}
}
Fission类
这个类上溢的时候存储分裂结果
public class Fission<T extends Comparable> {
private T value;
private Node<T> leftPart;
private Node<T> rightPart;
public Fission(T value, Node<T> leftPart, Node<T> rightPart) {
this.value = value;
this.leftPart = leftPart;
this.rightPart = rightPart;
}
public T getValue() {
return value;
}
public Node<T> getLeftPart() {
return leftPart;
}
public Node<T> getRightPart() {
return rightPart;
}
}
预告
接下来我想写红黑树或者B+树
