adderllyer

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 {

adderllyer

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
	 */

adderllyer

package com.ds.tree.adt;

public interface TreeTraversal {
	
	/**
	 * visit binary tree pre-order
	 * @param root binary tree root node
	 */
	public String preOrder();

adderllyer

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;


/**

adderllyer

http://wlh0706-163-com.iteye.com/blog/1856247

adderllyer

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