数据结构12—

数据结构12——查找

查找主要分类：

如上图所示：查找可分为动态查找和静态查找。

静态查找：只是在数据集合中查找是否含有某个元素。

动态查找：查找过程中包括数据的插入和删除中产生的数据。

1：静态查找

1.1：无序查找：相对容易，只提供无序查找的代码

1 public static int seqSearch(int[] a,int ele){
2         for (int i = 0; i < a.length; i++) {
3             if (ele==a[i]) 
4                 return i;
5         }
6          return -1;
7     }

1.2：有序查找

有序查找又可以分为顺序查找和二分查找。

1.2.1：顺序查找

1 public static int orderSearch(int[] a ,int ele){
2         int i;
3         for (i = 0; a[i]<ele && i < a.length-1; i++) ;
4         if (ele==a[i]) {
5             return i;
6         }
7         else return -1;
8     }

1.2.3:二分查找

public static int binarySearch(int[] a, int ele){
        int n=a.length;
        int low=0 , hight=n-1, mid;
        while(low<=hight){
            mid=(low+hight)/2;
            if (a[mid]<ele) 
                low=mid+1;
            else if (a[mid]>ele) 
                hight=mid-1;
            else return mid;
        }
        return -1;
    }

时间复杂度分析：对于二分法查找，因为都是对半分开，所以对于数据长度为n的集合，查找的平均时间复杂度为 Log₂n

2：动态查找

对于动态查找，在查找的过程中涉及到了数据的插入和删除，数据集合的长度都是动态变化的。

动态查找的结构主要分为：二叉树结构（二叉排序树），树结构（B_树）。

2.1：二叉排序树

二叉排序树的主要特征为：

(1)：若左子树不为空，则左子树上所有的结点的数据元素值都小于根结点的数据元素值。

(2)：若右子树不为空，则右子树上所有的结点的数据元素值都小于根结点的数据元素值。

(3)：同时左右子树也为二叉排序树。

二叉排序树的结点类：

二叉排序树的结点类必须包括两个方面：数据，结点。同时结点又分为左孩子结点，右孩子结点，父亲结点。

 1 package com.hone.search;
 2 /*
 3  * 定义一个二叉排序树结点类
 4  * 包含四个元素：左孩子结点，右孩子结点，数据，父母结点
 5  */
 6 public class BinarySortTreeNode {
 7     private BinarySortTreeNode leftChild;
 8     private BinarySortTreeNode rightChild;
 9     private BinarySortTreeNode parent;
10     private int data;
11     
12     //没有孩子结点
13     public BinarySortTreeNode(){
14         leftChild=null;
15         rightChild=null;
16     }
17     
18     //没有孩子结点，只有自身元素的初始化方法
19     public BinarySortTreeNode(int item){
20         data=item;
21         leftChild=null;
22         rightChild=null;
23     }
24     
25     public BinarySortTreeNode(int item, BinarySortTreeNode left,BinarySortTreeNode right){
26         leftChild=left;
27         rightChild=right;
28         data=item;
29     }
30 
31     //封装四个元素
32     public BinarySortTreeNode getLeftChild() {
33         return leftChild;
34     }
35 
36     public BinarySortTreeNode getRightChild() {
37         return rightChild;
38     }
39 
40     public BinarySortTreeNode getParent() {
41         return parent;
42     }
43 
44     public int getData() {
45         return data;
46     }
47 
48     public void setLeftChild(BinarySortTreeNode leftChild) {
49         this.leftChild = leftChild;
50     }
51 
52     public void setRightChild(BinarySortTreeNode rightChild) {
53         this.rightChild = rightChild;
54     }
55 
56     public void setParent(BinarySortTreeNode parent) {
57         this.parent = parent;
58     }
59 
60     public void setData(int data) {
61         this.data = data;
62     }
63     
64     //获得左子树
65     public BinarySortTreeNode getLeft(){
66         return leftChild;
67     }
68     
69     //获得右子树
70     public BinarySortTreeNode getRight(){
71         return rightChild;
72     }
73 
74 }

二叉排序树的类：

二叉排序树的类中的方法主要包括查找，删除，插入

二叉树遍历查找过程：

 1 //查找某一个元素的位置
 2     public BinarySortTreeNode find(int item){
 3         if (root != null) {
 4             BinarySortTreeNode temp=root;
 5             while(temp != null){
 6                 if (temp.getData() == item) {
 7                     return temp;
 8                 }
 9                 //如果item>temp.getData()  则数一定在右边，整个过程类似于二分查找
10                 if (temp.getData()<item) 
11                     temp.getRight();
12                 else 
13                     temp.getLeft();
14             }
15         }
16         return null;
17     }

二叉排序树的插入过程：

