Java data structure and algorithm analysis (nine) -- B tree

Original 2017, 09, 27, 09:41:56

Introduction to B tree

Definition

In computer science, the B tree (English: B-tree) is a self balancing tree that keeps data in order. This data structure enables data lookups, sequential access, insertion, and deletion operations to be done in log time.

Characteristic

The B tree of order M is a tree with the following characteristics:
The 1. data item is stored on the leaves
2. non leaf nodes until the M-1 keyword indicates the direction of the search: the keyword I stands for the smallest keyword in the subtree i+1
The root of a 3. tree, or a leaf, or its son between 2 and M
4. except for all non leaf nodes the number of sons between M/2 and M.
5. all leaves are at the same depth and have data items between L/2 and L

For example: (M=3)
Here's a picture description

Find and insert

For convenience, a special sentry key is used, which is smaller than all other keys and is represented by *.

In the beginning, the B tree contains only one root node, and the root node contains only the anchor key at initialization.

Each key in the inner node is associated with a node, and the subtree of this node is the root. All keys are greater than or equal to the key associated with this node, but less than all other keys.

Here's a picture description
Here's a picture description

Implementation of B tree


PublicClass BTree2<K,V>
{
    PrivateStatic, Log, logger = LogFactory.getLog (BTree.Class);

    / * *
* the key pair in the B tree node.
* <p/>
* the nodes in the B tree store key value pairs.
* access values by key.
*
*@param<K> - key type
*@param<V> - value type
* /
    PrivateStaticClass Entry<K,V>
{
        PrivateK key;
        PrivateV value;

Public Entry (K, K, V, V)
{
            This.key = k;
            This.value = v;
}

Public, K, getKey ()
{
            ReturnKey;
}

Public, V, getValue ()
{
            ReturnValue;
}

Public void setValue (V value)
{
            This.value = value;
}

        @Override
Public, String, toString ()
{
            ReturnKey +":"+ value;
}
}

    / * *
* searching for the return result of a given key value in the B tree node.
* <p/>
* the result consists of two parts. The first part indicates whether the search was successful,
* if the search succeeds, the second part represents the location of the given key value in the B tree node,
* if the lookup fails, the second part indicates where the given key value should be inserted.
* /
    PrivateStaticClass SearchResult<V>
{
        PrivateBoolean exist;
        PrivateInt index;
        PrivateV value;

Public SearchResult (Boolean, exist, int, index)
{
            This.exist = exist;
            This.index = index;
}

Public SearchResult (Boolean, exist, int, index, V, value)
{
            This(exist, index);
            This.value = value;
}

Public, Boolean, isExist ()
{
            ReturnExist;
}

Public, int, getIndex ()
{
            ReturnIndex;
}

Public, V, getValue ()
{
            ReturnValue;
}
}

    / * *
* nodes in the B tree.
*
* TODO needs to consider access in concurrent cases.
* /
    PrivateStaticClass BTreeNode<K,V>
{
        A key node / * * * / store, non descending
        PrivateList<Entry<K, V>>, entrys;
        * / / * * node node
        PrivateList<BTreeNode<K, V>>, children;
        Whether the leaf node * / / * *
        PrivateBoolean leaf;
        The key comparison object * / / * *
        PrivateComparator<K> kComparator;

        PrivateBTreeNode ()
{
Entrys =NewArrayList<Entry<K, V>> ();
Children =NewArrayList<BTreeNode<K, V>> ();
= leafFalse;
}

Public BTreeNode (Comparator<K> kComparator)
{
            This();
            This.kComparator = kComparator;
}

Public, Boolean, isLeaf ()
{
            ReturnLeaf;
}

Public void setLeaf (Boolean leaf)
{
            This.leaf = leaf;
}

        / * *
* returns the number of entries. If it is a non leaf node, according to the definition of the B tree,
* the number of child nodes in this node is ({)@link#size ()} + 1).
*
*@returnNumber of keywords
* /
Public, int, size ()
{
            ReturnEntrys.size ();
}

        @SuppressWarnings("Unchecked."")
Int compare (K, key1, K, key2)
{
            Return= = kComparatorNull((Comparable<K>) key1).CompareTo (key2): kComparator.compare (key1, key2);
}

        / * *
* find a given key in the node.
* if a given key exists in the node, a <code>SearchResult</code> is returned,
* identifies the lookup success, the index of the given key in the node, and the value associated with the given key;
* if it does not exist, return <code>SearchResult</code>,
* identifies this lookup failure where the given key should be inserted. The key associated value is null.
* <p/>
* if the lookup fails, the index field in the returned result is [0, {@link(#size)}];
* if the search succeeds, the index field in the returned result is [0, {@link#size ()} - 1]
* <p/>
* this is a two bit lookup algorithm that guarantees time complexity of O (log (T)).
*
*@paramKey - given key values
*@return- finding results
* /
Public SearchResult<V> searchKey (K key)
{
Int Low =Zero;
Int high = entrys.size () -One;
Int mid =Zero;
            While(low high)
{
Mid = (low + high) /Two;/ / the first that writing and implementation of the BTree, l+h can not overflow
Entry<K, V>, entry = entrys.get (mid);
                If(compare (entry.getKey), (key) = =Zero)/ / entrys.get (MID) (.GetKey = key)
                    Break;
                Else If(compare (entry.getKey (), key) >Zero)/ / entrys.get (MID).GetKey (key).
High = mid -One;
                Else / / entry.get (MID).GetKey (key).
Low = mid +One;
}
Boolean result =False;
Int index =Zero;
V value =Null;
            If(low high)Show / find success
{
Result =True;
Index = mid;Index said the location where the elements / /
Value = entrys.get (index).GetValue ();
}
            Else
{
Result =False;
Index = low;Index said the element should be inserted / / position
}
            Return NewSearchResult<V> (result, index, value);
}

        / * *
* appends a given item to the end of the node,
* you need to ensure that after you call the method, the entry in the node is still
* stored in non descending order by keyword.
*
*@paramEntry - the given item
* /
Public, void, addEntry (Entry<K, V>, entry)
{
Entrys.add (entry);
}

        / * *
* delete the <code>entry</code> of the given index.
* <p/>
* you need to ensure that the given index is legal.
*
*@paramIndex - given index
*@paramAn item at the given index
* /
Public, Entry<K, V>, removeEntry (int, index)
{
            ReturnEntrys.remove (index);
}

        / * *
* gets the entry of the given index in the node.
* <p/>
* you need to ensure that the given index is legal.
*
*@paramIndex - given index
*@returnAn item of a given index in a node
* /
Public, Entry<K, V>, entryAt (int, index)
{
            ReturnEntrys.get (index);
}

        / * *
* if the given key exists in the node, the value associated with it is updated.
* otherwise insert.
*
*@paramEntry - the given item
*@returnNull, if the key is not present before the node, otherwise the value associated with the return of the given key
* /
Public, V, putEntry (Entry<K, V>, entry)
{
SearchResult<V> result = searchKey (entry.getKey ());
            If(result.isExist ())
{
V oldValue = entrys.get (result.getIndex ()).GetValue ();
Entrys.get (result.getIndex ()).SetValue (entry.getValue ());
                ReturnOldValue;
}
            Else
{
InsertEntry (entry, result.getIndex ());
                Return Null;
}
}

        / * *
* inserts a given item in the node,
* this method ensures that the key value is stored in non descending order after insertion.
* <p/>
* however, the time complexity of the method is O (t).
* <p/>
* <b> note: key repetition is not allowed in the </b>B tree.
*
*@paramEntry - given key values
*@returnTrue, if the insert succeeds, false, if the insertion fails
* /
Public, Boolean, insertEntry (Entry<K, V>, entry)
{
SearchResult<V> result = searchKey (entry.getKey ());
            If(result.isExist ())
                Return False;
            Else
{
InsertEntry (entry, result.getIndex ());
                Return True;
}
}

        / * *
* inserts a given item at the location of the given index in the node,
* you need to make sure the entry is in the right place.
*
*@paramKey - given key values
*@paramIndex - given index
* /
Public, void, insertEntry (Entry<K, V>, entry, int, index)
{
            *
* it's really disgusting to plug in by creating a new ArrayList, so let's go ahead
If only there was a reallocate like C.
* /
List<Entry<K, V>>, newEntrys =NewArrayList<Entry<K, V>> ();
Int i =Zero;
            / / index = 0 or index = (keys.size) have no problem
            For(; I < index; + + I)
NewEntrys.add (entrys.get (I));
NewEntrys.add (entry);
            For(I; entrys.size); I < (+ +)
NewEntrys.add (entrys.get (I));
Entrys.clear ();
Entrys = newEntrys;
}

        / * *
* returns the child node of the given index in the node.
* <p/>
* you need to ensure that the given index is legal.
*
*@paramIndex - given index
*@returnThe child node corresponding to the given index
* /
Public, BTreeNode<K, V>, childAt (int, index)
{
            If(isLeaf ())
                Throw NewUnsupportedOperationException ("Leaf, node, doesn't, have, children.."");
            ReturnChildren.get (index);
}

        / * *
* appends a given child node to the end of that node.
*
*@paramChild - given child nodes
* /
Public, void, addChild (BTreeNode<K, V>, child)
{
Children.add (child);
}

        / * *
* deletes a child node at the given index position in that node.
* </p>
* you need to ensure that the given index is legal.
*
*@paramIndex - given index
* /
Public void removeChild (int index)
{
Children.remove (index);
}

        / * *
* inserts a given child node into a given index in that node
* position.
*
*@paramChild - given child nodes
*@paramIndex - child node with insertion location
* /
Public, void, insertChild (BTreeNode<K, V>, child, int, index)
{
List<BTreeNode<K, V>>, newChildren =NewArrayList<BTreeNode<K, V>> ();
Int i =Zero;
            For(; I < index; + + I)
NewChildren.add (children.get (I));
NewChildren.add (child);
            For(I; children.size); I < (+ +)
NewChildren.add (children.get (I));
Children = newChildren;
}
}

    PrivateStaticFinalInt DEFAULT_T =Two;

    The root node of the B tree / * * * /
    PrivateBTreeNode<K, V>, root;
    According to the definition of B / * * tree, the N keyword B tree number of each non root node satisfies (T - 1) < < = n (2t - 1).
    PrivateInt t = DEFAULT_T;
    The number of the smallest non key / * * * root node in the
    PrivateInt minKeySize = t -One;
    The number of the largest non key / * * * root node in the
    PrivateInt maxKeySize =Two- *tOne;
    The key comparison object * / / * *
    PrivateComparator<K> kComparator;

    / * *
* construct a B tree, and use the natural ordering method for key values
* /
Public, BTree ()
{
= rootNewBTreeNode<K, V> ();
Root.setLeaf (True);
}

Public BTree (int t)
{
        This();
        This.t = t;
MinKeySize = t -One;
MaxKeySize =Two- *tOne;
}

    / * *
* constructing a B tree by comparing the function object with a given key value.
*
*@paramKComparator - key comparison function object
* /
Public BTree (Comparator<K> kComparator)
{
= rootNewBTreeNode<K, V> (kComparator);
Root.setLeaf (True);
        This.kComparator = kComparator;
}

Public BTree (Comparator<K>, kComparator, int, t)
{
        This(kComparator);
        This.t = t;
MinKeySize = t -One;
MaxKeySize =Two- *tOne;
}

    @SuppressWarnings("Unchecked."")
Int compare (K, key1, K, key2)
{
        Return= = kComparatorNull((Comparable<K>) key1).CompareTo (key2): kComparator.compare (key1, key2);
}

    / * *
* searching for a given key.
*
*@paramKey - given key values
*@returnThe value associated with the key, if it exists, otherwise null
* /
Public V search (K key)
{
        ReturnSearch (root, key);
}

    / * *
* recursive searches in subtrees with a given node as root
* given <code>key</code>
*
*@paramNode - the root node of the subtree
*@paramKey - given key values
*@returnThe value associated with the key, if it exists, otherwise null
* /
    PrivateV search (BTreeNode<K, V>, node, K, key)
{
SearchResult<V> result = node.searchKey (key);
        If(result.isExist ())
            ReturnResult.getValue ();
        Else
{
            If(node.isLeaf ())
                Return Null;
            Else
Search (node.childAt (result.getIndex ()), key);

}
        Return Null;
}

    / * *
* splitting a full child node <code>childNode</code>.
* <p/>
* you need to make sure that the given child node is full.
*
*@paramParentNode - parent node
*@paramChildNode - full child node
*@paramIndex - the index of the full child node in the parent node
* /
    PrivateVoid, splitNode (BTreeNode<K, V>, parentNode, BTreeNode<K, V>, childNode, int, index)
{
Assert (childNode.size) = maxKeySize;

BTreeNode<K, V>, siblingNode =NewBTreeNode<K, V> (kComparator);
SiblingNode.setLeaf (childNode.isLeaf ());
        The index will be / / child nodes for [t, 2T - 2] (T - 1) a new node is inserted
        For(int, I =ZeroI; minKeySize; I) + +
SiblingNode.addEntry (childNode.entryAt (T + I));
        / / extraction middle term full subcategory node, which is index (T - 1)
Entry<K, V>, entry = childNode.entryAt (T -One);
        Delete the index node in full / [t - 1, 2T - 2] t items
        For(int, I = maxKeySize -OneI - > = t;One- - - I)
ChildNode.removeEntry (I);
        If(... ChildNode.isLeaf ())/ / if full subcategory node is not a leaf node, it also need to deal with its child nodes
{
            The index will be sub node / / [t, t sub node 2T - 1] insert the new node
            For(int, I =ZeroI < minKeySize +OneI + +);
SiblingNode.addChild (childNode.childAt (T + I));
            / / delete index for full node [t, t sub node 2T - 1]
            For(int i = maxKeySize; I > = t; I)
ChildNode.removeChild (I);
}
        / / entry will be inserted into the parent node
ParentNode.insertEntry (entry, index);
        / / insert the new node parent node
ParentNode.insertChild (siblingNode, index +)One);
}

    / * *
* inserts a given item in a non full node.
*
*@paramNode - non full node
*@paramEntry - the given item
*@returnTrue, if there is no item in the B tree, otherwise false
* /
    PrivateBoolean, insertNotFull (BTreeNode<K, V>, node, Entry<K, V>, entry)
{
Assert node.size () < maxKeySize;

        If(node.isLeaf ())/ / if is directly inserted into the leaf node,
            ReturnNode.insertEntry (entry);
        Else
{
            Entry should be inserted in a given / * find the location of nodes, then the entry should be inserted
* in the subtree corresponding to this location
* /
SearchResult<V> result = node.searchKey (entry.getKey ());
            If there is a direct return / /, failure
            If(result.isExist ())
                Return False;
BTreeNode<K, V>, childNode = node.childAt (result.getIndex ());
            If(childNode.size) (= =Two- *tOne)If the node is full of node / /
{
                The first division /
SplitNode (node, childNode, result.getIndex ());
                If the new generation of the key / given entry key is greater than the split, we need to insert the new item on the right,
* otherwise left.
* /
                If(compare (entry.getKey ()), node.entryAt (result.getIndex ()),.GetKey ())Zero)
ChildNode = node.childAt (result.getIndex () +)One);
}
            ReturnInsertNotFull (childNode, entry);
}
}

    / * *
* insert a key key pair into the B tree.
*
*@paramKey - bond
*@paramValue - value
*@paramTrue, if there is no item in the B tree, otherwise false
* /
Public, Boolean, insert (K, key, V, value)
{
        If(root.size) (= maxKeySize)/ / if the root node is full, then B trees grow taller
{
BTreeNode<K, V>, newRoot =NewBTreeNode<K, V> (kComparator);
NewRoot.setLeaf (False);
NewRoot.addChild (root);
SplitNode (newRoot, root),Zero);
Root = newRoot;
}
        ReturnInsertNotFull (root,NewEntry<K, V> (key, value);
}

    / * *
* if a given key is present, the value associated with the update key is updated,
* otherwise insert a given item.
*
*@paramNode - non full node
*@paramEntry - the given item
*@returnTrue, if there is no item in the B tree, otherwise false
* /
    PrivateV, putNotFull (BTreeNode<K, V>, node, Entry<K, V>, entry)
{
Assert node.size () < maxKeySize;

        If(node.isLeaf ())/ / if is directly inserted into the leaf node,
            ReturnNode.putEntry (entry);
        Else
{
            Entry should be inserted in a given / * find the location of nodes, then the entry should be inserted
* in the subtree corresponding to this location
* /
SearchResult<V> result = node.searchKey (entry.getKey ());
            If there is / / update.
            If(result.isExist ())
                ReturnNode.putEntry (entry);
BTreeNode<K, V>, childNode = node.childAt (result.getIndex ());
            If(childNode.size) (= =Two- *tOne)If the node is full of node / /
{
                The first division /
SplitNode (node, childNode, result.getIndex ());
                If the new generation of the key / given entry key is greater than the split, we need to insert the new item on the right,
* otherwise left.
* /
                If(compare (entry.getKey ()), node.entryAt (result.getIndex ()),.GetKey ())Zero)
ChildNode = node.childAt (result.getIndex () +)One);
}
            ReturnPutNotFull (childNode, entry);
}
}

    / * *
* if the given key exists in the B tree, the update value is updated.
* otherwise insert.
*
*@paramKey - bond
*@paramValue - value
*@returnIf a given key exists in the B tree, the previous value is returned, otherwise null
* /
Public, V, put (K, key, V, value)
{
        If(root.size) (= maxKeySize)/ / if the root node is full, then B trees grow taller
{
BTreeNode<K, V>, newRoot =NewBTreeNode<K, V> (kComparator);
NewRoot.setLeaf (False);
NewRoot.addChild (root);
SplitNode (newRoot, root),Zero);
Root = newRoot;
}
        ReturnPutNotFull (root,NewEntry<K, V> (key, value);
}

    / * *
* removes an item associated with a given key from the B tree.
*
*@paramKey - given key
*@returnIf an item associated with a given key exists in the B tree, the deleted item is returned, otherwise null
* /
Public, Entry<K, V>, delete (K, key)
{
        ReturnDelete (root, key);
}

    / * *
* deletes an item associated with a given key from the subtree with a given <code>node</code> as the root.
* <p/>
* delete the implementation of the idea, please refer to the introduction to algorithms, the second edition of the eighteenth chapter.
*
*@paramNode - given nodes
*@paramKey - given key
*@returnIf an item associated with a given key exists in the B tree, the deleted item is returned, otherwise null
* /
    PrivateEntry<K, V>, delete (BTreeNode<K, V>, node, K, key)
{
        The process / need to ensure that the implementation of the non root node deletion operation, the key number is at least t.
Assert node.size (T) node || > = = = root;

SearchResult<V> result = node.searchKey (key);
        *
* because this is the case of successful search, 0 (result.getIndex) (node.size < < = (- 1)),
* therefore, (result.getIndex () + 1) will not overflow.
* /
        If(result.isExist ())
{
            If the key nodes in node / / 1., and is a leaf node, then delete.
            If(node.isLeaf ())
                ReturnNode.removeEntry (result.getIndex ());
            Else
{
                If the node in node / / 2.a to key before the child node contains at least t items
BTreeNode<K, V>, leftChildNode = node.childAt (result.getIndex ());
                If(leftChildNode.size) (> = t)
{
                    The use of leftChildNode / / the last item instead need to delete the items in the node
Node.removeEntry (result.getIndex ());
Node.insertEntry (leftChildNode.entryAt (leftChildNode.size ()) -One) (result.getIndex ());
                    / / a recursive delete left child node in the last item
                    ReturnDelete (leftChildNode, leftChildNode.entryAt (leftChildNode.size ()) -One(.GetKey ());
}
                Else
{
                    If the node in node / / 2.b at key after the child node contains at least t keyword
BTreeNode<K, V>, rightChildNode = node.childAt (result.getIndex () +)One);
                    If(rightChildNode.size) (> = t)
{
                        The use of rightChildNode / / the first item to delete instead of the items in the node
Node.removeEntry (result.getIndex ());
Node.insertEntry (rightChildNode.entryAt ()Zero) (result.getIndex ());
                        Right recursive delete the first item / sub node in the
                        ReturnDelete (rightChildNode, rightChildNode.entryAt)Zero(.GetKey ());
}
                    Else Before and after key / / 2.c to key node contains only a T-1
{
Entry<K, V>, deletedEntry = node.removeEntry (result.getIndex ());
Node.removeChild (result.getIndex () +One);
                        / / will merge associated with key in node and rightChildNode in leftChildNode
LeftChildNode.addEntry (deletedEntry);
                        For(int, I =ZeroI; rightChildNode.size; I) < (+ +)
LeftChildNode.addEntry (rightChildNode.entryAt (I));
                        / / will merge into leftChildNode sub node in rightChildNode, if any
                        If(... RightChildNode.isLeaf ())
{
                            For(int, I =ZeroI; rightChildNode.size; I) (< = + +)
LeftChildNode.addChild (rightChildNode.childAt (I));
}
                        ReturnDelete (leftChildNode, key);
}
}
}
}
        Else
{
            *
* because it is the failure to find, 0 < = result.getIndex (< = node.size) (),
* therefore (result.getIndex () + 1) will overflow.
* /
            If(node.isLeaf ())/ / if key is not in the node node, and is a leaf node, not what to do, because the key is not in the B tree
{
Logger.info ("The key:.""+ key +"Isn't, in, this, BTree.."");
                Return Null;
}
BTreeNode<K, V>, childNode = node.childAt (result.getIndex ());
            If(childNode.size) (> = t)If a node / / / / no less than t, then recursively delete
                ReturnDelete (childNode, key);
            Else / / 3
{
                To find the right node / brother
BTreeNode<K, V>, siblingNode =Null;
Int, siblingIndex = -One;
                If(result.getIndex () < node.size ())Right / / brother node
{
                    If(node.childAt (result.getIndex () +)One) (.Size) > = t)
{
SiblingNode = node.childAt (result.getIndex () +)One);
SiblingIndex = result.getIndex () +One;
}
}
                / / if brother node right does not meet the conditions, then try to the left of the brother node
                If(siblingNode = =Null)
{
                    If(result.getIndex () >Zero)Left / / brother node
{
                        If(node.childAt (result.getIndex ()) -One) (.Size) > = t)
{
SiblingNode = node.childAt (result.getIndex ()) -One);
SiblingIndex = result.getIndex () -One;
}
}
}
                3.a / / there is an adjacent sibling node contains at least t items
                If(siblingNode = =!Null)
{
                    If(siblingIndex < result.getIndex ())/ / left brother node to meet the conditions
{
ChildNode.insertEntry (node.entryAt (siblingIndex)),Zero);
Node.removeEntry (siblingIndex);
Node.insertEntry (siblingNode.entryAt (siblingNode.size ()) -One) (siblingIndex);
SiblingNode.removeEntry (siblingNode.size () -One);
                        / / the last child left siblings moved to childNode
                        If(... SiblingNode.isLeaf ())
{
ChildNode.insertChild (siblingNode.childAt (siblingNode.size ()),Zero);
SiblingNode.removeChild (siblingNode.size ());
}
}
                    Else Right / brother node to meet the conditions
{
ChildNode.insertEntry (node.entryAt (result.getIndex ()), childNode.size () -One);
Node.removeEntry (result.getIndex ());
Node.insertEntry (siblingNode.entryAt ()Zero) (result.getIndex ());
SiblingNode.removeEntry (Zero);
                        The first child / right sibling node to move to childNode
                        / / childNode.insertChild (siblingNode.childAt) (0), childNode.size (+ 1);
                        If(... SiblingNode.isLeaf ())
{
ChildNode.addChild (siblingNode.childAt ()Zero));
SiblingNode.removeChild (Zero);
}
}
                    ReturnDelete (childNode, key);
}
                Else / / 3.b if its adjacent node contains a T-1.
{
                    If(result.getIndex () < node.size ())Right there / brother, additional directly behind
{
BTreeNode<K, V>, rightSiblingNode = node.childAt (result.getIndex () +)One);
ChildNode.addEntry (node.entryAt (result.getIndex ()));
Node.removeEntry (result.getIndex ());
Node.removeChild (result.getIndex () +One);
                        For(int, I =ZeroI; rightSiblingNode.size; I) < (+ +)
ChildNode.addEntry (rightSiblingNode.entryAt (I));
                        If(... RightSiblingNode.isLeaf ())
{
                            For(int, I =ZeroI; rightSiblingNode.size; I) (< = + +)
ChildNode.addChild (rightSiblingNode.childAt (I));
}
}
                    Else / / left in front of the insertion node
{
BTreeNode<K, V>, leftSiblingNode = node.childAt (result.getIndex ()) -One);
ChildNode.insertEntry (node.entryAt (result.getIndex ()) -One),Zero);
Node.removeEntry (result.getIndex () -One);
Node.removeChild (result.getIndex () -One);
                        For(int, I = leftSiblingNode.size () -One> = I;Zero- - - I)
ChildNode.insertEntry (leftSiblingNode.entryAt (I)),Zero);
                        If(... LeftSiblingNode.isLeaf ())
{
                            For(int) (I = leftSiblingNode.size; I =Zero- - - I)
ChildNode.insertChild (leftSiblingNode.childAt (I)),Zero);
}
}
                    / / if node is root and node do not contain any items.
                    If(node = = root & & node.size (= =)Zero)
