树

二叉查找树

将二叉树变成二叉查找树，对于树种每个节点X，它的左子树中所有相的值小于X中的值，右子树的所有项的值大于X中的值。

图来自《数据结构与算法分析》

二叉查找树的平均深度为O(logN)，所以不必担心栈内存耗尽。

BinaryNode为BinarySearchTree的内部嵌套类。

private static class BinaryNode<AnyType> {
    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
    
    BinaryNode(AnyType theElement) {
        this(theElement, null null);
    }
    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
        element = theElement;
        left = lt;
        right = rt;
    }
}

BinarySearchTree

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    //二叉查找树的每个节点定义
    private static class BinaryNode<AnyType> {}
    
    private BinaryNode<AnyType> root;
    
    public BinarySearchTree() {
        root = null;
    }
    
    public void makeEmpty() {
        root = null;
    }
    public boolean isEmpty() {
        return root == null;
    }
    
    public boolean contains(AnyType x) {
        return contains(x, root);
    }
    public AnyType findMin() {
        if(isEmpty()) throws new UnderflowException();
        return findMin(root).element;
    }
    public AnyType findMax() {
        if(isEmpty()) throws new UnderflowException();
        return findMax(root).element;
    }
    public void insert(AnyType x) {
        root = insert(x, root);
    }
    public void remove(AnyType x) {
        root = remove(x, root);
    }
    public void printTree(){}
    
    private boolean contains(AnyType x, BinaryNode<AnyType> t) {}
    
    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        //contains方法在二叉查找树中很简单，通过递归即可实现
        if(t == null) return false;
        int compareResult = x.compareTo(t.element);
        if(compareResult < 0) {
            //查找左子树
            return contains(x, t.left);
        } else if(compareResult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        //findMin不断查找左子树最左的一个叶子节点，必然为最小
        if(t == null) {return null;}
        else if(t.left == null) {
            return t;
        }
        return findMin(t.left);
    }
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
        if(t != null) {
            while(t.right != null) {
                t = t.right;
            }
        }
        return t;
    }
    
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if(t == null) {
            return new BinaryNode<AnyType>(x, null, null);
        }
        int compareResult = x.compareTo(t.element);
        
        if(compareResult < 0) {
            t.left = insert(x, t.left);
        } else if(compareResult > 0) {
            t.right = insert(x, t.right);
        }
        
        return t;
    }
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if(t == null) return t;
        int compareResult = x.compareTo(t.element);
        
        if(compareResult < 0) {
            t.left = remove(x, t.left);
        } else if(compareResult > 0) {
            t.right = remove(x, t.right);
        } else if(t.left != null && t.right != null) {
            //第一种情况：左右子树均存在
            t.element = findMin(t.right).element;//将右子树最小的值取代当前节点
            t.right = remove(t.element, t.right);
        } else {
            //第二种情况：右子树不存在
            t = (t.left != null) ? t.left: t.right;
        }
        return t;
    }
    private void printTree(BinaryNode<AnyType> t) {}
}

红黑树

红黑树是一种自平衡的二叉查找树，解决二叉查找树在极端情况下变为线性链表的情况。红黑树有以下特点：

红黑树是二叉搜索树。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量（称之为“黑高”）必须相等)。

插入流程查看：一般新插入的为红色节点，根据以下情况进行回溯

调整右边红色节点，如左边为黑色节点，右边为红色，将右边红色链接转到左边来，就是对下图中b节点做左旋和变色操作。
如果当左右叶子节点均为红色节点时，就如下图，将b节点变色，左右节点变为黑色。
当为连续红色节点时，如下图所示，将b节点做右旋操作和变色操作。

基本上，感觉插入之后，变色比较麻烦，还得进行旋转操作进行位置变换。具体详细插入过程可以看看这篇文章，作者良心画制，精品。

数据结构--树

二叉树

树

二叉查找树

红黑树

CATALOG

FEATURED TAGS

FRIENDS