文档章节

二叉查找树

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:00
字数 1166
阅读 3
收藏 0

定义:一个二叉查找树是一棵二叉树,其中每个节点都含有一个Comparable键(以及相关联的值),且每个节点中的键都大于其左子树中的任意节点的键,而小于右子树任意节点的键。
下面是完整的代码:

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    
    private Node root;

    public BinarySearchTree() {
    }
    
    private class Node {
        private Key key;
        private Value value;
        private Node left;
        private Node right;
        private int size;   //以该节点为根的字树中的节点总数(包括自身)
        
        public Node(Key key, Value value, int size) {
            this.key = key;
            this.value = value;
            this.size = size;
        }
    }
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("called put() with a null key");
        if (value == null) {   //插入一个value为null的值代表要删除他
            delete(key);
            return;
        }
        root = put(root, key, value);
    }

    //递归在左右子树中查找直到找到合适位置插入,注意size值,从上往下递归再从下往上返回时重塑
size值
    private Node put(Node node, Key key, Value value) {
        if (node == null) return new Node(key, value, 1);
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0)        node.left = put(node.left, key, value);
        else if (cmp > 0)   node.right = put(node.right, key, value);
        else                node.value = value;
        
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    
    public Value get(Key key) {
        return get(root, key);
    }
    
    private Value get(Node node, Key key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp < 0)        return get(node.left, key);
        else if (cmp > 0)   return get(node.right, key);
        else                return node.value;
    }

    //删除key键
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("called delete() with a null key");
        root = delete(root, key);
    }
    
    private Node delete(Node node, Key key) {
        if (node == null) return null;    //key不存在
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0) node.left = delete(node.left, key);
        else if (cmp > 0) node.right = delete(node.right, key);
        else {
            if (node.left == null) return node.right;  //左子树为空直接返回右子树
            if (node.right == null) return node.left;
            //左右子树都在的情况下,找到右子树中的最小节点,用它来代替被删除节点
            Node temp = node;
            node = min(node.right);
            node.right = deleteMin(temp.right);
            node.left = temp.left;
        }
        node.size = size(node.left) + size(node.right) + 1;  //一个节点大小=左子树大小+右子树大小+1
        return node;
    }

    //删除最大键
    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMax() with empty symbol table");
        root = deleteMax(root);
    }
    
    private Node deleteMax(Node node) {
        if (node.right == null) return node.left;
        node.right = deleteMax(node.right);
        node.size = size(node.right) + size(node.left) + 1;
        return node;
    }

    //删除最小键
    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMin() with empty symbol table");
        root = deleteMax(root);
    }
    
    private Node deleteMin(Node node) {
        if (node.left == null) return node.right;
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    
    public int size() {
        return size(root);
    }
    
    private int size(Node node) {
        if (node == null)   return 0;
        else                return node.size;
    }
    
    private boolean isEmpty() {
        return size() == 0;
    }
    
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null)  return node;
        else                    return min(node.left);
    }
    
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
        return max(root).key;
    }
    
    private Node max(Node node) {
        if (node.right == null) return node;
        else                    return max(node.right);
    }
    
    /**
     * 二叉树中小于等于key的最大key键
     * @param key
     * @return
     */
    public Key floor(Key key) {
        if (key == null) throw new IllegalArgumentException("called floor() with a null key");
        if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
        Node result = floor(root, key);
        if (result == null) return null;
        else                return result.key;
    }
    //递归直到找到key返回,若没有相匹配的则返回最后一个比key小的node,即最后一个调用floor(node.right,key)的node。
原因如下:往左递归寻找是因为要找到一个小于key的node,往右找是因为找到了已经找到了一个小于key的node,
要往右找找有没有更接近key的node,所以最后一个调用floor(node.right,key)的node就是我们想要的值
    private Node floor(Node node, Key key) {
        if (node == null) return null;   //表示树中没有与key相等的值
        int cmp = key.compareTo(node.key);
        if (cmp == 0) return node;   //表示找到了与key相等的值
        if (cmp < 0) return floor(node.left, key);
        Node temp = floor(node.right, key);
        if (temp != null) return temp;
        else              return node;
    }
    
    /**
     * 大于等于key的最小key键
     * @param key
     * @return
     */
    public Key ceiling(Key key) {
        if (key == null) throw new IllegalArgumentException("called ceiling() with a null key");
        if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
        Node result = ceiling(root, key);
        if (result == null) return null;
        else return result.key;
    }
    
    private Node ceiling(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp > 0) return ceiling(x.right, key);
        Node temp = ceiling(x.left, key);
        if (temp != null) return temp;
        else return x;
    }
    
    /**
     * 返回的这个键在树中正好有k个小于它的键
     * @param k
     * @return
     */
    public Key select(int k) {
        if (k < 0 || k >= size()) 
            throw new IllegalArgumentException("called select() with wrong number : " + k);
        Node result = select(root, k);
        return result.key;
    }
    
    private Node select(Node x, int k) {
        int size = size(x.left);
        if (k < size) return select(x.left, k);
        else if (k > size) return select(x.right, k-size-1);
        else return x;
    }
    //返回二叉树中小于key的node的个数
    public int rank(Key key) {
        if (key == null) throw new IllegalArgumentException("argument rank() is null");
        return rank(root, key);
    }
    
    private int rank(Node x, Key key) {
        if (x == null) return 0;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return rank(x.left, key);
        else if (cmp > 0) return 1 + size(x.left) + rank(x.right, key);
        else return size(x.left);
    }

}

二叉查找树平均情况下查找和插入时间复杂需为1.39logn;最坏情况下为n。

本文转载自:http://www.jianshu.com/p/89432dbe1291

上一篇: 归并排序
下一篇: 堆排序
AllenOR灵感
粉丝 11
博文 2635
码字总数 83001
作品 0
程序员
私信 提问

暂无文章

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
10
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部