二叉平衡树
约 3531 字大约 12 分钟
二叉搜索/排序树BST及实现
- 对于每个节点 N，其左子树的所有节点的值都小于 N 的值，右子树的所有节点的值都大于 N 的值。
- 查找操作：从根节点开始，如果要查找的值小于当前节点的值，则进入左子树；如果大于当前节点的值，则进入右子树；如果等于当前节点的值，则找到该值。
时间复杂度平均为O(log n)，最坏情况下为O(n)（当树退化为链表时）。 - 插入操作：从根节点开始，依次比较键值，将新节点插入到合适的位置，以保持树的性质。时间复杂度平均为O(log n)，最坏情况下为O(n)。
- 删除操作：分为三种情况：删除叶节点、删除只有一个子节点的节点、删除有两个子节点的节点。删除有两个子节点的节点时，需要找到其前驱或后继节点来替代它的位置。
时间复杂度平均为O(log n)，最坏情况下为O(n)。 - 中序遍历（In-order Traversal）：得到的节点序列是递增排序的。
- 前序遍历（Pre-order Traversal）和后序遍历（Post-order Traversal）：用于特定的树操作和应用场景。
/**
* This file contains an implementation of a Binary Search Tree (BST) Any comparable data is allowed
* within this tree (numbers, strings, comparable Objects, etc...). Supported operations include
* adding, removing, height, and containment checks. Furthermore, multiple tree traversal Iterators
* are provided including: 1) Preorder traversal 2) Inorder traversal 3) Postorder traversal 4)
* Levelorder traversal
*/
public class BinarySearchTree<T extends Comparable<T>> {
private int nodeCount = 0;
private Node root = null;
private class Node {
T data;
Node left, right;
public Node(Node left, Node right, T elem) {
this.data = elem;
this.left = left;
this.right = right;
}
}
public boolean isEmpty() { return size() == 0; }
public int size() { return nodeCount; }
// Add an element to this binary tree. Returns true if we successfully perform an insertion
public boolean add(T elem) {
// Check if the value already exists in this binary tree, if it does ignore adding it
if (contains(elem)) return false;
// Otherwise add this element to the binary tree
root = add(root, elem);
nodeCount++;
return true;
}
// Private method to recursively(递归) add a value in the binary tree
private Node add(Node node, T elem) {//返回子树的根节点
// Base case: found a leaf node
if (node == null) {
node = new Node(null, null, elem);
} else {
// Pick a subtree to insert element
if (elem.compareTo(node.data) < 0) {
node.left = add(node.left, elem);
} else {
node.right = add(node.right, elem);
}
}
return node;
}
// Remove a value from this binary tree if it exists, O(n)
public boolean remove(T elem) {
// Make sure the node we want to remove
// actually exists before we remove it
if (contains(elem)) {
root = remove(root, elem);
nodeCount--;
return true;
}
return false;
}
private Node remove(Node node, T elem) {//返回值 node 表示当前递归调用返回的子树根节点
if (node == null) return null;
int cmp = elem.compareTo(node.data);
// Dig into left subtree, the value we're looking
// for is smaller than the current value
if (cmp < 0) {
node.left = remove(node.left, elem);
// Dig into right subtree, the value we're looking
// for is greater than the current value
} else if (cmp > 0) {
node.right = remove(node.right, elem);
// Found the node we wish to remove
} else {
// This is the case with only a right subtree or
// no subtree at all. In this situation just
// swap the node we wish to remove with its right child.
if (node.left == null) {
Node rightChild = node.right;
node.data = null;
node = null;
return rightChild;
// This is the case with only a left subtree or
// no subtree at all. In this situation just
// swap the node we wish to remove with its left child.
} else if (node.right == null) {
Node leftChild = node.left;
node.data = null;
node = null;
return leftChild;
// When removing a node from a binary tree with two links the
// successor of the node being removed can either be the largest
// value in the left subtree or the smallest value in the right
// subtree. In this implementation I have decided to find the
// smallest value in the right subtree which can be found by
// traversing as far left as possible in the right subtree.
} else {
// Find the leftmost node in the right subtree
Node tmp = findMin(node.right);
// Swap the data
node.data = tmp.data;
// Go into the right subtree and remove the leftmost node we
// found and swapped data with. This prevents us from having
// two nodes in our tree with the same value.
node.right = remove(node.right, tmp.data);
// If instead we wanted to find the largest node in the left
// subtree as opposed to smallest node in the right subtree
// here is what we would do:
// Node tmp = findMax(node.left);
// node.data = tmp.data;
// node.left = remove(node.left, tmp.data);
}
}
return node;
}
// Helper method to find the leftmost node (which has the smallest value)
private Node findMin(Node node) {
while (node.left != null) node = node.left;
return node;
}
// Helper method to find the rightmost node (which has the largest value)
private Node findMax(Node node) {
while (node.right != null) node = node.right;
return node;
}
// returns true is the element exists in the tree
public boolean contains(T elem) {
return contains(root, elem);
}
// private recursive method to find an element in the tree
private boolean contains(Node node, T elem) {
// Base case: reached bottom, value not found
if (node == null) return false;
int cmp = elem.compareTo(node.data);
// Dig into the left subtree because the value we're
// looking for is smaller than the current value
if (cmp < 0) return contains(node.left, elem);
// Dig into the right subtree because the value we're
// looking for is greater than the current value
else if (cmp > 0) return contains(node.right, elem);
// We found the value we were looking for
else return true;
}
// Computes the height of the tree, O(n)
public int height() {
return height(root);
}
// Recursive helper method to compute the height of the tree
private int height(Node node) {
if (node == null) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
}
// This method returns an iterator for a given TreeTraversalOrder.
// The ways in which you can traverse the tree are in four different ways:
// preorder, inorder, postorder and levelorder.
public java.util.Iterator<T> traverse(TreeTraversalOrder order) {
switch (order) {
case PRE_ORDER:
return preOrderTraversal();
case IN_ORDER:
return inOrderTraversal();
case POST_ORDER:
return postOrderTraversal();
case LEVEL_ORDER:
return levelOrderTraversal();
default:
return null;
}
}
// Returns as iterator to traverse the tree in pre order
private java.util.Iterator<T> preOrderTraversal() {
final int expectedNodeCount = nodeCount;
final java.util.Stack<Node> stack = new java.util.Stack<>();
stack.push(root);
return new java.util.Iterator<T>() {
@Override
public boolean hasNext() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return root != null && !stack.isEmpty();
}
@Override
public T next() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
Node node = stack.pop();
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
return node.data;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// Returns as iterator to traverse the tree in order
private java.util.Iterator<T> inOrderTraversal() {
final int expectedNodeCount = nodeCount;
final java.util.Stack<Node> stack = new java.util.Stack<>();
stack.push(root);
return new java.util.Iterator<T>() {
Node trav = root;
@Override
public boolean hasNext() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return root != null && !stack.isEmpty();
}
@Override
public T next() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
// Dig left
while (trav != null && trav.left != null) {
stack.push(trav.left);
trav = trav.left;
}
Node node = stack.pop();
// Try moving down right once
if (node.right != null) {
stack.push(node.right);
trav = node.right;
}
return node.data;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// Returns as iterator to traverse the tree in post order
private java.util.Iterator<T> postOrderTraversal() {
final int expectedNodeCount = nodeCount;
final java.util.Stack<Node> stack1 = new java.util.Stack<>();
final java.util.Stack<Node> stack2 = new java.util.Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
Node node = stack1.pop();
if (node != null) {
stack2.push(node);
if (node.left != null) stack1.push(node.left);
if (node.right != null) stack1.push(node.right);
}
}
return new java.util.Iterator<T>() {
@Override
public boolean hasNext() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return root != null && !stack2.isEmpty();
}
@Override
public T next() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return stack2.pop().data;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
// Returns as iterator to traverse the tree in level order
private java.util.Iterator<T> levelOrderTraversal() {
final int expectedNodeCount = nodeCount;
final java.util.Queue<Node> queue = new java.util.LinkedList<>();
queue.offer(root);
return new java.util.Iterator<T>() {
@Override
public boolean hasNext() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return root != null && !queue.isEmpty();
}
@Override
public T next() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
Node node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
return node.data;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
t108将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
t98检查是否为二叉搜索树
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
t230二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
class Solution {
int i =0;TreeNode node=null;
public int kthSmallest(TreeNode root, int k) {
indexOrder(root);
return node;
}
private void indexOrder(TreeNode root){
if(root == null) return;
if(root.left != null) indexOrder(root.left);
i++;
if(k==i) {node = root;return;}
if(root.right != null) indexOrder(root.right);
}
}
700.二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
class Solution {
// 递归，普通二叉树
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
TreeNode left = searchBST(root.left, val);
if (left != null) {
return left;
}
return searchBST(root.right, val);
}
}
class Solution {
// 递归，利用二叉搜索树特点，优化
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
530二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
class Solution {
TreeNode pre;// 记录上一个遍历的结点
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root==null)return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
if(root==null)return;
//左
traversal(root.left);
//中
if(pre!=null){
result = Math.min(result,root.val-pre.val);
}
pre = root;
//右
traversal(root.right);
}
}
501二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：给定 BST [1,null,2,2],返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
class Solution {
private int maxCount = 0; // 当前众数的最大频率
private int currCount = 0; // 当前元素的频率
private Integer prev = null; // 记录前一个节点的值
private List<Integer> modes = new ArrayList<>(); // 存储众数
public int[] findMode(TreeNode root) {
inorderTraversal(root);
return modes.stream().mapToInt(Integer::intValue).toArray();
}
private void inorderTraversal(TreeNode root) {
if (root == null) return;
// 中序遍历：左
inorderTraversal(root.left);
// 中
if (prev != null && root.val == prev) {
currCount++;
} else {
currCount = 1;
}
if (currCount > maxCount) {
maxCount = currCount;
modes.clear();
modes.add(root.val);
} else if (currCount == maxCount) {
modes.add(root.val);
}
prev = root.val; // 更新 prev
// 中序遍历：右
inorderTraversal(root.right);
}
}
235二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
701二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
TreeNode newRoot = root;
TreeNode pre = root;
//寻找空位
while (root != null) {
pre = root;
//父节点比较大则放在左子树
if (root.val > val) {
root = root.left;
} else if (root.val < val) {
root = root.right;
}
}
//父节点比较大则放在左子树
if (pre.val > val) {
pre.left = new TreeNode(val);
} else {
pre.right = new TreeNode(val);
}
return newRoot;
}
}
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为
// 解法1(最好理解的版本)
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val == key) {
if (root.left == null) {//左子树为空
return root.right;
} else if (root.right == null) {//有子树为空
return root.left;
} else {
//左右孩子节点都不为空，
//将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
//并返回删除节点右孩子为新的根节点。
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
}
669修剪二叉搜索树
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return null;
}
//如果当前节点的值小于low，这意味着当前节点及其左子树中的所有节点都小于low，
//不在范围内。因此，我们需要修剪掉当前节点和其左子树，直接返回修剪后的右子树。
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
// root在[low,high]范围内
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
538把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
思路：此题等价于数组反向遍历求前缀和等价于反后序遍历求和
class Solution {
int sum;
public TreeNode convertBST(TreeNode root) {
sum = 0;
convertBST1(root);
return root;
}
// 按右中左顺序遍历，累加即可
public void convertBST1(TreeNode root) {
if (root == null) {
return;
}
convertBST1(root.right);
sum += root.val;
root.val = sum;
convertBST1(root.left);
}
}