一、什么是动态表查找？
动态查找表指在查找过程同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
动态查找表的表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
动态查找表也即树表的查找，动态查找表的方法是一种以树的形式来组织查找，以实现动态高效效率的查找。
动态查找表的方法有：
二叉排序树
平衡二叉树
B树
B+树
二、动态查找表的特点
表结构本身是在查找过程中动态生成的，即对于给定值key，
若表中存在关键字值等于key的记录，则查找成功返回；
否则插入关键字值等于key的记录。
三、二叉排序树
1）概述
二分查找具有最高的查找效率，但是由于二分查找要求表中记录按关键字有序，且不能用链表做存储结构，因此，当表的插入、删除操作非常频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。
二叉排序树不仅具有二分查找的效率，同时又便于在查找表中进行记录的增加和删除操作。
2）定义
二叉排序树（Binary Sort Tree ）或者是一棵空树，或者是一颗具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于根结点的值
若右子树不空，则右子树上所有结点的值均大于根结点的值
它的左右子树也都是二叉排序树
相关类：
二叉树结点：
public class BiTreeNode { public Object data;// 结点的数据元素 public BiTreeNode lchild, rchild; // 左右孩子 }
二叉排序树的类结构：
public class BSTree { //二叉排序树类 public BiTreeNode root; //根结点 public void inOrderTraverse(BiTreeNode p) { //中根次序遍历以p结点为根的二叉树 if (p != null) { inOrderTraverse(p.lchild); // 结点的数据元素存放的是RecordNode System.out.print(((RecordNode) p.data).toString() + ""); inOrderTraverse(p.rchild); } } }
3）插入：分析
假设待插入结点的关键字值为key，为了将其插入到表中
先要将它放入二叉排序树中进行查找，
若查找成功，则按二叉排序树定义，待插入结点已存在，不用插入
否则，将新结点插入到表中。因此，新插入的结点一定是作为叶子结点添加到表中去的。
构建一棵二叉排序树是从一棵空树开始逐个插入结点的过程。假设关键字序列为{49, 25, 55, 10, 51, 65}，则构造一棵二叉排序树的过程如下：
4）插入：算法
代码
//在二叉排序树中插入关键字为Key,数据项为theElement的结点,若插入成功返回true,否则返回false public boolean insertBST(Comparable key, Object theElement) { if (key == null || !(key instanceof Comparable)) {//不能插入空对象或不可比较大小的对象 return false; } if (root == null) { root = new BiTreeNode(new RecordNode(key, theElement)); //建立根结点 return true; } return insertBST(root, key, theElement); } //将关键字为key,数据项为theElement的结点插入到以p为根的二叉排序树中的递归算法 private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) { if (key.compareTo(((RecordNode) p.data).key) == 0) { return false; //不插入关键字重复的结点 } if (key.compareTo(((RecordNode) p.data).key) < 0) { if (p.lchild == null) { //若p的左子树为空 p.lchild=new BiTreeNode(new RecordNode(key, theElement)); //建立叶子结点作为p的左孩子 return true; } else { //若p的左子树非空 return insertBST(p.lchild, key, theElement); //插入到p的左子树中 } } else if (p.rchild == null) { //若p的右子树为空 p.rchild=new BiTreeNode(new RecordNode(key, theElement)); //建立叶子结点作为p的右孩子 return true; } else { //若p的右子树非空 return insertBST(p.rchild, key, theElement); //插入到p的右子树中 } }
- 测试
import book.ch07.RecordNode; public class TestBSTree1_insertBST { public static void main(String[] args) { int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68}; BSTree bsTree = new BSTree(); for (int i = 0; i < k.length; i++) { if (bsTree.insertBST(k[i], null)) { //若插入对象成功 System.out.print("[" + k[i] + "]"); } } System.out.println("\n中序遍历二叉排序树： "); bsTree.inOrderTraverse(bsTree.root); System.out.println(); } }
5）查找：分析
若将查找表组织为一棵二叉排序树，则根据二叉排序树的特点，查找过程的主要步骤：
若查找树为空，则查询失败
若查找树非空，则：
1. 若给定值k等于根结点的关键字值，则查找成功，结束查找过程，否则转2
2. 若给定值k小于根结点的关键字值，则继续在根结点的左子树上进行，否则转3
3. 若给定值k大于根结点的关键字值，则继续在根结点的右子树上进行。
6）查找：算法
代码
//查找关键字值为key的结点,若查找成功返回结点值，否则返回null public Object searchBST(Comparable key) { if (key == null || !(key instanceof Comparable)) { return null; } return searchBST(root, key); } //二叉排序树查找的递归算法 //在二叉排序树中查找关键字为key的结点。若查找成功则返回结点值，否则返回null private Object searchBST(BiTreeNode p, Comparable key) { if (p != null) { if (key.compareTo(((RecordNode) p.data).key) == 0) //查找成功 { return p.data; } // System.out.print(((RecordNode) p.data).key + "? "); if (key.compareTo(((RecordNode) p.data).key) < 0) { return searchBST(p.lchild, key); //在左子树中查找 } else { return searchBST(p.rchild, key); //在右子树中查找 } } return null; }
测试
import book.ch07.RecordNode; /** * @author 桐叔 * @email liangtong@itcast.cn */ public class TestBSTree2_searchBST { public static void main(String[] args) { int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68}; BSTree bsTree = new BSTree(); for (int i = 0; i < k.length; i++) { if (bsTree.insertBST(k[i], null)) { //若插入对象成功 System.out.print("[" + k[i] + "]"); } } System.out.println("\n中序遍历二叉排序树： "); bsTree.inOrderTraverse(bsTree.root); System.out.println(); //查找关键字 RecordNode recordNode1 = (RecordNode) bsTree.searchBST(35); System.out.println(recordNode1); RecordNode recordNode2 = (RecordNode) bsTree.searchBST(36); System.out.println(recordNode2); } } //中序遍历二叉排序树： //[5,null][8,null][10,null][12,null][15,null][35,null][49,null][65,null][68,null][88,null] //[35,null] //null
7）删除：分析
从二叉排序树中删除一个结点，要保证删除后仍然是一棵二叉排序树。根据二叉排序树的结构特征，删除操作可以分4种情况
情况1：若待删除的结点是叶子结点，则直接删除该结点即可。若该结点同时也是根节点，则删除后二叉排序树将变为空树。
情况2：若待删除的结点只有左子树，而无右子树。根据二叉排序树的特点，—《可以直接将其左子树的根结点代替被删除结点的位置—》，即若被删除的结点为其双亲结点的左孩子，则将被删除结点的唯一左孩子收为其双亲结点的左孩子；否则收为其双亲节点的右孩子。
情况3：待删除的结点只有右子树，而无左子树。—《可以直接将其右子树的根结点替代被删除结点的位置—》，即若被删除的结点为其双亲结点的左孩子，则将被删除结点的唯一右孩子收为其双亲结点的左孩子；否则收为其双亲结点的右孩子。
情况4：待删除结点既有左子树又有右子树。根据二叉排序树的特点，可以用被删除结点在中序遍历序列下的前驱结点（或其中序遍历序列下的后继结点）代替被删除结点，同时删除其中序遍历序列下的前驱结点（或其中序遍历序列下的后继结点）。而被删除结点在中序遍历下的前驱无右子树，被删除结点在中序遍历下的后继无左子树，因而问题转换为第2种情况或第3种情况。
方式1：前驱结点：左子树的最右的结点
方式2：后继结点：右子树的最左的结点
8）删除：算法
代码
//二叉排序树中删除结点算法。若删除成功返回删除结点值，否则返回null public Object removeBST(Comparable key) { if (root == null || key == null || !(key instanceof Comparable)) { return null; } //在以root为根的二叉排序树中删除关键字为elemKey的结点 return removeBST(root, key, null); } //在以p为根的二叉排序树中删除关键字为elemKey的结点。parent是p的父结点，递归算法 private Object removeBST(BiTreeNode p, Comparable elemKey, BiTreeNode parent) { if (p != null) { if (elemKey.compareTo(((RecordNode) p.data).key) < 0) { //在左子树中删除 return removeBST(p.lchild, elemKey, p); //在左子树中递归搜索 } else if (elemKey.compareTo(((RecordNode) p.data).key) > 0) { //在右子树中删除 return removeBST(p.rchild, elemKey, p); //在右子树中递归搜索 } else if (p.lchild != null && p.rchild != null) { //相等且该结点有左右子树 BiTreeNode innext = p.rchild; //寻找p在中根次序下的后继结点innext while (innext.lchild != null) { //即寻找右子树中的最左孩子 innext = innext.lchild; } p.data=innext.data; //以后继结点值替换p return removeBST(p.rchild, ((RecordNode) p.data).key, p); //递归删除结点p } else {//p是1度和叶子结点 if (parent == null) { //删除根结点，即p==root if (p.lchild != null) { root = p.lchild; } else { root = p.rchild; } return p.data; //返回删除结点p值 } if (p == parent.lchild) { //p是parent的左孩子 if (p.lchild != null) { parent.lchild=p.lchild; //以p的左子树填补 } else { parent.lchild=p.rchild; } } else if (p.lchild != null) { //p是parent的右孩子且p的左子树非空 parent.rchild=p.lchild; } else { parent.rchild=p.rchild; } return p.data; } } return null; }
测试
import book.ch07.RecordNode; /** * @author 桐叔 * @email liangtong@itcast.cn */ public class TestBSTree3_removeBST { public static void main(String[] args) { int[] k = {49, 12, 65, 8, 35, 88, 5, 10, 15,68}; BSTree bsTree = new BSTree(); for (int i = 0; i < k.length; i++) { if (bsTree.insertBST(k[i], null)) { //若插入对象成功 System.out.print("[" + k[i] + "]"); } } System.out.println("\n中序遍历二叉排序树： "); bsTree.inOrderTraverse(bsTree.root); System.out.println(); RecordNode recordNode = (RecordNode)bsTree.removeBST(12); System.out.println(recordNode); bsTree.inOrderTraverse(bsTree.root); } }
9）练习
50、40、60、35、25、45、70、80
要求1：绘制二叉排序树（绘图）
要求2：查询25，书写查询路径
要求3：重新开始，删除结点40后，二叉排序树（绘图）
要求4：重新开始，删除结点35后，二叉排序树（绘图）
要求5：重新开始，删除结点60后，二叉排序树（绘图）
要求2：查询25，书写查询路径：
50 --> 40 --> 35 --> 25
