二分搜尋樹

二分搜尋樹的實作

資料結構之樹（二分搜尋樹，堆和優先隊列）二分搜尋樹堆和優先隊列

二分搜尋樹不一定是完全二叉樹。
左邊都比根節點小，右邊都比根節點大。
如果二叉排序樹是平衡的，其查找效率為O(log2n)，近似于折半查找。如果二叉排序樹完全不平衡，則其深度可達到n，查找效率為O(n)，退化為順序查找。

聲明樹的結構：

public class BST<E extends Comparable<E>> {         //必須具有可比較性
	private class Node {
	     public E e;
	     public Node left, right;
	
	     public Node(E e) {
	         this.e = e;
	         left = null;
	         right = null;
	     }
	 }
    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    // 向二分搜尋樹中添加新的元素e
    public void add(E e){
        root = add(root, e);
    }
	 //方法
	 ...
	 ...
	 ...
}

向以node為根的二分搜尋樹中插入元素e，遞歸算法。不用遞歸，可采用連結清單類型的方法。

public void add(E e){
    root = add(root, e);
}

private Node add(Node node, E e){
    if(node == null){
        size ++;
        return new Node(e);
    }

    if(e.compareTo(node.e) < 0)
        node.left = add(node.left, e);
    else if(e.compareTo(node.e) > 0)
        node.right = add(node.right, e);

    return node;
}

二分搜尋樹的周遊：

public void preOrder(){
    preOrder(root);
}

// 前序周遊以node為根的二分搜尋樹, 遞歸算法
private void preOrder(Node node){
    if(node == null)
        return;

    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}



// 二分搜尋樹的非遞歸前序周遊(棧)
public void preOrderNR(){ 

    if(root == null)
        return;

    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
        Node cur = stack.pop();
        System.out.println(cur.e);

        if(cur.right != null)
            stack.push(cur.right);
        if(cur.left != null)
            stack.push(cur.left);
    }
}

// 二分搜尋樹的層序周遊(隊列)
public void levelOrder(){

    if(root == null)
        return;

    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while(!q.isEmpty()){
        Node cur = q.remove();
        System.out.println(cur.e);

        if(cur.left != null)
            q.add(cur.left);
        if(cur.right != null)
            q.add(cur.right);
    }
}

尋找二分搜尋樹的最小元素及删除：

// 尋找二分搜尋樹的最小元素
public E minimum(){
    if(size == 0)
        throw new IllegalArgumentException("BST is empty");

    Node minNode = minimum(root);
    return minNode.e;
}

// 傳回以node為根的二分搜尋樹的最小值所在的節點
private Node minimum(Node node){
    if( node.left == null )
        return node;

    return minimum(node.left);
}


// 從二分搜尋樹中删除最小值所在節點, 傳回最小值
public E removeMin(){
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

// 删除掉以node為根的二分搜尋樹中的最小節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMin(Node node){

    if(node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size --;
        return rightNode;
    }

    node.left = removeMin(node.left);
    return node;
}

删除任意一個節點：

// 從二分搜尋樹中删除元素為e的節點
public void remove(E e){
    root = remove(root, e);
}

// 删除掉以node為根的二分搜尋樹中值為e的節點, 遞歸算法
// 傳回删除節點後新的二分搜尋樹的根
private Node remove(Node node, E e){

    if( node == null )
        return null;

    if( e.compareTo(node.e) < 0 ){
        node.left = remove(node.left , e);
        return node;
    }
    else if(e.compareTo(node.e) > 0 ){
        node.right = remove(node.right, e);
        return node;
    }
    else{   // e.compareTo(node.e) == 0

        // 待删除節點左子樹為空的情況
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        // 待删除節點右子樹為空的情況
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }

        // 待删除節點左右子樹均不為空的情況
        // 找到比待删除節點大的最小節點, 即待删除節點右子樹的最小節點
        // 用這個節點頂替待删除節點的位置
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;

        node.left = node.right = null;

        return successor;
    }
}

leetcode上相關題目

144. 二叉樹的前序周遊

比較簡單，略

804. 唯一摩爾斯密碼詞

解法：

适合唯一性的資料結構有：

二分排序樹：上面解法自己實作了二分樹
TreeSet：底層是TreeMap
HashSet：底層是HashMap
全局排序一次，去除掉相鄰重複的

堆和優先隊列

堆的實作

資料結構之樹（二分搜尋樹，堆和優先隊列）二分搜尋樹堆和優先隊列

堆是完全二叉樹
用數組存儲二叉堆，從索引1開始，則左節點索引=2*父節點的索引，右節點索引=左節點索引+1。
從索引0開始，則左節點索引=2*父節點的索引+1，右節點索引=左節點索引+1。

資料結構之樹（二分搜尋樹，堆和優先隊列）二分搜尋樹堆和優先隊列

堆的結構：

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    // 傳回堆中的元素個數
    public int size(){
        return data.getSize();
    }

    // 傳回一個布爾值, 表示堆中是否為空
    public boolean isEmpty(){
        return data.isEmpty();
    }
    
    // 傳回完全二叉樹的數組表示中，一個索引所表示的元素的父親節點的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    
    // 傳回完全二叉樹的數組表示中，一個索引所表示的元素的左孩子節點的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 傳回完全二叉樹的數組表示中，一個索引所表示的元素的右孩子節點的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

增加元素，尾部添加，采用siftUp()操作：

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){
    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

删除元素，頂部删除，尾部元素移到頂部，進行siftDown()操作：

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此輪循環中,data[k]和data[j]交換位置
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

heapify操作，使無序數組變成堆：

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
        siftDown(i);
}

優先隊列：

private interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

private class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize(){
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }

    @Override
    public E getFront(){
        return maxHeap.findMax();
    }

    @Override
    public void enqueue(E e){
        maxHeap.add(e);
    }

    @Override
    public E dequeue(){
        return maxHeap.extractMax();
    }
}

leetcode上相關題目

堆的典型應用：求1000000萬個元素前100個最大元素。

先排序則需要nlogn，使用100個空間的堆，則時間複雜度為nlogm，m為100。

347. 前 K 個高頻元素

解法：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int num: nums){
            if(map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> map.get(a) - map.get(b)
            );
        for(int key: map.keySet()){
            if(pq.size() < k)
                pq.add(key);
            else if(map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }
        int[] num = new int[k];
        int i = 0;
        while(!pq.isEmpty()){
            num[i] = pq.remove();
            i++;
        }
                 
        return num;
    }
}

資料結構之樹（二分搜尋樹，堆和優先隊列）二分搜尋樹堆和優先隊列

目錄

二分搜尋樹

二分搜尋樹的實作

leetcode上相關題目

堆和優先隊列

堆的實作

leetcode上相關題目

繼續閱讀

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希