数据结构的二进制排序树

二叉搜索树是在节点值之间具有一定量级的二叉树. 对于树中的每个节点:

如果存在其左子树，则其左子树中每个节点的值均不大于该节点的值. 如果存在其右子树，则其右子树中每个节点的值都应不小于该节点的值. 该节点的左和右子树都是二进制搜索树. 没有节点具有相等的键值.

public class BSTree<T extends Comparable<T>> {
private BSTNode&lt;T&gt; mRoot;
@Data
public class BSTNode&lt;T extends Comparable&lt;T&gt;&gt; {
    T key;
    BSTNode&lt;T&gt; left;
    BSTNode&lt;T&gt; right;
    BSTNode&lt;T&gt; parent;
    public BSTNode() {
        super();
    }
    public BSTNode(T key, BSTNode&lt;T&gt; left, BSTNode&lt;T&gt; right, BSTNode&lt;T&gt; parent) {
        this.key = key;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

}
前任和后继
前任: 此节点左子树中的最大节点. 值接近于小于.

public BSTNode<T> predecessor(BSTNode<T> x) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x.left != null)
            return maximum(x.left);
    // 如果x没有左孩子。则x有以下两种可能：
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode&lt;T&gt; y = x.parent;
    while ((y != null) &amp;&amp; (x == y.left)) {
        x = y;
        y = y.parent;
    }
    return y;
}</code></pre> 

后继者: 此节点右子树中的最小节点. 该值紧邻大于的值.
public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null)
            return minimum(x.right);
    // 如果x没有右孩子。则x有以下两种可能：
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode&lt;T&gt; y = x.parent;
    while ((y != null) &amp;&amp; (x == y.right)) {
        x = y;
        y = y.parent;
    }
    return y;
}</code></pre> 

O（log2（n））〜O（n）
对于第一个极限情况: 树的深度和完整二叉树中的节点数为n = 2 ^（d + 1）-1. 令二叉树中节点的格式为nc. 然后nc <= 2 ^（d + 1）-1. 然后有d + 1> = log2（nc + 1），因为d + 1是搜索次数，而完整二叉树中的搜索次数是（log2（nc + 1））. 对于第二种极限情况: 搜索过程类似于遍历数组，因此搜索次数为O（n）.
递归搜索:
private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x == null)
            return x;
    int cmp = key.compareTo(x.key);
    if (cmp &lt; 0)
        return search(x.left, key);
    else if (cmp &gt; 0)
        return search(x.right, key);
    else
        return x;
}</code></pre> 
 
public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }

非递归搜索:

private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
        if (cmp &lt; 0)
            x = x.left;
        else if (cmp &gt; 0)
            x = x.right;
        else
            return x;
    }
    return x;
}</code></pre> 
 
public BSTNode<T> iterativeSearch(T key) {
   return iterativeSearch(mRoot, key);
}

二叉树的构建过程与二叉树的搜索过程大致相同.
不同的地方是:
查询过程是比较元素的值是否相等二叉排序树构造，如果相等则返回，如果不相等则判断大小. 迭代查询左右子树，直到找到相同的元素，或者子节点为空，并且返回的节点不存在. 插入的过程是比较元素的值是否相等. 如果元素相等，则返回值指示它们已经存在. 如果元素不相等，则确定大小. 左右子树被迭代直到找到相等的元素，或者如节点为空，则将该节点插入到空节点中. 位置.
private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;
    // 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp &lt; 0)
            x = x.left;
        else
            x = x.right;
    }
    z.parent = y;
    if (y == null)
        bst.mRoot = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp &lt; 0)
            y.left = z;
        else
            y.right = z;
    }
}</code></pre> 
 
public void insert(T key) {
        BSTNode<T> z = new BSTNode<T>(key, null, null, null);
        // 如果新建结点失败，则返回。
        if (z != null)
            insert(this, z);
    }

二进制搜索树删除有以下三种情况:
删除度为0的节点. 删除度为1的节点. 删除度为2的节点.
一个度数为0的节点. 这种类型的节点没有左右子树二叉排序树构造，可以被叶节点直接删除.

一个度数为1的节点只有一个左子树或右子树. 删除此类节点后，为了满足二叉搜索树的结构特征，需要删除其左子树或右子树. 上移.
一个度数为2的节点. 该节点同时具有左子树和右子树. 删除后，为了保持二进制搜索树的结构，您需要在其左侧子树中找到一个最大值以填充它. 节点已删除.
实际操作是:
在左侧子树中找到最大节点Nm. 将要删除的节点的值N替换为Nm. 删除Nm节点.
因为Nm是左子树的最大节点，所以它必须是度为0或1的节点. 这将转化为上述情况.
我认为，此处也可以使用右子树的最小值.
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x = null;
        BSTNode<T> y = null;
    if ((z.left == null) || (z.right == null))
        y = z;
    else
        y = successor(z);
    if (y.left != null)
        x = y.left;
    else
        x = y.right;
    if (x != null)
        x.parent = y.parent;
    if (y.parent == null)
        bst.mRoot = x;
    else if (y == y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;
    if (y != z)
        z.key = y.key;
    return y;
}</code></pre> 
 {2: 9: f: 9: 8: a: 6: a: d: 9: a: a: 4: 7: b: d : c: a: 2: b: 0: 9: 7: 3: b: 2: 3: 3: 2: 3: c: b: e）

找到最大的节点:

private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null)
            return null;
    while (tree.right != null)
        tree = tree.right;
    return tree;
}</code></pre> 
 
public T maximum() {
        BSTNode<T> p = maximum(mRoot);
        if (p != null)
            return p.key;
        return null;
    }

找到最小的节点:
private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null)
            return null;
    while (tree.left != null)
        tree = tree.left;
    return tree;
}</code></pre> 
 
public T minimum() {
        BSTNode<T> p = minimum(mRoot);
        if (p != null)
            return p.key;
        return null;
    }

打印二进制搜索树:
private void print(BSTNode<T> tree, T key, int direction) {
    if (tree != null) {
        if (direction == 0)    // tree是根节点
            System.out.printf("%2d is root\n", tree.key);
        else                // tree是分支节点
            System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
        print(tree.left, tree.key, -1);
        print(tree.right, tree.key, 1);
    }
}</code></pre> 
 
public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }

销毁二叉搜索树:
private void destroy(BSTNode<T> tree) {
        if (tree == null)
            return;
    if (tree.left != null)
        destroy(tree.left);
    if (tree.right != null)
        destroy(tree.right);
    tree = null;
}</code></pre> 
 
public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

二叉搜索树的查询，构造和删除的性能与树的高度有关. 与仅存储数值的数组相比，二叉树的指针占用更多空间. 二叉树是时间交换空间的一种方式. 如果您可以使二叉树保持尽可能的平衡，并且避免发展像数组一样的对角树，那么其时间复杂度将大大降低.
本文由[九分石人]发表在《开源中国》上，原始链接:
					

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-157970-1.html