查找与二叉树
- 2019 年 10 月 3 日
- 笔记
查找与二叉树
我家园子有几棵树系列
Preface
前面我们学习了基于线性表的数据结构，如数组，链表，队列，栈等。现在我们要开始学习一种非线性的数据结构–树(tree)，是不是很兴奋呢！让我们开始新的系列吧！
查找
先让我们回忆一下线性表的查找，首先最暴力的方法就是做一个线性扫描，一一对比是不是要找的值。这么做的时间复杂度显而易见的是 O(N)，如表格第一行;更机智一点，我们采用二分法，首先将线性表排好顺序，然后每次对比中间的值就好了，这样做的时间复杂度就是 O(logN)，如表格第二行。但上面的做法都是利用的线性数据结构，而它有致命的缺点;那就是进行动态的操作时，比如插入，删除;无法同时实现迅速的查找，只能等重新排序以后再查，效率就低了很多，无法满足日常需求(如下表)。这个时候我们的主角就闪亮登场了——二叉查找树。
二叉查找树的实现
首先我放几张图说明一下什么是二叉树，树的高度，深度等等，详细的介绍我已经放在这里，有兴趣的话也可以看看别人的博客。
图源 转载学习，如侵权则联系我删除！
废话不多说我们开始实现一颗二叉查找树(BST)吧！
[注] 为了方便理解大部分代码都提供了递归实现！
定义数据结构
public class BST<Key extends Comparable<Key>, Value> { private Node root; // root of BST private class Node { private Key key; // sorted by key private Value val; // associated data private Node left, right; // left and right subtrees private int size; // number of nodes in subtree public Node(Key key, Value val, int size) { this.key = key; this.val = val; this.size = size; } } /** * Initializes an empty symbol table. */ public BST() {} /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */ public int size() { return size(root); } // return number of key-value pairs in BST rooted at x private int size(Node x) { if (x == null) return 0; else return x.size; } }中序遍历
我们知道二叉查找树的任一个节点，他的左子结点比他小，右子节点比他大，哈，那么我们只要进行一波中序遍历就可以完成数据的排序啦！
/*************************************************************************** * 中序遍历，非递归版本 ***************************************************************************/ public Iterable<Key> keys() { Stack<Node> stack = new Stack<Node>(); Queue<Key> queue = new Queue<Key>(); Node x = root; while (x != null || !stack.isEmpty()) { if (x != null) { stack.push(x); x = x.left; } else { x = stack.pop(); queue.enqueue(x.key); x = x.right; } } return queue; } /************************************************************************ * 中序遍历，递归打印 ************************************************************************/ public void inOrder(Node* root) { if (root == null) return; inOrder(root.left); print root // 此处为伪代码，表示打印 root 节点 inOrder(root.right); }查找操作
/************************************************************************ * 非递归 ************************************************************************/ Value get(Key key){ Node x = root; while(x != null){ int cmp = key.compareTo(x.key); if(cmp<0) x = x.left; else if(cmp>0) x = x.right; else return x.value; } return null; } /************************************************************************ * 递归 ************************************************************************/ public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val; }插入
/************************************************************************ * 非递归 ************************************************************************/ public void put(Key key, Value val) { Node z = new Node(key, val); if (root == null) { root = z; return; } Node parent = null, x = root; while (x != null) { parent = x; int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else { x.val = val; return; } } int cmp = key.compareTo(parent.key); if (cmp < 0) parent.left = z; else parent.right = z; } /************************************************************************ * 递归版本 ************************************************************************/ public void put(Key key, Value value) { root = put(root, key, value); } private Node put(Node x, Key key, Value value) { if (x == null) return new Node(key, value, 1); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, value); else if (cmp > 0) x.right = put(x.right, key, value); else x.value = value; x.size = 1 + size(x.left) + size(x.right); return x; }删除
删除有两种方式，一种是合并删除，另一种是复制删除，这里我主要讲第二种，想了解第一种可以点这里
删除最小值
在正式的删除之前让我们先热身一下，看看怎么删除一棵树的最小值(如图)。
步骤
- 我们先找到最小值，即不断查找节点的左子节点，若无左节点，那他就是最小值。
- 找到最小的节点后，返回他的右子节点给上一层，最小节点会被GC机制回收
- 因为用的是递归方法，所以依次更新节点数量
public void deleteMin(){ root = deleteMin(root); } private Node deleteMin(Node x){ if (x.left == null) return x.right; x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; }复制(拷贝)删除
在说复制删除之前，我们需要先熟悉二叉查找树的前驱和后继（根据中序遍历衍生出来的概念）。
- 前驱：A节点的前驱是其左子树中最右侧节点。
- 后继：A节点的后继是其右子树中最左侧节点。
上图是复制删除的原理，我们既可以用前驱节点 14 代替，又可以用后继节点 18 代替。
步骤
如图所示，我们分为四个步骤
- 将指向即将被删除的节点的链接保存为t;
- 将 x 指向它的后继节点
min(t.right); - 将 x 的右链接(原本指向一颗所有节点都大于 x.key 的二叉查找树) 指向
deleteMin(t.right)，也就是在删除后所有节点仍然都大于 x.key 的子二叉查找树。 - 将 x 的左链接(本为空) 设为 t.left
public void delete(Key key){ root = delete(root,key); } private Node min(Node x){ if(x.left == null) return x; else return min(x.left); } private Node delete(Node x, Key key){ if(x==null) return null; int cmp = key.compareTo(x.key); if(cmp < 0) x.left = delete(x.left, key); else if(cmp > 0) x.right = delete(x.right, key); else{ if(x.right == null) return x.left; if(x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; }在前面的代码中，我们总是删除node中的后继结点，这样必然会降低右子树的高度，在前面中我们知道，我们也可以使用前驱结点来代替被删除的结点。所以我们可以交替的使用前驱和后继来代替被删除的结点。
J.Culberson从理论证实了使用非对称删除, IPL(内部路径长度)的期望值是 O(n√n), 平均查找时间为 O(√n),而使用对称删除, IPL的期望值为 O(nlgn),平均查找时间为 O(lgn)。
Rank
查找节点 x 的排名
public int rank(Key key){ return rank(key, root); } private int rank(Key key, Node x){ // 返回以 x 为根节点的子树中小于x.key的数量 if(x == null) return 0; int cmp = key.compareTo(x.key); if(cmp<0) return rank(key,x.left); else if(cmp>0) return 1 + size(x.left) + rank(key,x.right); else return size(x.left); }2-3查找树
通过前面的分析我们知道，一般情况下二叉查找树的查找，插入，删除都是 O(lgn)的时间复杂度，但是二叉查找树的时间复杂度是和树的高度是密切相关的，如果我们以升序的元素进行二叉树的插入，我们会发现，此时的二叉树已经退化成链表了，查找的时间复杂度变成了 O(n)，这在性能上是不可容忍的退化！那么我们该怎么解决这个问题呢？
答案相信大家都知道了，那就是构建一颗始终平衡的二叉查找树。那么有哪些平衡二叉查找树呢？如何实现？
这些我们留到下节再讲。
总结
这一节我们学会了使用非线性的数据结构–二叉查找树来高效的实现查找，插入，删除操作。分析了它的性能，在随机插入的情况下，二叉查找树的高度趋近于 2.99lgN ,平均查找时间复杂度为 1.39lgN(2lnN)，而且在升序插入的情况下，树会退化成链表。这些知识为我们后面学习2-3查找树和红黑树打下了基础。
