Java平衡二叉树实现

Java平衡二叉树的实现可以使用Java集合框架提供的TreeSet或TreeMap，它们内部都使用红黑树实现平衡二叉树。

红黑树是一种自平衡的二叉查找树，它保证任何一个节点的左右子树的高度差小于两倍。红黑树通过节点的颜色来维护平衡，每个节点不是红色就是黑色，同时满足以下规则：

1. 根节点是黑色的
2. 每个叶子节点（NIL节点，空节点）是黑色的
3. 如果一个节点是红色的，则它的两个子节点都是黑色的
4. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

在Java中，TreeSet和TreeMap都实现了SortedSet和SortedMap接口，它们会对插入元素进行排序，而且支持自然排序或者自定义排序。当插入或删除元素时，它们内部会自动进行平衡操作，以保证树的高度始终保持在log(N)的级别。因此，使用TreeSet和TreeMap实现平衡二叉树是非常方便和高效的。

相关问题

平衡二叉树 java 实现

平衡二叉树（AVL树）是一种自平衡的二叉搜索树，它的左子树和右子树的高度差不超过1。在Java中，可以通过以下步骤实现平衡二叉树：

1. 定义节点类：首先定义一个节点类，包含节点值、左子节点和右子节点等属性。

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

2. 实现平衡二叉树类：创建一个平衡二叉树类，包含插入节点、删除节点、旋转操作等方法。

class AVLTree {
    private Node root;

    // 插入节点
    public void insert(int value) {
        root = insertNode(root, value);
    }

    private Node insertNode(Node root, int value) {
        if (root == null) {
            return new Node(value);
        }

        if (value < root.value) {
            root.left = insertNode(root.left, value);
        } else if (value > root.value) {
            root.right = insertNode(root.right, value);
        } else {
            // 如果存在相同值的节点，可以根据需求进行处理
            return root;
        }

        // 更新节点的高度
        root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

        // 平衡操作
        int balance = getBalance(root);

        // 左左情况，进行右旋操作
        if (balance > 1 && value < root.left.value) {
            return rightRotate(root);
        }

        // 右右情况，进行左旋操作
        if (balance < -1 && value > root.right.value) {
            return leftRotate(root);
        }

        // 左右情况，先左旋再右旋
        if (balance > 1 && value > root.left.value) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // 右左情况，先右旋再左旋
        if (balance < -1 && value < root.right.value) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    // 删除节点
    public void delete(int value) {
        root = deleteNode(root, value);
    }

    private Node deleteNode(Node root, int value) {
        // 空树或未找到节点
        if (root == null) {
            return root;
        }

        if (value < root.value) {
            root.left = deleteNode(root.left, value);
        } else if (value > root.value) {
            root.right = deleteNode(root.right, value);
        } else {
            // 找到要删除的节点

            // 节点只有一个子节点或无子节点
            if (root.left == null || root.right == null) {
                Node temp = null;
                if (temp == root.left) {
                    temp = root.right;
                } else {
                    temp = root.left;
                }

                // 无子节点的情况
                if (temp == null) {
                    temp = root;
                    root = null;
                } else { // 一个子节点的情况
                    root = temp;
                }
            } else {
                // 节点有两个子节点，找到右子树中最小的节点
                Node temp = minValueNode(root.right);

                // 将右子树中最小节点的值赋给要删除的节点
                root.value = temp.value;

                // 删除右子树中最小的节点
                root.right = deleteNode(root.right, temp.value);
            }
        }

        // 更新节点的高度
        root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

        // 平衡操作
        int balance = getBalance(root);

        // 左左情况，进行右旋操作
        if (balance > 1 && getBalance(root.left) >= 0) {
            return rightRotate(root);
        }

        // 左右情况，先左旋再右旋
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // 右右情况，进行左旋操作
        if (balance < -1 && getBalance(root.right) <= 0) {
            return leftRotate(root);
        }

        // 右左情况，先右旋再左旋
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    // 获取节点的高度
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 获取节点的平衡因子
    private int getBalance(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    // 右旋操作
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

    // 左旋操作
    private Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

        return y;
    }

    // 获取最小值节点
    private Node minValueNode(Node node) {
        Node current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }
}

以上是一个简单的平衡二叉树的Java实现，包括插入节点、删除节点、旋转操作等方法。你可以根据需要进行调整和扩展。

java平衡二叉树代码

Java中的平衡二叉树实现通常是基于红黑树算法，这是一种自平衡二叉查找树。在红黑树中，每个节点都被标记为红色或黑色，并满足以下特性：
1. 根节点是黑色的。
2. 所有叶子节点都是黑色的（叶子节点为NIL节点）。
3. 如果一个节点是红色的，则它的两个子节点都是黑色的。
4. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些特性确保了红黑树是平衡的，因为任意路径上的黑色节点数目相同。插入和删除操作可以通过对颜色和结构进行适当的旋转来维护树的平衡性。

下面是一个简单的Java平衡二叉树实现示例：

import java.util.*;

public class RedBlackTree<K extends Comparable<K>, V> {

    private static final boolean RED   = true;
    private static final boolean BLACK = false;

    private Node root;

    private class Node {
        K key;
        V val;
        Node left, right;
        int size;
        boolean color;

        public Node(K key, V val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }

    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == RED;
    }

    private int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }    

    public int size() {
        return size(root);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public V get(K key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root, key);
    }

    private V get(Node x, K key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if      (cmp < 0) x = x.left;
            else if (cmp > 0) x = x.right;
            else              return x.val;
        }
        return null;
    }

