查找算法总结(3)--二叉查找树_二分搜索树的查找效率与该树的高度有关

转自http://hxraid.iteye.com/blog/609312

一、简介

当所有的静态查找结构添加和删除一个数据的时候，整个结构都需要重建。这对于常常需要在查找过程中动态改变数据而言，是灾难性的。因此人们就必须去寻找高效的动态查找结构，我们在这讨论一个非常常用的动态查找树——二叉查找树 。
二叉查找树的特点：
(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树

我们中序遍历这两棵树发现一个有序的数据序列： 【1 2 3 4 5 6 7 8 】

二、二叉查找树的操作

1、查找操作
在a图中查找关键字6
1）如果数为空，查找失败
2）比较6和根节点，如果相等，查找成功，如果6大于根节点，转向节点的右子树，如果小于6，转向节点的左子树；
3）递归查找每一个节点，直到找到和6相等的节点，否则查找失败。

2、插入操作：
现在我们要查找一个数9，如果不存在则，添加进a图。我们看看二叉查找树动态添加的过程：
1). 数9和根节点4比较(9>4)，则9放在节点4的右子树中。
2). 接着，9和节点5比较(9>5)，则9放在节点5的右子树中。
3). 依次类推：直到9和节点8比较(9>8)，则9放在节点8的右子树中，成为节点8的右孩子。
这个过程我们能够发现，动态添加任何一个数据，都会加在原树结构的叶子节点上，而不会重新建树。 由此可见，动态查找结构确实在这方面有巨大的优势。

3、删除操作：假设p指向待删除的节点，parent指向p的父母节点。删除p节点分为3中情况，根据不同的情况有不同的操作：
1）p是叶节点,直接删除

• p是parent的左子节点，删除p节点并设置parent.left为空
• p是parent的右子节点，删除p节点并设置parent.right为空

2）需要删除的节点只有一个左子树或右子树，用子树代替该点

• 如果p是parent的左子节点并且p有左子节点，设置parent.left指向p的左子节点
• 如果p是parent的左子节点并且p有右子节点，设置parent.left指向p的右子节点
• 如果p是parent的右子节点并且p有左子节点，设置parent.right指向p的左子节点
• 如果p是parent的右子节点并且p有右子节点，设置parent.right指向p的右子节点

3）需要删除的节点左、右子树都存在，此时不直接删除p节点，而是用p节点在中序遍历下的第一个后续节点s代替p节点，然后删除s节点。这样将3）转化为1）或者2）的问题。因为p在中序遍历下的后续节点要么是其右子节点且为叶子结点，要么是右子树中最左边的一个子孙节点，度为0或者1.

三、二叉查找树的实现

package binarytree;
/*
 * 二叉树查找树的表示和操作
 * 1、构建二叉树查找树
 * 2、二叉树查找树的查找，包括任意一个值，最大值，最小值，任意值的前驱和后继
 * 3、二叉树查找树的插入和删除
 * */
public class BSTDemo {
    private BSTDemo tree;
    private Node root;


    public BSTDemo(){}

    public Node getRoot(){
        return root;
    }

    //查找，递归
    public int find(Node node,int value){
        if(node==null) {
            System.out.println("查找失败");
            return value;
        }
        if(node.getKey()==value){
            return value;
        }
        if(node.getKey()>value){
            return find(node.getLChild(),value);
        }
        if(node.getKey()<value){
            return find(node.getRChild(),value);
        }

        return value;
    }

    //查找，非递归
    public int loopFind(Node node,int value){
        while(node!=null){
            if(node.getKey()==value){
                return value;
            }
            if(node.getKey()>value){
                node=node.getLChild();
            }
            else{
                node=node.getRChild();
            }
        }
        System.out.println("查找失败");
        return value;
    }

    //查找最小值
    public Node getMin(Node node){
        while(node.getLChild()!=null){
            node=node.getLChild();
        }
        return node;
    }

    //查找最大值
    public Node getMax(Node node){
        while(node.getRChild()!=null){
            node=node.getRChild();
        }
        return node;
    }

