二叉查找树
二叉查找树出现的目的是使查询的速率整体能够维持在O(logn)上,而又不像链表那样查询一定需要O(logN)的时间复杂度,和数组那样在增删上会引起整个数组进行重构导致的效率问题.
二叉查找树的特点
- 二叉查找树的的左子节点一定比当前节点小，右子节点一定比当前节点大.
- 二叉查找树不允许存在相同的值.
这样在理想的情况下,二叉查找树的查询效率就在O(logN)上了.
二叉查找树的实现
package Tree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Created by Hammy on 2018/3/3.
*/
public class BST<T extends Comparable> implements BinarySearchTree<T>
{
public TreeNode<T> root;
public BST(){
this.root = null;
}
public BST(T data){
root = new TreeNode<T>(data,null,null);
}
@Override
public boolean isEmpty() {
return size()==0;
}
@Override
public int size() {
if(root==null)
return 0;
return size(root);
}
private int size(TreeNode<T> node){
if(node==null)
return 0;
return size(node.left) + 1 + size(node.right);
}
@Override
public int height() {
if(root==null){
return 0;
}
return height(root);
}
private int height(TreeNode<T> node){
if(node==null)
return 0;
int left = height(node.left);
int right = height(node.right);
return (left>right)?(left+1):(right+1);
}
@Override
public String preOrder() {
StringBuffer stringBuffer = new StringBuffer();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> tempNode = root;
while(tempNode!=null||!stack.isEmpty()){
if(tempNode!=null){
stringBuffer.append(tempNode.data+",");
stack.push(tempNode);
tempNode=tempNode.left;
}else{
tempNode=stack.pop();
tempNode=tempNode.right;
}
}
return stringBuffer.toString();
}
@Override
public String inOrder() {
StringBuffer stringBuffer = new StringBuffer();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> tempNode = root;
while(tempNode!=null||!stack.isEmpty()){
while(tempNode!=null){
stack.push(tempNode);
tempNode=tempNode.left;
}
if(!stack.isEmpty()){
tempNode=stack.pop();
stringBuffer.append(tempNode.data+",");
tempNode=tempNode.right;
}
}
return stringBuffer.toString();
}
@Override
public String postOrder() {
StringBuffer stringBuffer = new StringBuffer();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> curNode = root;
TreeNode<T> preNode = root;
while(curNode!=null||!stack.isEmpty()){
while(curNode!=null){
stack.push(curNode);
curNode=curNode.left;
}
if(!stack.isEmpty()){
TreeNode<T> tempNode = stack.peek().right;
if(tempNode==null||tempNode==preNode){
curNode=stack.pop();
stringBuffer.append(curNode.data+",");
preNode=curNode;
curNode=null;
}else{
curNode=tempNode;
}
}
}
return stringBuffer.toString();
}
@Override
public String levelOrder() {
StringBuffer stringBuffer = new StringBuffer();
Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
TreeNode<T> tempNode = root;
while(tempNode!=null){
stringBuffer.append(tempNode.data+",");
if(tempNode.left!=null)
queue.add(tempNode.left);
if(tempNode.right!=null)
queue.add(tempNode.right);
tempNode=queue.poll();
}
return stringBuffer.toString();
}
@Override
public void insert(T data) throws Exception {
if(data==null)
throw new Exception("data can't be null");
root=insert(root,data);
}
private TreeNode<T> insert(TreeNode<T> node,T data){
if(node==null){
node=new TreeNode<T>(data,null,null);
}else{
int compareResult=data.compareTo(node.data);
if(compareResult<0)
node.left=insert(node.left,data);
if(compareResult>0)
node.right=insert(node.right,data);
}
return node;
}
@Override
public T remove(T data) throws Exception {
if(data==null)
throw new Exception("data can't be null");
return remove(root,data).data;
}
private TreeNode<T> remove(TreeNode<T> node,T data) throws Exception{
if(node==null)
return null;
int compareResult=data.compareTo(node.data);
if(compareResult>0){
node.right=remove(node.right,data);
return node;
}
if(compareResult<0){
node.left=remove(node.left,data);
return node;
}
//如果要删除节点的左子树为空
if(node.left==null){
TreeNode<T> rightNode = node.right;
node.right=null;
return rightNode;
}
if(node.right==null){
TreeNode<T> leftNode = node.left;
node.left=null;
return leftNode;
}
//左右子树都不为空
TreeNode<T> successorNode = new TreeNode<T>(findMin(node.right).data,null,null);
successorNode.left=node.left;
successorNode.right=remove(node.right,data);
//将原节点set null
node.left=null;
node.right=null;
if(root.data==data)
root=successorNode;
return successorNode;
}
@Override
public T findMax() throws Exception {
if(root==null)
throw new Exception("data can't be null");
return findMax(root).data;
}
private TreeNode<T> findMax(TreeNode<T> node){
TreeNode<T> tempNode = node;
while(tempNode.right!=null){
tempNode=tempNode.right;
}
return tempNode;
}
@Override
public T findMin() throws Exception {
if(root==null)
throw new Exception("data can't be null");
return findMin(root).data;
}
private TreeNode<T> findMin(TreeNode<T> node) throws Exception{
TreeNode<T> tempNode = node;
while(tempNode.left!=null)
tempNode=tempNode.left;
return tempNode;
}
@Override
public boolean contain(T data) throws Exception {
if(data==null)
throw new Exception("data can't be null");
return contain(root,data);
}
private boolean contain(TreeNode<T> node,T data){
if(node==null)
return false;
int compareResult=data.compareTo(node.data);
if(compareResult>0)
return contain(node.right,data);
if(compareResult<0)
return contain(node.left,data);
return true;
}
}
二叉查找树会引发的问题,如果当前数据几乎是一个顺序或者逆序的前提下,二叉查找树就把一个偏向一边甚至退化为链表.这样就完全丧失了它存在的意义.
AVL树
AVL树是理想的平衡二叉树,它保证左子节点和右子节点的深度最多相差1,但每次插入和删除二叉树整体都会进行旋转.但它整体的查询的效率维持在了O(logN)
B树
B树这种数据结构的特点就是深度低,这样做的目的是减少访问外存的次数.
B树的节点设计为一个【k,v】对，这样就可以根据k的规则就寻找想找的value值.
特点：
- 一颗m阶的b-tree最多有m个孩子
- 除了根节点和叶子节点外,每个节点至少有Ceil(m/2)个孩子
-所有叶子节点都在同一层.
-关键字的个数n满足：ceil(m/2)-1<=n<=m-1 - ki(i=1,…n)为关键字，且关键字升序排序。
- Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)
B+树
B+树存在的目的是为了降低b树的深度.特点如下：
- 非叶子节点只存储键值信息。
- 所有叶子节点之间都有一个链指针。
- 数据记录都存放在叶子节点中。