    public boolean contains(K key) {
        return get(key) != null;
    }

    public void put(K key, V val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (val == null) {
            delete(key);
            return;
        }
        root = put(root, key, val);
        root.color = BLACK;
    }

    private Node put(Node h, K key, V val) { 
        if (h == null) return new Node(key, val, RED, 1);

        int cmp = key.compareTo(h.key);
        if      (cmp < 0) h.left  = put(h.left,  key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else              h.val   = val;

        // fix-up any right-leaning links
        if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
        if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);

        h.size = size(h.left) + size(h.right) + 1;

        return h;
    }

    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("BST underflow");

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = deleteMin(root);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node deleteMin(Node h) { 
        if (h.left == null)
            return null;

        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);

        h.left = deleteMin(h.left);
        return balance(h);
    }

    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("BST underflow");

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = deleteMax(root);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node deleteMax(Node h) { 
        if (isRed(h.left))
            h = rotateRight(h);

        if (h.right == null)
            return null;

        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);

        h.right = deleteMax(h.right);

        return balance(h);
    }

    public void delete(K key) { 
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        if (!contains(key)) return;

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = delete(root, key);
        if (!isEmpty()) root.color = BLACK;
    }

    private Node delete(Node h, K key) { 
        if (key.compareTo(h.key) < 0)  {
            if (!isRed(h.left) && !isRed(h.left.left))
                h = moveRedLeft(h);
            h.left = delete(h.left, key);
        }
        else {
            if (isRed(h.left))
                h = rotateRight(h);
            if (key.compareTo(h.key) == 0 && (h.right == null))
                return null;
            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);
            if (key.compareTo(h.key) == 0) {
                Node x = min(h.right);
                h.key = x.key;
                h.val = x.val;
                h.right = deleteMin(h.right);
            }
            else h.right = delete(h.right, key);
        }
        return balance(h);
    }

    private Node rotateRight(Node h) {
        assert (h != null) && isRed(h.left);
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    private Node rotateLeft(Node h) {
        assert (h != null) && isRed(h.right);
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = x.left.color;
        x.left.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    private void flipColors(Node h) {
        assert !isRed(h) && isRed(h.left) && isRed(h.right);
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    private Node moveRedLeft(Node h) {
        assert (h != null);
        assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

        flipColors(h);
        if (isRed(h.right.left)) { 
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            flipColors(h);
        }
        return h;
    }

    private Node moveRedRight(Node h) {
        assert (h != null);
        assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);

        flipColors(h);
        if (isRed(h.left.left)) { 
            h = rotateRight(h);
            flipColors(h);
         }
         return h;
     }

     private Node balance(Node h) {
         assert (h != null);

         if (isRed(h.right))                      h = rotateLeft(h);
         if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
         if (isRed(h.left) && isRed(h.right))     flipColors(h);

         h.size = size(h.left) + size(h.right) + 1;
         return h;
     }

     public K min() {
         if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
         return min(root).key;
     } 

     private Node min(Node x) { 
         if (x.left == null) return x; 
         else                return min(x.left); 
     } 

     public K max() {
         if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
         return max(root).key;
     } 

     private Node max(Node x) { 
         if (x.right == null) return x; 
         else                 return max(x.right); 
     } 

     public Iterable<K> keys() {
         if (isEmpty()) return new LinkedList<K>();
         return keys(min(), max());
     }

     public Iterable<K> keys(K lo, K hi) {
         if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
         if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");

         Queue<K> queue = new LinkedList<K>();
         keys(root, queue, lo, hi);
         return queue;
     } 

     private void keys(Node x, Queue<K> queue, K lo, K hi) { 
         if (x == null) return; 
         int cmplo = lo.compareTo(x.key); 
         int cmphi = hi.compareTo(x.key); 
         if (cmplo < 0) keys(x.left, queue, lo, hi); 
         if (cmplo <= 0 && cmphi >= 0) queue.offer(x.key); 
         if (cmphi > 0) keys(x.right, queue, lo, hi); 
     }
}