数据结构与算法 整理笔记---二叉搜索树

二叉搜索树

查找问题是计算机中非常重要的基础问题

二分查找法

对于有序数组,才能使用二分查找法(排序作用)

public class BinarySearch {
    public static int binarySearch(Comparable[] arr, Comparable target) {

        if (arr == null || arr.length == 0) {
            return -1;
        }
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) {
                return mid;
            } else if (arr[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return -1;
    }
}

总结:

  1. int mid = (low + high) / 2;如果low 和 high足够大时,low + high会越界。更好的写法为int mid = low + (high - low) / 2;
  2. compareTo
    Returns:

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)).

floor算法的实现

public static int floor(Comparable[] arr, Comparable target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        if (arr[0].compareTo(target) > 0) {
            return -1;
        }

        int n = arr.length;
        int l = 0, r = n - 1;
        int floor = 0;
        boolean found = false;
        while (l < r) {
            floor = l + (r - l) / 2;
            if (arr[floor].compareTo(target) == 0) {
                found = true;
                break;
            } else if (arr[floor].compareTo(target) > 0) {
                r = floor - 1;
            } else {
                l = floor + 1;
            }
        }
        if (found) {
            while (floor >= 1 && arr[floor - 1].compareTo(arr[floor]) == 0) {
                floor--;
            }
            return floor;
        } else {
            if (l == r) {
                if (arr[l].compareTo(target) < 0) {
                    return l;
                } else {
                    return (l - 1) >= 0 ? l - 1 : 0;
                }
            } else {
                return Math.min(l, r);
            }
        }
    }

总结:边界条件比较多,但是应该有更优的算法。算法复杂度应该为min(O(logn), O(m)),其中m为target元素重复的个数,即while循环中floor遍历的个数

二分搜索树

优势:为实现查找表这种数据结构,也即字典。

查找元素插入元素删除元素
普通数组O(n)O(n)O(n)
顺序数组O(logn)O(n)O(n)
二分搜索树O(logn)O(logn)O(logn)

二分搜索树的优势

  1. 不仅可以查找数据,还可以高效地插入,删除数据,动态维护数据
  2. 可以方便地回答 很多 数据之间的关系问题

min max floor ceil rank select

特性:

  1. 每个节点的键值大于左孩子
  2. 每个节点的键值小于右孩子
  3. 以左右孩子为根的子树仍为二分搜索树
  4. 不一定是完全二叉树(用数组表示并不方便)

二叉搜索树的创建

package com.meituan.search;
class Node<K, V> {
    K key;
    V value;
    Node left;
    Node right;
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.left = this.right = null;
    }
}

public class BinarySearchTree {
    private Node root;
    int count;

    public BinarySearchTree() {
        this.root = null;
        this.count = 0;
    }

    public int size() {
        return count;
    }

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

插入新节点 insert

public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    private Node insert(Node node, K key, V value) {
        if (node == null) {
            count++;
            return new Node(key, value);
        }

        if (key == node.key) {
            node.value = value;
        } else if (key < node.key) {
            node.left = insert(node.left, key, value);
        } else {
            node.right = insert(node.right, key, value);
        }

        return node;
    }

总结:
私有方法返回一个node的原因是在退出递归时构建子树

查找元素

/**
    * 返回值的方式
    * 1. 返回node,不好Node为内部类
    * 2. 返回Value
    */
    public V search(K key) {
        return search(root, key);
    }

    private V search(Node root, K key) {
        if (root == null) {
            return null;
        } 

        if (key == root.key) {
            return root.value;
        } else if (key < root.key) {
            return search(root.left, key)
        } else {
            return search(root.right, key);
        }
    }

遍历

前中后序遍历

  1. 前序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    System.out.println(root.value);
    traverseRec(root.left);
    traverseRec(root.right);
}

迭代法
Stack可以解决,Queue无法解决

public void preOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);

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

        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}
  1. 中序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    traverseRec(root.left);
    System.out.println(root.value);
    traverseRec(root.right);
}

迭代法

public void inOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    Node cur = root;
    while (true) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        if (stack.isEmpty()) {
            break;
        }

        cur = stack.pop();
        System.out.println(cur.value);
        cur = cur.right;
    }
}
  1. 后序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    traverseRec(root.left);
    traverseRec(root.right);    
    System.out.println(root.value);
}

迭代法

public void inOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    Stack<Node> out = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        out.push(cur);

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

    while (!out.isEmtpy()) {
        Node cur = out.pop();
        System.out.println(cur.value);
    }
}

广度优先遍历 (层序优先遍历)

public void levelOrder(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node cur = queue.offer();
        System.out.println(cur.value);

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

删除节点

首先删除最小值和最大值

查找到最大值或最小值

K minimun() {
    if (count == 0) {
        return null;
    }

    return minimum(root).key;
}

K maximum() {
    if (count == 0) {
        return null;
    }
    return maximum(root);
}

private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }
    return minimun(node.left);
}

private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }
    return maximum(node.right);
}

删除最小值,找到最左子树,如果该子树还有右子树,将该右子树挂到被删除结点的位置上来

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

    root = removeMin(root);
}

private Node removeMin(Node node) {
    if (node.left == null) {
        count--;
        return node.right;
    }
    node.left = removeMin(node.left);
    return node;
}

删除最大值,找到最右子树,如果该子树还有左子树,将该左子树挂到被删除结点的位置上来

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

private Node removeMax(Node node) {
    if (node.right == null) {
        count--;
        return node.left;
    }
    node.right = removeMax(node.right);
    return node;
}

删除任意结点

删除最大及最小值的算法,同样适用于只有左孩子或者右孩子的节点;难点在于,删除既有左孩子又有右孩子的节点

public Node deleteNode(Node node, K key) {
    if (node == null) {
        return;
    }
    if (key < node.key) {
        node.left = deleteNode(node.left, key);
        return node;
    } else if (key > node.key) {
        node.right = deleteNode(node.right, key);
        return node;
    } else {
        // node.key == key 
        if (node.left == null) {
            count--;
            return node.right;
        }
        if (node.right == null) {
            count--;
            return node.left;
        }

        Node successor = new Node(minimum(node.right).key, minimum(node.right).value);
        count++;
        successor.right = removeMin(node.right);
        successor.left = node.left;
        return successor;
    }
}

二分搜索树的局限性

二分搜索树可能退化成链表,改造方法是平衡二叉树,最著名的解决方法为红黑树

平衡二叉树和堆的结合:Treap

相关推荐