这里面的插入操作同时也包括查找过程，首先查找需要插入的数据是否在二叉树中存在，如果存在则结束，如果不存在，则根据需要插入结点的数值，把储存该数据元素的结点，插入到二叉排序树查找失败的左孩子或者右孩子结点。

插入代码

 1 //插入一个元素,传入两个参数，一个为当前结点，一个为数据元素
 2     public void insert(BinarySortTreeNode ptr, int item){
 3         if (item < ptr.getData()) {　　　　　　　　　　　　//插入左子树中
 4             if (ptr.getLeft()==null) {
 5                 BinarySortTreeNode temp=new BinarySortTreeNode(item);
 6                 temp.setParent(ptr);
 7                 ptr.setLeftChild(temp);
 8             }
 9             else
10                 insert(ptr.getLeft(), item);
11         }
12         if (item > ptr.getData()) {　　　　　　　　　　　　//插入右子树中
13             if (ptr.getRight()==null) {
14                 BinarySortTreeNode temp=new BinarySortTreeNode(item);
15                 temp.setParent(ptr);
16                 ptr.setRightChild(temp);
17             }
18             else
19                 insert(ptr.getRight(), item);
20         }
21     }

二叉树的删除算法：

首先需要查找数据元素是否存在于二叉排序树中，如果不存在，则直接结束，如果存在又分为四种情况

（1）：待删除结点无孩子结点，这种情况只需要直接删除该节点即可

（2）：待删除结点只有左孩子结点，删除该结点，并且使该结点的父亲结点指向被删除结点的左孩子结点（但是在写代码过程中，被删除结点的左孩子结点是放在被删除结点　　的左孩子位还是右孩子位？）

（3）：待删除结点只有右孩子结点，删除该结点，并且使该结点的父亲结点指向被删除结点的

（4）：待删除结点有左右孩子结点，第一步：寻找要删除结点右子树的最小结点，

　　　　　　　　　　　　　　　　第二步：将右子树中最小结点拷贝到要删除结点上面

　　　　　　　　　　　　　　　　第三步：最后删除右子树的最左结点

 1 //删除某一个元素
 2     public void delete(BinarySortTreeNode ptr, int item){
 3         if (ptr != null) {
 4             if (item<ptr.getData()) 
 5                 delete(ptr.getLeft(), item);        //在左子树遍历
 6             else if (item > ptr.getData()) 
 7                 delete(ptr.getRight(), item);        //在右子树 遍历
 8             /*
 9              * 当左右子树都存在时,首先查找数据元素值大于要删除结点元素的关键字的最小值，也就是寻找
10              * 要删除结点右子树的最左结点，然后将其拷贝到要删除的结点
11              * 最后删除右子树的最左结点
12              */
13             
14             else if (ptr.getLeft() != null&& ptr.getRight()!=null) {
15                 BinarySortTreeNode min;
16                 min=ptr.getRight();
17                 while(min.getLeft()!=null){
18                     min=min.getLeft();
19                 }
20                 ptr.setData(min.getData());             //将最小数值赋值给ptr元素
21                 //在ptr结点的右子树中递归删除min结点
22                 delete(ptr.getRight(), min.getData());         
23                 
24             }
25             
26             /*
27              * 当待删除结点只有右孩子时,画图理解
28              * 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
29              */
30             
31             else if (ptr.getLeft()==null&&ptr.getRight()!=null) {
32                 ptr.getParent().setRightChild(ptr.getRight());
33                 ptr.getRight().setParent(ptr.getParent());
34                 
35             }
36             /*
37              * 当待删除结点只有左孩子结点时，
38              */
39             else if (ptr.getLeft()!=null&&ptr.getRight()==null) {
40                 ptr.getParent().setLeftChild(ptr.getLeft());
41                 ptr.getLeft().setParent(ptr.getParent());
42             }
43             /*
44              * 当待删除结点为叶子节点时
45              */
46             else {
47                 BinarySortTreeNode parent=ptr.getParent();
48                 if (parent.getLeft()==ptr) {
49                     parent.setLeftChild(null);
50                 }
51                 else{
52                     parent.setRightChild(null);
53                 }
54             }
55         }
56         
57     }

