二分搜尋樹02：二分搜尋樹的應用

基于二分搜尋樹的集合實作（Set）

不能添加重複元素

集合是有序的，效率高

interface Set<E>{

    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

class BSTSet<E extends Comparable<E>> implements Set<E>{

    private BinarySearchTree bst;

    public BSTSet(){

        bst = new BinarySearchTree();
    }

    @Override
    public int getSize(){

        return bst.size();
    }

    @Override
    public boolean isEmpty(){

        return bst.isEmpty();
    }

    @Override
    public void add(E e){

        bst.add(e);
    }

    @Override
    public void remove(E e){

        bst.remove(e);
    }

    @Override
    public boolean contains(E e){

        return bst.contains(e);
    }
}

class BinarySearchTree<E extends Comparable<E>> {

    private class Node{

        public E e;
        public Node leftNext;
        public Node rightNext;

        private Node(E e){

            this.e = e;
            leftNext = null;
            rightNext = null;
        }
    }

    private Node root;
    private int size;

    public BinarySearchTree(){

        root = null;
        size = 0;
    }

    public int size(){

        return size;
    }

    public boolean isEmpty(){

        return size == 0;
    }

    public void add(E e) {

        root = add(root, e);
    }

    private Node add(Node root, E e){

        if (root == null){

            size++;

            return new Node(e);
        }

        if (root.e.compareTo(e) < 0){
            root.rightNext = add(root.rightNext, e);
        }
        else if (root.e.compareTo(e) > 0) {
            root.leftNext = add(root.leftNext, e);
        }

        return root;
    }

    public E removeMin(){

        E value = Min();
        root = removeMin(root);

        return value;
    }

    private Node removeMin(Node root){

        if (root.leftNext == null){

            Node newRoot = root.rightNext;
            root.rightNext = null;
            size--;

            return newRoot;
        }

        root.leftNext = removeMin(root.leftNext);

        return root;
    }

    public void remove(E e){

        root = remove(root, e);
    }

    private Node remove(Node root, E e){

        if (root == null){
            return null;
        }

        if (root.e.compareTo(e) < 0){

            root.rightNext = remove(root.rightNext, e);
            return root;
        }
        else if (root.e.compareTo(e) > 0){

            root.leftNext = remove(root.leftNext, e);
            return root;
        }
        else {

            if (root.leftNext == null) {

                Node newRoot = root.rightNext;
                root.rightNext = null;
                size--;

                return newRoot;
            } else if (root.rightNext == null) {

                Node newRoot = root.leftNext;
                root.leftNext = null;
                size--;

                return newRoot;
            } else {

                Node newRoot = Min(root.rightNext);
                newRoot.rightNext = removeMin(root.rightNext);
                newRoot.leftNext = root.leftNext;
                root.leftNext = null;
                root.rightNext = null;

                return newRoot;
            }
        }
    }

    public boolean contains(E e){

        return contains(root, e);
    }

    private boolean contains(Node root, E e){

        if (root == null) {
            return false;
        }

        if (root.e.compareTo(e) == 0){
            return true;
        }
        else if (root.e.compareTo(e) > 0){
            return contains(root.leftNext, e);
        }
        else {
            return contains(root.rightNext, e);
        }
    }

    public E Min(){

        return Min(root).e;
    }

    private Node Min(Node root){

        if (root == null){
            return null;
        }

        if (root.leftNext == null){
            return root;
        }

        return Min(root.leftNext);
    }
}

基于連結清單的集合實作

集合是無序的

interface Set<E>{

    void add(E e, int index);
    void remove(int index);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

class LinkedListSet<E> implements Set<E>{

    private LinkedList linkedList;

    public LinkedListSet(){

        linkedList = new LinkedList<>();
    }

    @Override
    public int getSize(){

        return linkedList.size();
    }

    @Override
    public boolean isEmpty(){

        return linkedList.isEmpty();
    }

    @Override
    public void add(E e, int index){

        if (!linkedList.contains(e)) {
            linkedList.add(e, index);
        }
    }

    @Override
    public void remove(int index){

        linkedList.remove(index);
    }

    @Override
    public boolean contains(E e){

        return linkedList.contains(e);
    }
}

class LinkedList<E>{

    class Node{

        public E e;
        public Node next;

        public Node(E e, Node next){

            this.e = e;
            this.next = next;
        }

        public Node(){

            this.next = null;
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList(){

        dummyHead = new Node();
        size = 0;
    }

    public int size(){

        return size;
    }

    public boolean isEmpty(){

        return isEmpty();
    }

    private Node getPrevNode(int index){

        if (index < 0 || index > size){
            throw new IllegalArgumentException("索引不合法");
        }

        if (index == 0){
            return dummyHead;
        }

        return getPrevNode(index - 1).next;
    }

    public void add(E e, int index){

        Node prev = getPrevNode(index);

        prev.next = new Node(e, prev.next);
        size++;
    }

    public E remove(int index){

        if (index == size){

            throw new IllegalArgumentException("索引不合法");
        }

        Node prev = getPrevNode(index);

        Node temp = prev.next;
        prev.next = temp.next;
        temp.next = null;
        size--;

        return temp.e;
    }

    public boolean contains(E e){

        for (Node prev = dummyHead; prev.next != null; prev = prev.next) {

            if (prev.next.e.equals(e)){
                return true;
            }
        }

        return false;
    }
}

基于連結清單的映射實作（Map）

存儲（鍵，值）資料對的資料結構，根據鍵尋找值

無序

interface Map<K, V>{

    void add(K key, V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key, V value);
    int getSize();
    boolean isEmpty();
}

class LinkedListMap<K, V> implements Map<K, V>{

