二叉排序树(BST)

首先二叉排序树可以认为是Biary Sort Tree或者Biary Search Tree的缩写，也可以解释为二叉查找树，还可以称之为二叉搜索树。

引出

对于之前的线性存储结构比如数组、链表，他们有一个通病就是查找效率低下，就算使用二分查找或者插值查找亦或者斐波那契查找，也不能提升太多在海量数据下的查找效率。

而树结构查找天然就有很大的优势，所以自然就引出了二叉排序树这个概念，来解决传统线性结构的查找效率低下的问题。

定义

一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 左、右子树也分别为二叉排序树；

以上是百度百科粘贴的比较正式化的定义，这里我来翻译一下。

二叉排序树：一棵空二叉树或者这棵非空二叉树中的所有非叶子节点，它的左子节点要比当前节点小，它的右子节点要比当前节点大。

其实我看我翻译的这个定义，像极了之前堆排序中的大顶堆和小顶堆的折中。

在百度上的定义上是要求不可以有相同的值的，这里我们就按照教程中的规定，如果有相同的值可以放在其左子节点或者右子节点。

代码实现-基本结构搭建

节点类编写

还是老一套的三板斧：构造方法、遍历方法、toString方法
但是要注意的是遍历的方法需要时中序遍历，因为二叉排序树只有中序遍历的时候遍历出来时有序的。

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

二叉排序树类编写

这里只需要写入root节点和封装中序遍历的方法就可以了

class BinarySortTree {
    private Node root;
    // 中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("树为空！");
        }
    }
}

代码实现-添加方法

添加的代码还是非常简单的，因为和删除节点比起来添加就是个弟弟。

思想

  1. 如果待添加节点比当前节点小
  2. 判断当前节点是否为空，为空直接将待添加节点添加到当前节点左边
  3. 如果不为空则将左子节点当作当前节点继续进行第一步
  4. 如果待添加节点比当前节点大
  5. 判断当前节点是否为空，为空直接将待添加节点添加到当前节点右
  6. 如果不为空则将右子节点当作当前节点继续进行第一步

图示

二叉排序树添加图例

节点类代码

使用的递归来进行添加代码编写会比较简单

public void add(Node node) {
    if (node == null) {
        return;
    }
    // 传入节点的值，和当前子树的根节点的关系
    if (node.value < this.value) {
        if (this.left == null) {
            this.left = node;
        } else {
            this.left.add(node);
        }
    } else {
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.add(node);
        }
    }
}

二叉排序树类代码

public void add(Node node) {
    if (root == null) {
        root = node;
    } else {
        root.add(node);
    }
}

代码实现-删除代码

之所以删除会比较复杂，是因为需要考虑的情况很多比如：删除叶子节点、删除只有一个子树的节点、删除有两个子树的节点

思想

这里接下来的分析设待删除节点为：target，待删除节点的父节点为parent

删除叶子节点