完整代码：

  1 package com.hone.search;
  2 
  3 /*
  4  * 二叉排序树的主要方法包括查找，删除，插入
  5  */
  6 public class BinarySortTree {
  7     public BinarySortTreeNode root;                //获得根节点
  8     
  9     //中序遍历
 10     private void inOrder(BinarySortTreeNode t,Visit vs){
 11         if (t!=null) {
 12             inOrder(t.getLeftChild(), vs);
 13             vs.print(new Integer(t.getData()));
 14             inOrder(t.getRightChild(), vs);
 15         }
 16     }
 17     
 18     //前序遍历
 19     private void preOrder(BinarySortTreeNode t,Visit vs){
 20         if (t!=null) {
 21             vs.print(new Integer(t.getData()));
 22             preOrder(t.getLeftChild(), vs);
 23             preOrder(t.getRightChild(), vs);
 24         }
 25     }
 26     
 27     //构造函数，初始化根节点
 28     public BinarySortTree (){
 29         root=null;
 30     }
 31     
 32 
 33     public BinarySortTreeNode getRoot() {
 34         return root;
 35     }
 36 
 37     public void setRoot(BinarySortTreeNode root) {
 38         this.root = root;
 39     }
 40     
 41     //统一遍历的接口
 42     public void preOrder(Visit vs){
 43         preOrder(root, vs);
 44     }
 45     public void inOder(Visit vs){
 46         inOrder(root, vs);
 47     }
 48     
 49     //取左孩子(左孩子可以是一个集合)
 50     public BinarySortTreeNode getLeft(BinarySortTreeNode current){
 51         return current != null ? current.getLeft():null; 
 52     }
 53     
 54     //取右孩子
 55     public BinarySortTreeNode getRight(BinarySortTreeNode current){
 56         return current != null ? current.getRight():null; 
 57     }
 58     
 59     //查找某一个元素的位置
 60     public BinarySortTreeNode find(int item){
 61         if (root != null) {
 62             BinarySortTreeNode temp=root;
 63             while(temp != null){
 64                 if (temp.getData() == item) {
 65                     return temp;
 66                 }
 67                 //如果item>temp.getData()  则数一定在右边
 68                 if (temp.getData()<item) 
 69                     temp.getRight();
 70                 else 
 71                     temp.getLeft();
 72             }
 73         }
 74         return null;
 75     }
 76     
 77     //插入一个元素,传入两个参数，一个为当前结点，一个为数据元素
 78     public void insert(BinarySortTreeNode ptr, int item){
 79         if (item < ptr.getData()) {
 80             if (ptr.getLeft()==null) {
 81                 BinarySortTreeNode temp=new BinarySortTreeNode(item);
 82                 temp.setParent(ptr);
 83                 ptr.setLeftChild(temp);
 84             }
 85             else
 86                 insert(ptr.getLeft(), item);
 87         }
 88         if (item > ptr.getData()) {
 89             if (ptr.getRight()==null) {
 90                 BinarySortTreeNode temp=new BinarySortTreeNode(item);
 91                 temp.setParent(ptr);
 92                 ptr.setRightChild(temp);
 93             }
 94             else
 95                 insert(ptr.getRight(), item);
 96         }
 97     }
 98     
 99     
100     //删除某一个元素
101     public void delete(BinarySortTreeNode ptr, int item){
102         if (ptr != null) {
103             if (item<ptr.getData()) 
104                 delete(ptr.getLeft(), item);        //在左子树遍历
105             else if (item > ptr.getData()) 
106                 delete(ptr.getRight(), item);        //在右子树 遍历
107             /*
108              * 当左右子树都存在时,首先查找数据元素值大于要删除结点元素的关键字的最小值，也就是寻找
109              * 要删除结点右子树的最左结点，然后将其拷贝到要删除的结点
110              * 最后删除右子树的最左结点
111              */
112             
113             else if (ptr.getLeft() != null&& ptr.getRight()!=null) {
114                 BinarySortTreeNode min;
115                 min=ptr.getRight();
116                 while(min.getLeft()!=null){
117                     min=min.getLeft();
118                 }
119                 ptr.setData(min.getData());             //将最小数值赋值给ptr元素
120                 //在ptr结点的右子树中递归删除min结点
121                 delete(ptr.getRight(), min.getData());         
122                 
123             }
124             
125             /*
126              * 当待删除结点只有右孩子时,画图理解
127              * 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
128              */
129             
130             else if (ptr.getLeft()==null&&ptr.getRight()!=null) {
131                 ptr.getParent().setRightChild(ptr.getRight());
132                 ptr.getRight().setParent(ptr.getParent());
133                 
134             }
135             /*
136              * 当待删除结点只有左孩子结点时，
137              */
138             else if (ptr.getLeft()!=null&&ptr.getRight()==null) {
139                 ptr.getParent().setLeftChild(ptr.getLeft());
140                 ptr.getLeft().setParent(ptr.getParent());
141             }
142             /*
143              * 当待删除结点为叶子节点时
144              */
145             else {
146                 BinarySortTreeNode parent=ptr.getParent();
147                 if (parent.getLeft()==ptr) {
148                     parent.setLeftChild(null);
149                 }
150                 else{
151                     parent.setRightChild(null);
152                 }
153             }
154         }
155         
156     }  
160 }

总体而言：

二叉排序树的插入，删除，时间复杂度的最重要的的查找部分。

一般情况下：二叉排序树的平均查找长度O(log₂n)

最坏情况下：为一颗单分支退化树平均查找长度为 O(n)