二叉搜索树

操作-查找

操作-插入

操作-删除

性能分析

二叉搜索树

二叉搜索树又称二叉排序树,它要么是一棵空树,要么是具有以下性质的二叉树:

若它的左子树不为空,则左子树上所有结点的值都小于根节点的值
若它的右子树不为空,则右子树上所有结点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

如图就是一棵二叉搜索树.

下面,我们来实现几个二叉搜索树的操作.

操作-查找

查找val是否在当前搜索树当中,根据二叉搜索树的特点,如果根节点的val == 查找val,则直接返回根节点;如果根节点的val > 查找val,就去根节点的左子树里去找;如果根节点的val < 查找的val,就去根节点的右子树里去找,以此类推,没找到就返回null.

 public TreeNode search(int val){TreeNode cur = root;while (cur != null){if (cur.val < val){cur = cur.right;}else if (cur.val > val){cur = cur.left;}else {return cur;}}return null;}

操作-插入

public boolean insert(int key){//根节点为空,就直接插入到根节点的位置if (root == null){root = new TreeNode(key);return true;}//parent用来记录cur的prevTreeNode parent = null;TreeNode cur = root;//cur==null就说明要进行插入了while(cur != null){//当前节点的值大于key,就往当前节点的左子树走if (cur.val > key){parent = cur;cur = cur.left;}else if (cur.val < key){parent = cur;cur = cur.right;}else {//插入相同的元素直接返回falsereturn false;}}//代码走到这里cur==null//此时比较key和parent的val大小来判断//往左子树插入还是右子树插入TreeNode node = new TreeNode(key);if (parent.val > key){parent.left = node;}else {parent.right = node;}return true;}

操作-删除

删除的逻辑比较复杂,分为多种情况.

设待删除的节点为cur,待删除的双亲结点为parent.

1.cur.left == null

cur是root,则root = cur.right
cur不是root,cur是parent的left.则parent.left=cur.right
cur不是root,cur是parent.right,则parent.right=cur.right

2.cur.right == null

cur是root,则root = cur.left
cur不是root,cur是parent的right,则parent.right=cur.left
cur不是root,cur是parent的left,则parent.left = cur.left

3.cur.left!=null && cur.right!=null

此种情况,要使用替罪羊法进行删除.即在它的右子树中找到最左边的结点(cur右边最小的结点)或者是在它的左子树中找到最右边的结点(cur左边最大的结点),用找到的值来填补到待删除结点中,此时问题就转换为删除替罪结点了.

比如要删除12.我们要找到9或者是13来代替12,然后在将9或者13删除掉.

因为9或者13的特殊性,9没有右子树,13没有左子树,所有9或者13的删除就可以使用前两种情况.

public void remove(int key){TreeNode parent = null;TreeNode cur = root;while(cur != null){if (cur.val == key){removeNode(parent,cur);return;}else if (cur.val < key){parent = cur;cur = cur.right;}else {parent = cur;cur = cur.left;}}}private void removeNode(TreeNode parent,TreeNode cur){if (cur.left == null){if (cur == root){root = cur.right;}else if (cur == parent.left){parent.left = cur.right;}else {parent.right = cur.right;}}else if (cur.right == null){if(cur == root) {root = cur.left;} else if (cur == parent.left) {parent.left = cur.left;}else {parent.right = cur.left;}}else {TreeNode target = cur.right;TreeNode targetParent = cur;while (target.left != null){targetParent = target;target = target.left;}cur.val = target.val;if (targetParent.left == target){targetParent.left = target.right;}else {//待删除节点的右边可能没有左子树//此时cur.right就是替罪羊targetParent.right = target.right;}}}