This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
/* | |
* Unlike a binary search tree, each node of a B-tree may have a variable number of keys and children. | |
* The keys are stored in non-decreasing order. Each node either is a leaf node or | |
* it has some associated children that are the root nodes of subtrees. | |
* The left child node of a node's element contains all nodes (elements) with keys less than or equal to the node element's key | |
* but greater than the preceding node element's key. | |
* If a node becomes full, a split operation is performed during the insert operation. | |
* The split operation transforms a full node with 2*T-1 elements into two nodes with T-1 elements each |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
http://wlh0706-163-com.iteye.com/blog/1856247 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.ds.tree.rbtree; | |
import java.util.LinkedList; | |
import java.util.Queue; | |
import com.ds.tree.adt.BinarySearchTree; | |
import com.ds.tree.adt.TreeTraversal; | |
/** |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.ds.tree.adt; | |
public interface TreeTraversal { | |
/** | |
* visit binary tree pre-order | |
* @param root binary tree root node | |
*/ | |
public String preOrder(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.ds.tree.adt; | |
public interface BinarySearchTree<T extends Comparable<? super T>> { | |
/** | |
* search the tree and find the specific data if exist | |
* @param root tree root node | |
* @param data element data to search | |
* @return true if data exist, or return false | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.ds.tree.avltree; | |
import java.util.LinkedList; | |
import java.util.Queue; | |
import com.ds.tree.adt.BinarySearchTree; | |
import com.ds.tree.adt.TreeTraversal; | |
public class AVLTreeImpl<T extends Comparable<? super T>> implements BinarySearchTree<T>,TreeTraversal { |