    //获取给定点的前驱
    public Node getPredecessor(Node node){
        //如果左子树不空，前驱是左子树的最大值
        if(node.getLChild()!=null){
            return getMax(node.getLChild());
        }
        //如果左子树为空
        Node p=node.getParent();
        Node x;
        while(p!=null && node==p.getLChild()){
            x=p;
            p=p.getParent();
        }
        return p;
    }
    //获取给顶点的后继
    public Node getSuccessor(Node node){
        //如果右子树不空，后继是右子树的最小值
        if(node.getRChild()!=null){
            return getMin(node.getRChild());
        }
        //如果右子树空
        Node p=node.getParent();
        Node x;
        while(p!=null && node==p.getRChild()){
            x=p;
            p=p.getParent();
        }
        return p;
    }

    //插入，非递归
    public void insert(int value){
        //如果树根为空，则树为空，插入的元素作为根
        Node temp=new Node(value);
        if(this.root==null){
            this.root=temp;
            return;
        }
        //如果树不为空，则查找插入合适的位置
        Node node=root;
        while(node!=null){
            if(node.getKey()==value){
                node.setKey(value);
            }
            if(node.getKey()>value){
                if(node.getLChild()==null){
                    node.setLChild(temp);
                    temp.setParent(node);
                    return;
                }else node=node.getLChild();
            }
            else{
                if(node.getRChild()==null){
                    node.setRChild(temp);
                    temp.setParent(node);
                    return;
                }else node=node.getRChild();
            }
        }
    }

    public void insertAll(int[] array){
        for(int x:array){
            insert(x);
        }
    }

    //给定一个节点，并删除
    public void remove(Node node){
        if(node==null) return;
        if(node.getLChild()==null){
            //左子树为空，用右子树代替
            trans(node,node.getRChild());
        }else if(node.getRChild()==null){
            //如果右子树空，用左子树代替
            trans(node,node.getLChild());
        }else{
            //如果都不空,首先找到该点的直接后继
            Node suc=getSuccessor(node);
            if(suc.getParent()!=node){
                //如果直接后继的父节点不是node,因为suc没有左子树，所有用右子树代替
                trans(suc,suc.getRChild());
                suc.setRChild(node.getRChild());
                suc.getRChild().setParent(suc);
            }
            //如果直接后继是node的右子树，因为suc没有左子树，所以用suc直接代替node
            trans(node,suc);
            suc.setLChild(node.getLChild());
            suc.getLChild().setParent(node);

        }
    }

    //用y替换x
    public void trans(Node x,Node y){
        if (x.getParent()==null){
            //如果是根节点
            this.root=y;
        }else if(x==x.getParent().getLChild()){
            //如果是左子树
            x.getParent().setLChild(y);
        }else x.getParent().setRChild(y);

        if(y==null){
            //如果y是空
            x.setParent(null);
        }
    }
//判断一个二叉树是否为二叉查找树
public boolean isSorted(Node node){
    if(node==null) return true;
    return (node.getLChild()==null || node.getLChild()!=null && node.getKey()>node.getLChild().getKey()&& node.getRChild()==null || node.getRChild()!=null && node.getKey()<node.getRChild().getKey()
&& isSorted(node.getLChild()) && isSorted(node.getRChild()));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

四、性能分析

由于二叉查找树的插入和删除操作花费时间的主要部分是查找操作，所以二叉查找树的各操作性能有查找效率决定。
在一棵有n个节点的二叉差值奥数中查找一个节点，一次成功的查找刚好做过一条从根节点到该节点的路径，比较次数为该节点的高度level，$1\le level \le h$，其中h是树的高度。所以二叉查找树查找成功的平均查找长度不大于该树的高度。而二叉查找树的高度和其形态有关，n个节点的文案二叉树高度最小，为$\lfloor logn \rfloor+1$，n个节点的单支二叉树高度最大，高度为n。所以二叉查找树的平均查找长度为$O(logn)--O(n)$。
二叉查找树的查找效率与二叉树的高度有关，高度越低，查处效率越高。因此，提高二叉查找树查找效率的办法是尽量降低二叉查找树的高度。