BST原理剖析及Java实现

淡淡的烟草味﹌ 2021-11-11 06:08 224阅读 0赞

### BST原理剖析及Java实现 ###

*  BST概念
 *  BST 实现原理
 *   *  BST 查找原理
     *  BST 插入原理
     *  BST 删除原理
 *  Java实现二叉查找树
 *   *  BST类
     *  测试
 *  BST 存在的问题

# BST概念 #

二叉查找树(Binary Search Tree，简称BST)是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。  
在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。

# BST 实现原理 #

## BST 查找原理 ##

当BST查找的时候，先与当前节点进行比较：

*  如果相等的话就返回当前节点；
 *  如果少于当前节点则继续查找当前节点的左节点；
 *  如果大于当前节点则继续查找当前节点的右节点。  
    直到当前节点指针为空或者查找到对应的节点，程序查找结束。

## BST 插入原理 ##

插入操作先通过循环查找到待插入的节点的父节点，和查找父节点的逻辑一样，都是比大小，小的往左，  
大的往右。找到父节点后，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上。

## BST 删除原理 ##

删除操作的步骤如下：

*  查找到要删除的节点。
 *  如果待删除的节点是叶子节点，则直接删除。
 *  如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。

# Java实现二叉查找树 #

## BST类 ##

/** * 二叉排序树 * @author JustinNeil * */
    public class BST<T extends Comparable<T>>{ 
    	//根节点
    	private Node<T> root = new Node<T>();
    	
    	/** * 节点类 * @author JustinNeil */
    	class Node<T extends Comparable<T>>{ 
    		
    		/** * 存储的对象 */
    		private T key;
    		
    		/** * 左孩子 */
    		private Node<T> leftChild;
    		
    		/** * 右孩子 */
    		private Node<T> rightChild;
    		
    		/** * 中序遍历 */
    		@Override
    		public String toString() { 
    			StringBuilder sb = new StringBuilder();
    			/** * 当前节点为空，不打印 */
    			if(this.key == null) { 
    				sb.append("");
    			}else { 
    				/** * 左子树不为空，中序遍历左子树 */
    				if(leftChild != null) { 
    					sb.append(leftChild.toString());
    				}
    				/** * 打印当前节点 */
    				sb.append(key.toString());
    				/** * 右子树不为空，中序遍历右子树 */
    				if(rightChild != null) { 
    					sb.append(rightChild.toString());
    				}
    			}
    			return sb.toString();
    		}
    		
    		/** * 添加元素 * @param t */
    		public void add(T t) { 
    			/** * 当前节点为空，设当前节点的值为添加的元素 */
    			if(this.key == null){ 
    				this.key = t;
    			/** * 小于当前节点，添加到左子树中 */
    			}else if(key.compareTo(t)>0){ 
    				if(leftChild == null) { 
    					leftChild = new Node<T>();
    				}
    				leftChild.add(t);
    			/** * 大于当前节点，添加到右子树中 */
    			}else if(key.compareTo(t)<0){ 
    				if(rightChild == null) { 
    					rightChild = new Node<T>();
    				}
    				rightChild.add(t);
    			}
    		}
    		
    		/** * 删除节点 * @param t */
    		public void delete(T t) { 
    			
    			if(key == t) { 
    				/** * 左右子树均为空，直接删除 */
    				if(rightChild == null && leftChild == null) { 
    					key = null;
    				/** * 右子树为空，将当前节点的左子树作为当前节点 */
    				}else if(rightChild == null){ 
    					T temp = this.leftChild.key;
    					this.rightChild = leftChild.rightChild;
    					this.leftChild = leftChild.leftChild;
    					this.key = temp;
    				/** * 左子树为空，将当前节点的右子树作为当前节点 */
    				}else if(leftChild == null){ 
    					T temp = this.rightChild.key;
    					this.leftChild = rightChild.leftChild;
    					this.rightChild = rightChild.rightChild;
    					this.key = temp;
    				/** * 左右子树都不为空，将当前节点的左子树作为当前节点右子树中最左子树的左子树，然后 * 将右子树作为当前节点 */
    				}else { 
    					Node node = rightChild;
    					while(node.leftChild != null) { 
    						node = node.leftChild;
    					}
    					node.leftChild = leftChild;
    					T temp = this.rightChild.key;
    					this.leftChild = rightChild.leftChild;
    					this.rightChild = rightChild.rightChild;
    					this.key = temp;
    				}
    			}else if(key.compareTo(t)>0){ 
    				leftChild.delete(t);
    			}else if(key.compareTo(t)<0) { 
    				rightChild.delete(t);
    			}
    		}
    	}
    	
    	@Override
    	public String toString() { 
    		return root.toString();
    	}
    	
    	public void add(T t) { 
    		root.add(t);
    	}
    	
    	public void delete(T t) { 
    		root.delete(t);
    	}
    }

## 测试 ##

public class BSTTest { 
    	public static void main(String[] args) { 
    		BST<Integer> BSTree = new BST<Integer>();
    		BSTree.add(8);
    		System.out.println(BSTree);
    		BSTree.add(4);
    		System.out.println(BSTree);
    		BSTree.add(1);
    		System.out.println(BSTree);
    		BSTree.add(2);
    		System.out.println(BSTree);
    		BSTree.add(9);
    		System.out.println(BSTree);
    		BSTree.add(5);
    		System.out.println(BSTree);
    		BSTree.add(7);
    		System.out.println(BSTree);
    		BSTree.add(3);
    		System.out.println(BSTree);
    		BSTree.delete(8);
    		System.out.println(BSTree);
    		BSTree.delete(9);
    		System.out.println(BSTree);
    		BSTree.delete(7);
    		System.out.println(BSTree);
    		
    	}
    }

# BST 存在的问题 #

BST存在的主要问题：  
数在插入的时候会导致树倾斜，  
不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。  
理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。