    class Node{

        public K key;
        public V value;
        public Node next;

        public Node(K key, V value, Node next){

            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(){

            this(null, null, null);
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap(){

        dummyHead = new Node();
        size = 0;
    }

    @Override
    public int getSize(){

        return size;
    }

    @Override
    public boolean isEmpty(){

        return size == 0;
    }

    private Node getNode(K key){

        Node cur = dummyHead.next;

        while (cur != null){

            if (cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }

        return null;
    }

    @Override
    public boolean contains(K key){

        return getNode(key) != null;
    }

    @Override
    public V get(K key){

        Node res = getNode(key);
        return res == null ? null : res.value;
    }

    @Override
    public void add(K key, V value){

        Node res = getNode(key);

        if (res == null){
            dummyHead.next = new Node(key, value, dummyHead.next);
        }

        res.value = value;
    }

    @Override
    public void set(K key, V value) {

        Node res = getNode(key);

        if (res == null){
            throw new IllegalArgumentException("沒有這個鍵");
        }

        res.value = value;
    }

    @Override
    public V remove(K key){

        Node prev = dummyHead;

        while (prev.next != null){

            if (prev.next.key.equals(key)){

                Node temp = prev.next;
                prev.next = temp.next;
                temp.next = null;
                size--;

                return temp.value;
            }

            prev = prev.next;
        }

        return null;
    }
}

拓展：用哈希表實作的無序集合和映射，效率比二分搜尋樹更高

基于二分搜尋樹的映射實作

interface Map<K, V>{

    void add(K key, V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key, V value);
    int getSize();
    boolean isEmpty();
}

class BSTMap<K extends Comparable<K>, V> implements Map<K, V>{

    class Node{

        public K key;
        public V value;
        public Node leftNext;
        public Node rightNext;

        public Node(K key, V value){

            this.key = key;
            this.value = value;
            leftNext = null;
            rightNext = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){

        root = null;
        size = 0;
    }

    @Override
    public int getSize(){

        return size;
    }

    @Override
    public boolean isEmpty(){

        return size == 0;
    }


    private Node getNode(Node root, K key){

        if (root == null){
            return null;
        }

        if (root.key.compareTo(key) == 0){
            return root;
        }
        else if (root.key.compareTo(key) > 0){
            return getNode(root.leftNext, key);
        }
        else {
            return getNode(root.rightNext, key);
        }
    }

    @Override
    public boolean contains(K key){

        return getNode(root, key) != null;
    }

    @Override
    public V get(K key){

        Node res = getNode(root, key);

        return res == null ? null : res.value;
    }

    @Override
    public void add(K key, V value){

        root = add(root, key, value);
    }

    private Node add(Node root, K key, V value){

        if (root == null){

            size++;
            return new Node(key, value);
        }

        if (root.key.compareTo(key) > 0){
            root.leftNext = add(root.leftNext, key, value);
        }
        else if (root.key.compareTo(key) < 0){
            root.rightNext = add(root.rightNext, key, value);
        }
        else {
            root.value = value;
        }

        return root;
    }

    @Override
    public void set(K key, V value) {

        Node res = getNode(root, key);

        if (res == null){
            throw new IllegalArgumentException("鍵值不存在");
        }
        else {
            res.value = value;
        }
    }

    private Node Min(Node root){

        if (root.leftNext == null){
            return root;
        }

        return Min(root.leftNext);
    }

    private Node removeMin(Node root){

        if (root.leftNext == null){

            Node newRoot = root.rightNext;
            root.rightNext = null;
            size--;

            return newRoot;
        }

        root.leftNext = removeMin(root.leftNext);

        return root;
    }

    @Override
    public V remove(K key){

        Node res = getNode(root, key);

        if (res == null){
            throw new IllegalArgumentException("鍵值不存在");
        }

        root = remove(root, key);

        return res.value;
    }

    private Node remove(Node root, K key){

        if (root.key.compareTo(key) > 0){

            root.leftNext = remove(root.leftNext, key);
            return root;
        }
        else if (root.key.compareTo(key) < 0){

            root.rightNext = remove(root.rightNext, key);
            return root;
        }
        else {

            if (root.leftNext == null) {

                Node newRoot = root.rightNext;
                root.rightNext = null;
                size--;

                return newRoot;
            }
            else if (root.rightNext == null) {

                Node newRoot = root.leftNext;
                root.leftNext = null;
                size--;

                return newRoot;
            }
            else {

                Node min = Min(root.rightNext);
                min.rightNext = removeMin(root.rightNext);
                min.leftNext = root.leftNext;
                root.leftNext = null;
                root.rightNext = null;

                return min;
            }
        }
    }
}

二分搜尋樹02：二分搜尋樹的應用

基于二分搜尋樹的集合實作（Set）

基于連結清單的集合實作

基于連結清單的映射實作（Map）

基于二分搜尋樹的映射實作

複雜度分析

繼續閱讀

HDU 4719 Oh My Holy FFF

CSU 1561 (More) Multiplication

CSU 1563 Lexicography

HDU 4721 Food and Productivity

ZOJ 1041 Transmitters

CSU 1562 Fun House

CodeChef PALPROB Palindromeness

UVA 10344- 23 out of 5

ZOJ 1104 Leaps Tall Buildings

HDU 2821 Pusher

UVA 1401 Remember the Word

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

JAVA 系列——>開發工具IntelliJ IDEA的安裝以及配置、快捷鍵IDEA 簡介

UVA 519 Puzzle (II)

磁盤結構及在Linux中的命名