Root = childNode;
                    ReturnDelete (childNode, key);
}
}
}
}

    / * *
* a simple hierarchical traversal of the B tree is implemented for outputting the B tree.
* /
Public, void, output ()
{
Queue<BTreeNode<K, V>>, queue =NewLinkedList<BTreeNode<K, V>> ();
Queue.offer (root);
        While(... Queue.isEmpty ())
{
BTreeNode<K, V>, node = queue.poll ();
            For(int, I =ZeroI; node.size; I) < (+ +)
System.out.print (node.entryAt (I) +"");
System.out.println ();
            If(... Node.isLeaf ())
{
                For(int, I =ZeroI; node.size; I) (< = + +)
Queue.offer (node.childAt (I));
}
}
}

Public, static, void, main (String[], args)
{
Random random =NewRandom ();
BTree2<Integer, Integer>, BTREE =NewBTree2<Integer, Integer>Three);
List<Integer> save =NewArrayList<Integer> ();
        For(int, I =ZeroI; "TenI + +);
{
Int r = random.nextIntOne hundred);
Save.add (R);
System.out.println (R);
Btree.insert (R, R);
}

System.out.println ("Conducting");
Btree.output ();
System.out.println ("Conducting");
Btree.delete (save.get ()Zero));
Btree.output ();
}
}
Copyright statement: This article is original article for blogger. Without permission from blogger, it is forbidden to reprint. Report

