一、概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
搜索效率高，一次能砍掉一半，最好的情况：O(logN)，最坏的情况：O(N)
二、搜索
图解
代码实现
public class BinarySearchTree {static class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val = val;}}public TreeNode root = null;public TreeNode search(int key){TreeNode cur = root;while(cur!=null){if(cur.val<key){cur = cur.right;}else if(cur.val>key){cur = cur.left;}else{return cur;}}return null;}}
三、插入 （只能插入叶子节点）
图解：
代码实现：
public class BinarySearchTree {static class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val = val;}}public TreeNode root = null;//只能插入叶子节点public void insert(int key){TreeNode node = new TreeNode(key);if(root==null){root = node;return;}TreeNode cur = root;TreeNode parent = null;while(cur!=null){if(cur.val>key){parent = cur;cur = parent.left;}else if(cur.val<key){parent = cur;cur = parent.right;}else{return;//相同值不能插入}}if(parent.val>key){parent.left = node;}else{parent.right = node;}}}四、删除
分三种情况
代码实现：
public void remove(int key){TreeNode parent = null;TreeNode cur = root;while(cur!=null){if(cur.val<key){parent = cur;cur = cur.right;}else if(cur.val>key){parent = cur;cur = cur.left;}else{//找到要删除的节点removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent,TreeNode cur){//三种情况//左树空if(cur.left==null){if(cur == root){cur = cur.right;}else if(cur == parent.left){parent.left = cur.right;}else{parent.right = cur.right;}}else if(cur.right == null){//右树空if(cur==root){cur = cur.left;}else if(cur == parent.left){parent.left = cur.left;}else{parent.right = cur.left;}}else{//都不为空TreeNode target = cur.right;//找右树TreeNode targetP = cur;while(target.left!=null){targetP = target;target = targetP.left;}cur.val = target.val;if(target==targetP.left){targetP.left = target.right;}else{targetP.right = target.right;}}}五、性能分析
搜索的最优情况下是完全二叉树，时间复杂度O(logN)
最差情况下，二叉搜索树退化为单支树，时间复杂度O(N)
如果退化成单支树，二叉搜索树的性能就失去了。因此就需要解决高度平衡问题，就出现了AVL树。
