请选择 进入手机版 | 继续访问电脑版

我爱科技论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 692|回复: 0

[技术分享] 【java进阶】利用Java实现B+树的添加和删除源码

[复制链接]

696

主题

743

帖子

7927

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
7927

最佳新人活跃会员热心会员推广达人宣传达人灌水之王突出贡献优秀版主荣誉管理论坛元老

发表于 2018-3-27 16:35:31 | 显示全部楼层 |阅读模式
定义一个接口B
  1. package bptree;

  2. // 先来定义一个接口
  3. // 每一个树都应该具备下面的这三个功能
  4. public interface B {
  5.         // 查询
  6.         public Object get(Comparable key);
  7.         // 移除节点
  8.         public void remove(Comparable key);
  9.         // 插入或者更新节点, 如果节点已经存在就更新; 只有节点不存在的时候就插入这个节点
  10.         public void insertOrUpdate(Comparable key, Object obj);
  11. }
复制代码
开始实现我的B+树
  1. package bptree;

  2. import java.util.Random;

  3. // 这个是我的B+树,实现我自己定义的三个接口(接口一旦定义了, 实现类都必须要一一实现这个接口)
  4. public class IBPlusTree implements B{
  5.        
  6.         // 定义B+树的一些节点属性
  7.         // 根节点
  8.         protected INode root;
  9.        
  10.         // 阶数:一个节点最多能够有多少个子节点(也就是M阶)
  11.         protected int order;
  12.        
  13.         // 叶子结点的链表头
  14.         protected INode head;
  15.        
  16.        
  17.        

  18.         public INode getRoot() {
  19.                 return root;
  20.         }

  21.         public void setRoot(INode root) {
  22.                 this.root = root;
  23.         }

  24.         public int getOrder() {
  25.                 return order;
  26.         }

  27.         public void setOrder(int order) {
  28.                 this.order = order;
  29.         }

  30.         public INode getHead() {
  31.                 return head;
  32.         }

  33.         public void setHead(INode head) {
  34.                 this.head = head;
  35.         }
  36.        
  37.        

  38.         // 获得一个节点
  39.         @Override
  40.         public Object get(Comparable key) {
  41.                 // TODO Auto-generated method stub
  42.                 return root.get(key);
  43.         }
  44.        

  45.        
  46.         // 删除节点的实现
  47.         @Override
  48.         public void remove(Comparable key) {
  49.                 // TODO Auto-generated method stub
  50.                 // 删除这一颗树的节点key(直接删除即可)
  51.                 root.remove(key, this);
  52.                
  53.         }

  54.        
  55.         // 添加或者更新节点
  56.         @Override
  57.         public void insertOrUpdate(Comparable key, Object obj) {
  58.                 // TODO Auto-generated method stub
  59.                 // 在这一颗树的key的位置添加一个新的节点obj
  60.                 root.insertOrUpdate(key, obj, this);
  61.         }
  62.        
  63.        
  64.        
  65.         // 定义我的构造函数(B+树的构造函数)
  66.         /**
  67.          * 这是一个order(M阶)的B+树
  68.          * @param order
  69.          */
  70.         public IBPlusTree(int order){
  71.                 // 要保证这个树的阶数大于2(也就是一个节点至少要有两个子节点)
  72.                 if (order < 3){
  73.                         System.out.println("order (M阶数) must be greater than 2");
  74.                         System.exit(0);;
  75.                 }
  76.                
  77.                 // 当前的树的阶数设置进来
  78.                 this.order = order;
  79.                 // 开始新建我的根节点
  80.                 this.root = new INode(true, true);
  81.                 // 这个树的当前头结点就是自己本身
  82.                 this.head = root;
  83.         }
  84.        
  85.        
  86.         // toString()函数的重写
  87.         @Override
  88.         public String toString() {
  89.                 return "BPlusTree [root=" + root + ", order=" + order + ", head=" + head + "]";
  90.         }
  91.        
  92.        
  93.        
  94. }
