数据结构与算法 整理笔记---二叉搜索树
二叉搜索树
查找问题是计算机中非常重要的基础问题
二分查找法
对于有序数组,才能使用二分查找法(排序作用)
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; } }
总结:
- int mid = (low + high) / 2;如果low 和 high足够大时,low + high会越界。更好的写法为int mid = low + (high - low) / 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) |
二分搜索树的优势
- 不仅可以查找数据,还可以高效地插入,删除数据,动态维护数据
- 可以方便地回答 很多 数据之间的关系问题
min max floor ceil rank select
特性:
- 每个节点的键值大于左孩子
- 每个节点的键值小于右孩子
- 以左右孩子为根的子树仍为二分搜索树
- 不一定是完全二叉树(用数组表示并不方便)
二叉搜索树的创建
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); } }
遍历
前中后序遍历
- 前序遍历
递归法
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); } } }
- 中序遍历
递归法
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; } }
- 后序遍历
递归法
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