这个还是算比较简单的：

  1. 查找到target和parent
  2. 判断target是parent的左子树还是右子树
  3. 若为左子树则:parent.left=null
  4. 若为右子树则:```parent.right=null``

删除有一个子树的非叶子节点

  1. 查找到target和parent
  2. 若target有左子树target.left
    1. 如果target是parent的左子树则:parent.left = target.left
    2. 如果target是parent的右子树则:parent.right = target.left
  3. 若target有右子树target.right
    1. 如果target是parent的左子树则:parent.left = target.rigth
    2. 如果target是parent的右子树则:parent.right = target.right

删除有两个子树的非叶子节点

  1. 查找到target
  2. 存储target的左子树的最大节点，或者存储target的右子树的最小(下面的代码中先会以右子树的最小节点为例，但是后面的课后练习中会再补上左子树最大的代码)
  3. 删除掉存储的节点
  4. 将target替换为存储的节点target.value = temp

辅助方法编写

1. 查找target节点

节点类中的代码

public Node search(int value) {
    if (value == this.value) {
        return this;
    } else if(value < this.value) {
        // 查找的值小于当前节点，向左子树递归查找
        // 如果左子节点为空,就代表找不到了
        if (this.left == null) {
            return null;
        }
        return this.left.search(value);
    } else {
        // 查找的值不小于
        if (this.right == null) {
            return null;
        }
        return this.right.search(value);
    }
}

排序树类中的代码

// 查找要删除的节点
public Node search(int value) {
    if (root == null) {
        return null;
    } else {
        return root.search(value);
    }
}

2. 查找parent节点

节点类代码

/**
 * 查找要删除节点的父节点
 * @param value 要查找的值
 * @return 返回是查找的值的父节点
 */
public Node searchParent(int value) {
    if ((this.left != null && this.left.value == value) ||
            (this.right != null && this.right.value == value)) {
        return this;
    } else {
        // 如果查找的值小于当前节点的值，且当前节点的左子节点不为空
        if (value < this.value && this.left!= null) {
            return this.left.searchParent(value);
        } else if (value >= this.value && this.right != null) {
            return this.right.searchParent(value);
        } else {
            return null;
        }
    }
}

排序树类代码

// 查找要删除的节点的父节点
public Node searchParent(int value) {
    if (root == null) {
        return null;
    } else {
        return root.searchParent(value);
    }
}

3. 查找传入节点的最小节点返回并删除

这个方法是直接写在排序树类中的

/**
 * 删除并返回传入节点的最子小节点的值
 * @param node 传入的节点
 * @return 传入节点最小子节点值
 */
public int delRightTreeMin(Node node) {
    Node target = node;
    // 循环的查找左节点就会找到最小值
    while (target.left != null) {
        target = target.left;
    }
    // 这时候target就指向了最小的节点
    // 删除最小节点
    delNode(target.value);
    return target.value;
}

删除方法代码

这个代码的分析实在是写不动，难度倒是不高就是逻辑太复杂了，是完全按照上面的思想写的，但愿以后复习的我可以看懂。

public void delNode(int value) {
    if (root == null) {
        return;
    }
    // 找到要删除的节点
    Node targetNode = search(value);
    // 如果没有找到
    if (targetNode == null) {
        return;
    }
    // 树中只有一个节点
    if (root.left == null && root.right == null) {
        root = null;
        return;
    }
    Node parent = searchParent(value);
    // 如果要删除的节点是叶子节点
    if (targetNode.left == null && targetNode.right == null) {
        if (parent.left != null && targetNode == parent.left) {
            parent.left = null;
        }
        if (parent.right != null && targetNode == parent.right) {
            parent.right = null;
        }
    } else if (targetNode.left != null && targetNode.right != null) {
        // 有两颗子树
        targetNode.value = delRightTreeMin(targetNode.right);
    } else {
        // 只有一个子树
        // 如果要删除的节点有左子节点
        if (targetNode.left != null) {
            if (parent == null) {
                root = targetNode.left;
                return;
            }
            if (parent.left != null && targetNode == parent.left) {
                parent.left = targetNode.left;
            }
            if (parent.right != null && targetNode == parent.right) {
                parent.right = targetNode.left;
            }
        } else {
            if (parent == null) {
                root = targetNode.right;
                return;
            }
            if (parent.left != null && targetNode == parent.left) {
                parent.left = targetNode.right;
            }
            if (parent.right != null && targetNode == parent.right) {
                parent.right = targetNode.right;
            }
        }
    }
}

课后作业-实现删除两个子树的节点的第二种方案

上面代码是用的将右子树中的最小的来替换target，这里就是要求使用左子树中最大的来替换target

先重新写一下寻早最小值的方法改造成找最大值删除，其实也很简单

/**
 * 删除并返回传入节点的最大子节点的值
 * @param node 传入的节点
 * @return 传入节点最大子节点值
 */
public int delLeftTreeMax(Node node) {
    Node target = node;
    // 循环的查找左节点就会找到最小值
    while (target.right != null) {
        target = target.right;
    }
    // 这时候target就指向了最小的节点
    // 删除最小节点
    delNode(target.value);
    return target.value;
}

再改变一下delNode中的调用的代码就好了
将之前的targetNode.value = delRightTreeMin(targetNode.right);改为下述代码就完成了！

targetNode.value = delLeftTreeMax(targetNode.left);

二叉平衡排序树(AVL)

引出

比二叉排序树多了个平衡，那为什么二叉排序树做不到平衡呢？
先看一组例子：将int arr[] = {1,2,3,4,5,6,7}依次添加到一颗二叉排序树中
结果会是
二叉排序树

虽然再名义上还是一棵二叉树但是它的内心早就变成一个单链表了。
这就引出了平衡这一概念，因为树高度越低查找效率越高，这种一条龙形态的二叉排序树是最不想看到的。
可以将二叉排序树做到平衡的算法有很多比如：AVL算法、红黑树、替罪羊树等等。
这里教程中的介绍的是AVL算法，我感觉介绍的比较浅，虽然我十分喜欢红黑树，但是这里还是根据教程只写AVL的算法。才不是我太菜看不懂红黑树呢？

定义

二叉平衡排序树首先是一棵二叉排序树，且它的所有节点具有一个属性为平衡因子，当所有的节点的平衡因子仅为0，1，-1时称这个二叉排序树为二叉平衡排序树。

平衡因子 = 右子树的高度 - 左子树的高度

思路

一棵二叉平衡排序树必须的先是一棵二叉排序树，前者对于后者也仅仅是多了平衡的处理。其实难点也在这个平衡上。

实现调整平衡而又不破坏二叉排序树的结构的方法是旋转，旋转分为左旋，右旋和双旋。

左旋

左旋转用于处理右子树比左子树高的情况，也就是根节点的平衡因子大于1的情况
操作步骤：

  1. 新建一个节点为newNode，存储当前节点
  2. 将newNode的左子树设为当前节点的左子树
  3. 将newNode的右子树设为当前节点的右子树的左子树
  4. 将当前节点的值替换为当前节点的右子树的值
  5. 将当前节点的左子树设置为newNode
  6. 将当前节点的右子树设置为当前节点的右子树的右子树
    左旋
    图中右树的绿色框内是新建的节点，橘色框中是当前节点的右子节点。

右旋

左旋转用于处理左子树比右子树高的情况，也就是根节点的平衡因子小于-1的情况

操作步骤和左旋大同小异，这里就不再啰嗦一遍了只展示图例。

右旋

双旋

双旋转故名思意就是左旋和右旋结合，没有新的知识。
这里只介绍一下什么时候用双旋，和为什么会需要使用双旋。
先看一个例子：arr[] = {10, 11, 7, 6, 8, 9}

使用这个数组构建的二叉排序树，是需要使用右旋来进行平衡调整的，但是单独的右旋是不能将其调整平衡的，具体请情况看图示。

双旋

可以看到进行右旋之后二叉树并没有平衡它的根节点平衡因子由-2变为了2还是不平衡
这时候就要进行双旋的处理了。
也就是如果需要进行右旋的时候左子树的平衡因子>0，则要先对左子树进行左旋然后再对根节点进行右旋，这个过程就成为双旋。

双旋2

代码实现

求树的高度

这里的height很巧妙的用了递归

// 返回当前节点的高度,该节点为根节点的高度
public int height() {
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

// 返回左子树的高度
public int leftHeight() {
    if (left == null) {
        return 0;
    }
    return left.height();
}

// 返回右子树的高度
public int rightHeight() {
    if (right == null) {
        return 0;
    }
    return right.height();
}

左旋右旋实现

// 左旋
private void leftRotate() {
    // 创建新的节点，以当前根节点的值
    Node newNode = new Node(value);
    // 把新的节点的左子树，设置成当前节点的左子树
    newNode.left = left;
    // 把新的节点的右子树设置成当前节点的右子树的左子树
    newNode.right = right.left;
    // 把当前节点的值替换成右子节点的值
    value = right.value;
    // 把当前节点的右子树设置成右子树的右子树
    right = right.right;
    // 把当前节点的左子节点设置为新的节点
    left = newNode;
}
public void rightRotate() {
    Node newNode = new Node(value);
    newNode.right = right;
    newNode.left = left.right;
    value = left.value;
    left = left.left;
    right = newNode;
}

add方法的升级

在添加元素时判断平衡因子是如何旋转来保持平衡，注意旋转的时候要判断双旋转的情况

public void add(Node node) {
    if (node == null) {
        return;
    }
    // 传入节点的值，和当前子树的根节点的关系
    if (node.value < this.value) {
        if (this.left == null) {
            this.left = node;
        } else {
            this.left.add(node);
        }
    } else {
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.add(node);
        }
    }
    // 这之后的代码时保持平衡的代码
    // 当添加完一个节点后，如果右子树的高度-左子树的高度>1 左旋转
    if (rightHeight() - leftHeight() > 1) {
        if (right != null && right.leftHeight() > right.rightHeight()) {
            right.rightRotate(); // 右旋转
        }
        leftRotate(); // 左旋转
        return;
    }
    if (leftHeight() - rightHeight() > 1) {
        if (left != null && left.rightHeight() > left.leftHeight()) {
            left.leftRotate(); // 左旋转
        }
        rightRotate(); // 右旋转
    }
}

Q.E.D.

深至缄默，如云漂泊