复制代码
我的节点
  1. package bptree;
  2. import java.util.AbstractMap.SimpleEntry;  
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5. import java.util.Map.Entry;  

  6. /**
  7. * 这个是B+树的节点
  8. * @author Xiugang
  9. *
  10. */
  11. public class INode {
  12.         // 添加树的节点的一些属性
  13.         // 这个节点是不是叶子节点
  14.         protected boolean isLeaf;
  15.        
  16.         // 这个节点是不是根节点
  17.         protected boolean isRoot;
  18.        
  19.         // 父节点
  20.         protected INode parent;
  21.        
  22.         // 叶子节点的前一个节点
  23.         protected INode previous;
  24.        
  25.         // 叶子节点的后一个节点
  26.         protected INode next;
  27.        
  28.         // 一个节点位置的关键字
  29.         protected List<Entry<Comparable, Object>> entries;
  30.        
  31.         // 孩子节点(一个节点有多个孩子节点, 这里需要使用List集合来存储孩子节点)
  32.         protected List<INode> children;
  33.        
  34.        
  35.        
  36.        
  37.        
  38.         public boolean isLeaf() {
  39.                 return isLeaf;
  40.         }


  41.         public void setLeaf(boolean isLeaf) {
  42.                 this.isLeaf = isLeaf;
  43.         }


  44.         public boolean isRoot() {
  45.                 return isRoot;
  46.         }


  47.         public void setRoot(boolean isRoot) {
  48.                 this.isRoot = isRoot;
  49.         }


  50.         public INode getParent() {
  51.                 return parent;
  52.         }


  53.         public void setParent(INode parent) {
  54.                 this.parent = parent;
  55.         }


  56.         public INode getPrevious() {
  57.                 return previous;
  58.         }


  59.         public void setPrevious(INode previous) {
  60.                 this.previous = previous;
  61.         }


  62.         public INode getNext() {
  63.                 return next;
  64.         }


  65.         public void setNext(INode next) {
  66.                 this.next = next;
  67.         }


  68.         public List<Entry<Comparable, Object>> getEntries() {
  69.                 return entries;
  70.         }


  71.         public void setEntries(List<Entry<Comparable, Object>> entries) {
  72.                 this.entries = entries;
  73.         }


  74.         public List<INode> getChildren() {
  75.                 return children;
  76.         }


  77.         public void setChildren(List<INode> children) {
  78.                 this.children = children;
  79.         }


  80.         // 定义我的这个节点的构造函数
  81.         /**
  82.          * 根据是不是叶子节点来进行构造
  83.          * @param isLeaf
  84.          */
  85.         public INode(boolean isLeaf){
  86.                 // 每次生成一个节点都要看一下是不是叶子节点
  87.                 this.isLeaf = isLeaf;
  88.                
  89.                 // 设置这个节点位置的关键字
  90.                 this.entries = new ArrayList<Entry<Comparable,Object>>();
  91.                
  92.                 // 如果不是叶子节点的话
  93.                 if (!isLeaf){
  94.                         // 只要不是叶子节点的话, 那么这个节点就有一个孩子节点
  95.                         this.children = new ArrayList<INode>();
  96.                 }
  97.         }
  98.        
  99.        
  100.         /**
  101.          * 通过是不是叶子节点,是不是根节点来构造
  102.          * @param isLeaf
  103.          * @param isRoot
  104.          */
  105.         public INode(boolean isLeaf, boolean isRoot){
  106.                 // 调用我上面的构造函数
  107.                 this(isLeaf);
  108.                 // 根节点
  109.                 this.isRoot = isRoot;
  110.         }
  111.        
  112.        
  113.         /**
  114.          * 根据key值获得一个节点
  115.          * @param key
  116.          * @return
  117.          */
  118.         public Object get(Comparable key){
  119.                 // 如果这个节点是叶子节点的话
  120.                 if (this.isLeaf){
  121.                         // 开始遍历我的所有的关键字集合
  122.                         for (Entry<Comparable, Object> entry : entries){
  123.                                 // 如果在这个集合里面找到了和我的这个key相等的key
  124.                                 if (entry.getKey().compareTo(key) == 0){
  125.                                         // 就把这个对象返回出去
  126.                                         return entry.getValue();
  127.                                 }
  128.                         }
  129.                         // 如果没有找到,就返回空
  130.                         return null;
  131.                 }
  132.                 // 如果当前的这个节点不是叶子节点的话
  133.                 else {
  134.                         // 如果key小于等于节点最左边的key, 就沿着第一个子节点继续搜索
  135.                         if (key.compareTo(entries.get(0).getKey()) <= 0){
  136.                                 return children.get(0).get(key);
  137.                         }
  138.                         // 如果key 大于节点最右边的key, 就沿着最后一个子节点继续搜索
  139.                         else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {  
  140.                 return children.get(children.size()-1).get(key);  
  141.             //否则沿比key大的前一个子节点继续搜索  
  142.             }
  143.                         else {  
  144.                                 for (int i = 0; i < entries.size(); i++) {  
  145.                     if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {  
  146.                         return children.get(i).get(key);  
  147.                     }  
  148.                 }
  149.                
  150.                         }
  151.         }
  152.         return null;
  153.         }
  154.        
  155.        
  156.        
  157.         /**
  158.          * 如果key不存在就添加, 如果存在了就更新
  159.          * @param key
  160.          * @param obj
  161.          * @param tree
  162.          */
  163.         public void insertOrUpdate(Comparable key, Object obj, IBPlusTree tree){  
  164.         //如果是叶子节点  
  165.         if (isLeaf){  
  166.             //不需要分裂,直接插入或更新  
  167.             if (contains(key) || entries.size() < tree.getOrder()){  
  168.                 insertOrUpdate(key, obj);  
  169.                 if (parent != null) {  
  170.                     //更新父节点  
  171.                     parent.updateInsert(tree);  
  172.                 }  
  173.   
  174.             //需要分裂   
  175.             }else {  
  176.                 //分裂成左右两个节点  
  177.                 INode left = new INode(true);  
  178.                 INode right = new INode(true);  
  179.                 //设置链接  
  180.                 if (previous != null){  
  181.                     previous.setNext(left);  
  182.                     left.setPrevious(previous);  
  183.                 }  
  184.                 if (next != null) {  
  185.                     next.setPrevious(right);  
  186.                     right.setNext(next);  
  187.                 }  
  188.                 if (previous == null){  
  189.                     tree.setHead(left);  
  190.                 }  
  191.   
  192.                 left.setNext(right);  
  193.                 right.setPrevious(left);  
  194.                 previous = null;  
  195.                 next = null;  
  196.                   
  197.                 //左右两个节点关键字长度  
  198.                 int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;   
  199.                 int rightSize = (tree.getOrder() + 1) / 2;  
  200.                 //复制原节点关键字到分裂出来的新节点  
  201.                 insertOrUpdate(key, obj);  
  202.                 for (int i = 0; i < leftSize; i++){  
  203.                     left.getEntries().add(entries.get(i));  
  204.                 }  
  205.                 for (int i = 0; i < rightSize; i++){  
  206.                     right.getEntries().add(entries.get(leftSize + i));  
  207.                 }  
  208.                   
  209.                 //如果不是根节点  
  210.                 if (parent != null) {  
  211.                     //调整父子节点关系  
  212.                     int index = parent.getChildren().indexOf(this);  
  213.                     parent.getChildren().remove(this);  
  214.                     left.setParent(parent);  
  215.                     right.setParent(parent);  
  216.                     parent.getChildren().add(index,left);  
  217.                     parent.getChildren().add(index + 1, right);  
  218.                     setEntries(null);  
  219.                     setChildren(null);  
  220.                      
  221.                     //父节点插入或更新关键字  
  222.                     parent.updateInsert(tree);  
  223.                     setParent(null);  
  224.                 //如果是根节点      
  225.                 }else {  
  226.                     isRoot = false;  
  227.                     INode parent = new INode(false, true);  
  228.                     tree.setRoot(parent);  
  229.                     left.setParent(parent);  
  230.                     right.setParent(parent);  
  231.                     parent.getChildren().add(left);  
  232.                     parent.getChildren().add(right);  
  233.                     setEntries(null);  
  234.                     setChildren(null);  
  235.                      
  236.                     //更新根节点  
  237.                     parent.updateInsert(tree);  
  238.                 }  
  239.                   
  240.   
  241.             }  
  242.               
  243.         //如果不是叶子节点  
  244.         }else {  
  245.             //如果key小于等于节点最左边的key,沿第一个子节点继续搜索  
  246.             if (key.compareTo(entries.get(0).getKey()) <= 0) {  
  247.                 children.get(0).insertOrUpdate(key, obj, tree);  
  248.             //如果key大于节点最右边的key,沿最后一个子节点继续搜索  
  249.             }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {  
  250.                 children.get(children.size()-1).insertOrUpdate(key, obj, tree);  
  251.             //否则沿比key大的前一个子节点继续搜索  
  252.             }else {  
  253.                 for (int i = 0; i < entries.size(); i++) {  
  254.                     if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {  
  255.                         children.get(i).insertOrUpdate(key, obj, tree);  
  256.                         break;  
  257.                     }  
  258.                 }     
  259.             }  
  260.         }  
  261.     }  
  262.       
  263.     /** 插入节点后中间节点的更新 */  
  264.         /**
  265.          * 更新添加的操作
  266.          * @param tree
  267.          */
  268.     protected void updateInsert(IBPlusTree tree){  
  269.   
  270.         validate(this, tree);  
  271.          
  272.         //如果子节点数超出阶数,则需要分裂该节点     
  273.         if (children.size() > tree.getOrder()) {  
  274.             //分裂成左右两个节点  
  275.             INode left = new INode(false);  
  276.             INode right = new INode(false);  
  277.             //左右两个节点关键字长度  
  278.             int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;  
  279.             int rightSize = (tree.getOrder() + 1) / 2;  
  280.             //复制子节点到分裂出来的新节点,并更新关键字  
  281.             for (int i = 0; i < leftSize; i++){  
  282.                 left.getChildren().add(children.get(i));  
  283.                 left.getEntries().add(new SimpleEntry(children.get(i).getEntries().get(0).getKey(), null));  
  284.                 children.get(i).setParent(left);  
  285.             }  
  286.             for (int i = 0; i < rightSize; i++){  
  287.                 right.getChildren().add(children.get(leftSize + i));  
  288.                 right.getEntries().add(new SimpleEntry(children.get(leftSize + i).getEntries().get(0).getKey(), null));  
  289.                 children.get(leftSize + i).setParent(right);  
  290.             }  
  291.               
  292.             //如果不是根节点  
  293.             if (parent != null) {  
  294.                 //调整父子节点关系  
  295.                 int index = parent.getChildren().indexOf(this);  
  296.                 parent.getChildren().remove(this);  
  297.                 left.setParent(parent);  
  298.                 right.setParent(parent);  
  299.                 parent.getChildren().add(index,left);  
  300.                 parent.getChildren().add(index + 1, right);  
  301.                 setEntries(null);  
  302.                 setChildren(null);  
  303.                   
  304.                 //父节点更新关键字  
  305.                 parent.updateInsert(tree);  
  306.                 setParent(null);  
  307.             //如果是根节点      
  308.             }else {  
  309.                 isRoot = false;  
  310.                 INode parent = new INode(false, true);  
  311.                 tree.setRoot(parent);  
  312.                 left.setParent(parent);  
  313.                 right.setParent(parent);  
  314.                 parent.getChildren().add(left);  
  315.                 parent.getChildren().add(right);  
  316.                 setEntries(null);  
  317.                 setChildren(null);  
  318.                   
  319.                 //更新根节点  
  320.                 parent.updateInsert(tree);  
  321.             }  
  322.         }  
  323.     }  
  324.       
  325.     /** 调整节点关键字*/  
  326.     /**
  327.      * 检查节点的有效性
  328.      * @param node
  329.      * @param tree
  330.      */
  331.     protected static void validate(INode node, IBPlusTree tree) {  
  332.          
  333.         // 如果关键字个数与子节点个数相同  
  334.         if (node.getEntries().size() == node.getChildren().size()) {  
  335.             for (int i = 0; i < node.getEntries().size(); i++) {  
  336.                 Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();  
  337.                 if (node.getEntries().get(i).getKey().compareTo(key) != 0) {  
  338.                     node.getEntries().remove(i);  
  339.                     node.getEntries().add(i, new SimpleEntry(key, null));  
  340.                     if(!node.isRoot()){  
  341.                         validate(node.getParent(), tree);  
  342.                     }  
  343.                 }  
  344.             }  
  345.             // 如果子节点数不等于关键字个数但仍大于M / 2并且小于M,并且大于2  
  346.         } else if (node.isRoot() && node.getChildren().size() >= 2   
  347.                 ||node.getChildren().size() >= tree.getOrder() / 2   
  348.                 && node.getChildren().size() <= tree.getOrder()  
  349.                 && node.getChildren().size() >= 2) {  
  350.             node.getEntries().clear();  
  351.             for (int i = 0; i < node.getChildren().size(); i++) {  
  352.                 Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();  
  353.                 node.getEntries().add(new SimpleEntry(key, null));  
  354.                 if (!node.isRoot()) {  
  355.                     validate(node.getParent(), tree);  
  356.                 }  
  357.             }  
  358.         }  
  359.     }  
  360.       
  361.     /** 删除节点后中间节点的更新*/  
  362.     /**
  363.      * 删除节点之后的更新操作
  364.      * @param tree
  365.      */
  366.     protected void updateRemove(IBPlusTree tree) {  
  367.          
  368.         validate(this, tree);  
  369.   
  370.         // 如果子节点数小于M / 2或者小于2,则需要合并节点  
  371.         if (children.size() < tree.getOrder() / 2 || children.size() < 2) {  
  372.             if (isRoot) {  
  373.                 // 如果是根节点并且子节点数大于等于2,OK  
  374.                 if (children.size() >= 2) {  
  375.                     return;  
  376.                 // 否则与子节点合并  
  377.                 } else {  
  378.                     INode root = children.get(0);  
  379.                     tree.setRoot(root);  
  380.                     root.setParent(null);  
  381.                     root.setRoot(true);  
  382.                     setEntries(null);  
  383.                     setChildren(null);  
  384.                 }  
  385.             } else {  
  386.                 //计算前后节点   
  387.                 int currIdx = parent.getChildren().indexOf(this);  
  388.                 int prevIdx = currIdx - 1;  
  389.                 int nextIdx = currIdx + 1;  
  390.                 INode previous = null, next = null;  
  391.                 if (prevIdx >= 0) {  
  392.                     previous = parent.getChildren().get(prevIdx);  
  393.                 }  
  394.                 if (nextIdx < parent.getChildren().size()) {  
  395.                     next = parent.getChildren().get(nextIdx);  
  396.                 }  
  397.                   
  398.                 // 如果前节点子节点数大于M / 2并且大于2,则从其处借补  
  399.                 if (previous != null   
  400.                         && previous.getChildren().size() > tree.getOrder() / 2  
  401.                         && previous.getChildren().size() > 2) {  
  402.                     //前叶子节点末尾节点添加到首位  
  403.                     int idx = previous.getChildren().size() - 1;  
  404.                     INode borrow = previous.getChildren().get(idx);  
  405.                     previous.getChildren().remove(idx);  
  406.                     borrow.setParent(this);  
  407.                     children.add(0, borrow);  
  408.                     validate(previous, tree);  
  409.                     validate(this, tree);  
  410.                     parent.updateRemove(tree);  
  411.                      
  412.                 // 如果后节点子节点数大于M / 2并且大于2,则从其处借补  
  413.                 } else if (next != null   
  414.                         && next.getChildren().size() > tree.getOrder() / 2  
  415.                         && next.getChildren().size() > 2) {  
  416.                     //后叶子节点首位添加到末尾  
  417.                     INode borrow = next.getChildren().get(0);  
  418.                     next.getChildren().remove(0);  
  419.                     borrow.setParent(this);  
  420.                     children.add(borrow);  
  421.                     validate(next, tree);  
  422.                     validate(this, tree);  
  423.                     parent.updateRemove(tree);  
  424.                      
  425.                 // 否则需要合并节点  
  426.                 } else {  
  427.                     // 同前面节点合并  
  428.                     if (previous != null   
  429.                             && (previous.getChildren().size() <= tree.getOrder() / 2 || previous.getChildren().size() <= 2)) {  
  430.                           
  431.                         for (int i = previous.getChildren().size() - 1; i >= 0; i--) {  
  432.                             INode child = previous.getChildren().get(i);  
  433.                             children.add(0, child);  
  434.                             child.setParent(this);  
  435.                         }  
  436.                         previous.setChildren(null);  
  437.                         previous.setEntries(null);  
  438.                         previous.setParent(null);  
  439.                         parent.getChildren().remove(previous);  
  440.                         validate(this, tree);  
  441.                         parent.updateRemove(tree);  
  442.                           
  443.                     // 同后面节点合并  
  444.                     } else if (next != null   
  445.                             && (next.getChildren().size() <= tree.getOrder() / 2 || next.getChildren().size() <= 2)) {  
  446.   
  447.                         for (int i = 0; i < next.getChildren().size(); i++) {  
  448.                             INode child = next.getChildren().get(i);  
  449.                             children.add(child);  
  450.                             child.setParent(this);  
  451.                         }  
  452.                         next.setChildren(null);  
  453.                         next.setEntries(null);  
  454.                         next.setParent(null);  
  455.                         parent.getChildren().remove(next);  
  456.                         validate(this, tree);  
  457.                         parent.updateRemove(tree);  
  458.                     }  
  459.                 }  
  460.             }  
  461.         }  
  462.     }  
  463.       
  464.     /**
  465.      * 删除一棵树上的key
  466.      * @param key
  467.      * @param tree
  468.      */
  469.     public void remove(Comparable key, IBPlusTree tree){  
  470.         //如果是叶子节点  
  471.         if (isLeaf){  
  472.               
  473.             //如果不包含该关键字,则直接返回  
  474.             if (!contains(key)){  
  475.                 return;  
  476.             }  
  477.               
  478.             //如果既是叶子节点又是跟节点,直接删除  
  479.             if (isRoot) {  
  480.                 remove(key);  
  481.             }else {  
  482.                 //如果关键字数大于M / 2,直接删除  
  483.                 if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) {  
  484.                     remove(key);  
  485.                 }else {  
  486.                     //如果自身关键字数小于M / 2,并且前节点关键字数大于M / 2,则从其处借补  
  487.                     if (previous != null   
  488.                             && previous.getEntries().size() > tree.getOrder() / 2  
  489.                             && previous.getEntries().size() > 2  
  490.                             && previous.getParent() == parent) {  
  491.                         int size = previous.getEntries().size();  
  492.                         Entry<Comparable, Object> entry = previous.getEntries().get(size - 1);  
  493.                         previous.getEntries().remove(entry);  
  494.                         //添加到首位  
  495.                         entries.add(0, entry);  
  496.                         remove(key);  
  497.                     //如果自身关键字数小于M / 2,并且后节点关键字数大于M / 2,则从其处借补     
  498.                     }else if (next != null   
  499.                             && next.getEntries().size() > tree.getOrder() / 2  
  500.                             && next.getEntries().size() > 2  
  501.                             && next.getParent() == parent) {  
  502.                         Entry<Comparable, Object> entry = next.getEntries().get(0);  
  503.                         next.getEntries().remove(entry);  
  504.                         //添加到末尾  
  505.                         entries.add(entry);  
  506.                         remove(key);  
  507.                     //否则需要合并叶子节点      
  508.                     }else {  
  509.                         //同前面节点合并  
  510.                         if (previous != null   
  511.                                 && (previous.getEntries().size() <= tree.getOrder() / 2 || previous.getEntries().size() <= 2)  
  512.                                 && previous.getParent() == parent) {  
  513.                             for (int i = previous.getEntries().size() - 1; i >=0; i--) {  
  514.                                 //从末尾开始添加到首位  
  515.                                 entries.add(0, previous.getEntries().get(i));  
  516.                             }  
  517.                             remove(key);  
  518.                             previous.setParent(null);  
  519.                             previous.setEntries(null);  
  520.                             parent.getChildren().remove(previous);  
  521.                             //更新链表  
  522.                             if (previous.getPrevious() != null) {  
  523.                                 INode temp = previous;  
  524.                                 temp.getPrevious().setNext(this);  
  525.                                 previous = temp.getPrevious();  
  526.                                 temp.setPrevious(null);  
  527.                                 temp.setNext(null);                           
  528.                             }else {  
  529.                                 tree.setHead(this);  
  530.                                 previous.setNext(null);  
  531.                                 previous = null;  
  532.                             }  
  533.                         //同后面节点合并     
  534.                         }else if(next != null   
  535.                                 && (next.getEntries().size() <= tree.getOrder() / 2 || next.getEntries().size() <= 2)  
  536.                                 && next.getParent() == parent){  
  537.                             for (int i = 0; i < next.getEntries().size(); i++) {  
  538.                                 //从首位开始添加到末尾  
  539.                                 entries.add(next.getEntries().get(i));  
  540.                             }  
  541.                             remove(key);  
  542.                             next.setParent(null);  
  543.                             next.setEntries(null);  
  544.                             parent.getChildren().remove(next);  
  545.                             //更新链表  
  546.                             if (next.getNext() != null) {  
  547.                                 INode temp = next;  
  548.                                 temp.getNext().setPrevious(this);  
  549.                                 next = temp.getNext();  
  550.                                 temp.setPrevious(null);  
  551.                                 temp.setNext(null);  
  552.                             }else {  
  553.                                 next.setPrevious(null);  
  554.                                 next = null;  
  555.                             }  
  556.                         }  
  557.                     }  
  558.                 }  
  559.                 parent.updateRemove(tree);  
  560.             }  
  561.         //如果不是叶子节点   
  562.         }else {  
  563.             //如果key小于等于节点最左边的key,沿第一个子节点继续搜索  
  564.             if (key.compareTo(entries.get(0).getKey()) <= 0) {  
  565.                 children.get(0).remove(key, tree);  
  566.             //如果key大于节点最右边的key,沿最后一个子节点继续搜索  
  567.             }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {  
  568.                 children.get(children.size()-1).remove(key, tree);  
  569.             //否则沿比key大的前一个子节点继续搜索  
  570.             }else {  
  571.                 for (int i = 0; i < entries.size(); i++) {  
  572.                     if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {  
  573.                         children.get(i).remove(key, tree);  
  574.                         break;  
  575.                     }  
  576.                 }     
  577.             }  
  578.         }  
  579.     }  
  580.       
  581.     /** 判断当前节点是否包含该关键字*/  
  582.     /**
  583.      *
  584.      * @param key
  585.      * @return
  586.      */
  587.     protected boolean contains(Comparable key) {  
  588.         for (Entry<Comparable, Object> entry : entries) {  
  589.             if (entry.getKey().compareTo(key) == 0) {  
  590.                 return true;  
  591.             }  
  592.         }  
  593.         return false;  
  594.     }  
  595.       
  596.     /** 插入到当前节点的关键字中*/  
  597.     /**
  598.      *
  599.      * @param key
  600.      * @param obj
  601.      */
  602.     protected void insertOrUpdate(Comparable key, Object obj){  
  603.         Entry<Comparable, Object> entry = new SimpleEntry<Comparable, Object>(key, obj);  
  604.         //如果关键字列表长度为0,则直接插入  
  605.         if (entries.size() == 0) {  
  606.             entries.add(entry);  
  607.             return;  
  608.         }  
  609.         //否则遍历列表  
  610.         for (int i = 0; i < entries.size(); i++) {  
  611.             //如果该关键字键值已存在,则更新  
  612.             if (entries.get(i).getKey().compareTo(key) == 0) {  
  613.                 entries.get(i).setValue(obj);  
  614.                 return;  
  615.             //否则插入   
  616.             }else if (entries.get(i).getKey().compareTo(key) > 0){  
  617.                 //插入到链首  
  618.                 if (i == 0) {  
  619.                     entries.add(0, entry);  
  620.                     return;  
  621.                 //插入到中间  
  622.                 }else {  
  623.                     entries.add(i, entry);  
  624.                     return;  
  625.                 }  
  626.             }  
  627.         }  
  628.         //插入到末尾  
  629.         entries.add(entries.size(), entry);  
  630.     }  
  631.       
  632.     /** 删除节点*/  
  633.     /**
  634.      * 函数的重写:根据key来进行删除
  635.      * @param key
  636.      */
  637.     protected void remove(Comparable key){  
  638.         int index = -1;  
  639.         for (int i = 0; i < entries.size(); i++) {  
  640.             if (entries.get(i).getKey().compareTo(key) == 0) {  
  641.                 index = i;  
  642.                 break;  
  643.             }  
  644.         }  
  645.         if (index != -1) {  
  646.             entries.remove(index);  
  647.         }  
  648.     }  
  649.    
  650.    
  651.     /**
  652.      *  重写这个toString() 函数
  653.      */
  654.     public String toString(){  
  655.         StringBuilder sb = new StringBuilder();  
  656.         sb.append("isRoot: ");  
  657.         sb.append(isRoot);  
  658.         sb.append(", ");  
  659.         sb.append("isLeaf: ");  
  660.         sb.append(isLeaf);  
  661.         sb.append(", ");  
  662.         sb.append("keys: ");  
  663.         for (Entry entry : entries){  
  664.             sb.append(entry.getKey());  
  665.             sb.append(", ");  
  666.         }  
  667.         sb.append(", ");  
  668.         
  669.         // 可以直接返回一个对象的属性
  670.         return sb.toString();  
  671.          
  672.     }  
  673.        
  674.        
  675. }
复制代码








上一篇:【JavaScript进阶】利用HTML5中的Canvas实现小球运动的Animation动画模型实现思路
下一篇:【C++源码】自定义实现一个Set和List的集合源码资料共享
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案; 如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

微信扫一扫

快速回复 返回顶部 返回列表