公众号merlinsea
- 二叉排序树介绍
- 二叉排序树是一棵二叉树或者空树
- 若它的左子树不空，则左子树的所有节点的关键字均小于根节点
- 若它的右子树不空，则右子树的所有节点的关键字均大于根节点
- 二叉排序树的插入操作
- 插入操作是指向一个二叉排序树中插入一个元素，如果这个元素已经存在，则插入失败；如果不存在则插入成功。
- 插入操作结束后仍旧需要保证这个二叉排序树的左小右大的特点。
- 比如向上面这个二叉排序树中插入元素6，这个元素6最后会插入在节点5的右孩子处。
- 插入操作——代码实现
/ 返回true代表插入成功，返回false代表插入失败 public boolean insert(BTNode p){ if(p==null){ return false; } if(root==null){ root = p; }else{ //工作节点 BTNode work = root; while(work!=null){ if(work.val < p.val){ //p应该插入在work的右边 if(work.right!=null){ work = work.right; }else{ //完成了插入; work.right = p; break; } }else if(work.val > p.val){ //p应该插入在work的左边 if(work.left != null){ work = work.left; }else{ //完成插入插入操作 work.left = p; break; } }else{ //我们找到了一个一抹一样的节点,更新info信息，返回fasle work.info = p.info; return false; } } } return true; }
- 二叉排序树的查询操作
- 查询操作就是从树的根节点出发，查找知道关键值的元素，如果可以找到则返回这个元素，如果不可以找到则返回空。
- 查询操作的代码实现
public BTNode find(int val){ BTNode p = root; while(p!=null){ if(p.val == val){ break; }else if(p.val < val){ //说明目标节点在p的右边 p = p.right; }else{ //说明目标节点在p的左边 p = p.left; } } return p; }
- 二叉排序树的删除操作
- 删除操作是指需要在一棵二叉排序树中删除指定关键字的节点，同样的删除以后需要保证二叉排序树的左小右大的特征。
- 二叉排序树删除的三种情况
- 删除的是叶子节点，即待删除元素左右子树都为空的情况，直接删除即可。
- 删除的是单分支的节点，即待删除元素左子树为空右子树不为空 或者 右子树为空左子树不为空，只需要讲其孩子节点来替代这个待删除的节点即可。
- 删除的是双分支节点，即待删除的元素左右子树都不空的情况，可以将其左子树中的最大值来替换当前节点，同时删除左子树中的最大值，或者可以将其右子树中的最小值来替换当前节点，同时删除右子树中的最小值。
- 删除节点的时候，我们需要找到待删除目标节点的父节点，比如下图中我们需要删除节点4，我们需要找到4的父节点5，让5的左指针指向2。
- 删除操作代码实现
public boolean delete(int val){ //1、先找到待删除元素的父节点 BTNode target = findDel(val); if(target==null){ // 说明查找失败 return false; } //2、删除元素 ---> 根节点 / 非根节点 //左子树的最大值来填充 if(val == root.val){ //说明删除的是根节点 if(root.left == null && root.right ==null){ root = null; }else if(root.left == null){ root = root.right; }else if(root.right == null){ root = root.left; }else{ //寻找左子树最大值 BTNode p = root.left; while(p.right != null){ p = p.right; } delete(p.val); root.val = p.val; root.info = p.info; } }else{ //说明删除的不是根节点,则target是待删除元素的父亲节点 if(target.left!=null && target.left.val == val){ //说明需要删除的是target的左节点 BTNode del = target.left; if(del.left == null && del.right == null){ target.left = null; }else if(del.left == null){ target.left = del.right; }else if(del.right == null){ target.left = del.left; }else{ //说明待删除元素有左右孩子节点 BTNode p = del.left; while(p.right!=null){ p = p.right; } delete(p.val); del.val = p.val; del.info = p.info; } }else{ //说明待删除的是target的右孩子 BTNode del = target.right; if(del.left == null && del.right == null){ target.right = null; }else if(del.left == null){ target.right = del.right; }else if(del.right == null){ target.right = del.left; }else{ //说明待删除元素有左右孩子节点 BTNode p = del.left; while(p.right!=null){ p = p.right; } delete(p.val); del.val = p.val; del.info = p.info; } } } return true; } //找的是val的父节点 public BTNode findDel(int val){ if(root==null){ return null; } if(val == root.val){ return root; } BTNode p = root; while(p!=null){ if(val < p.val){ if(p.left != null && p.left.val == val){ return p; }else if(p.left == null){ return null; }else{ //存在但不相等 p = p.left; } }else{ if(p.right !=null && p.right.val == val){ return p; }else if(p.right == null){ return null; }else{ p = p.right; } } } return null; }
- 二叉排序树的不足
- 假设我们需要建立一棵二叉排序树，但我们依次插入的元素是[1，2，3，4，5，6，7，8，9），那么我们实际插入的树其实以一颗只有右子树，没有左子树的树。那么其查找效率会退化为一个单链表。