Related articles recommended

Data structures and algorithms -- C++ implementation of B tree

Data structures and algorithms -- C++ implementation of B tree
  • Linux_ever
  • Linux_ever
  • 2016-05-13 11:55
  • Nine hundred and twenty

Java source collection class, TreeMap learning 1 - data structure 4, balance two fork tree, insert an element recursive algorithm

A recursive algorithm for inserting a new element into the balanced two sorted tree (see the book "C") A balanced two fork sorting tree BBST (Balanced Binary Search Tree) insert a new element, e recursive algorithm has the following several...

Data structures and algorithms Java Edition - two fork tree and its traversal

Two fork tree can be expressed in sequential storage structure, or can be expressed by two linked list, but the sequential storage structure is only suitable for storing completely two fork tree...... This semester I learned the data structure of the book, so I'm going to use Java to implement tables, teams, stacks, trees. If you're interested, you can...

Data structures and algorithms Java version - Huffman tree

Huffman tree, also known as the best two fork tree, is an application of two fork tree, it is the shortest path weight path, in the information retrieval is more common. This semester I learned the data structure of the book, so I'm going to use Java to implement tables, teams, stacks, trees. If you're interested, you can keep an eye on my follow-up...
  • Xichang702
  • Xichang702
  • 2017-06-26 17:39
  • One hundred and seventy-three
Back top
Collection assistant
Bad information report
You report articles:Depth learning: derivation of forward and backward propagation algorithms in neural networks
Report reason:
Reason supplement:

(only 30 words are allowed at most)