50-BST二叉排序树

很久不练习了，把电脑最深处文件夹里面的数据结构和算法的代码拿出来写一下，为了防止老年痴呆。
首先从二叉排序树开始吧。

定义

• 二叉查找树可以是空树。
• 如果非空，则对于其任何节点，其左子树关键字小于其节点值，其右子树都大于其节点值。

常用推论

• 按照中序遍历会得到一个非递减序列。

补充说明

前序遍历

• 先遍历根节点
• 前序遍历左子树
• 前序遍历右子树

中序遍历

• 遍历左节点
• 遍历根节点
• 遍历右节点

后序遍历

• 后序遍历左子树
• 后序遍历右子树
• 后序遍历根节点

重要操作

二叉树的旋转

• 二叉树节点的平衡因子等于左子树的高度减去右子树的高度，整体越平衡的二叉树，查找的效率就越高。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。所以面对最常见的场景，就设计出了左旋和右旋两种操作。
• 由于二叉查找树的性质，调整的时候就是找到一条链上的三个节点，旋转支点是三个主节点中大小居中的那个节点，左旋就是左边的节点降下来，右旋就是右边的节点降下来，都成为中间节点的子树。

• 这里root指的是失去平衡的节点，左边失衡则调整左边的节点，右边失衡则调整右边的节点。TODO(这里描述不准确，还要重新梳理)
• 左左情况(右旋，顺时针): 找到Pivot, 找到Pivot的父节点(root), Pivot的parent指针指向root-parent(取代), Pivot原来的right节点加入root的left, root的parent指针指向Pivot的right。
• 右右情况(左旋, 逆时针): 找到Pivot, 找到Pivot的父节点(root), Pivot的parent指针指向root-parent(取代), Pivot原来的Left节点指到root的Right去, root的parent指针指向Pivot的Left。
• 左右失衡(先左旋, 顺时针): 先找到失衡的三个节点的中间值(因为他要成为三者新的根节点),这种情况下就是三个值高度最低的那个节点，图中是先以3,4,C进行左旋，按照上面的左旋策略,Pivot(4)的parent指针指向其父节点的父节点(5), 其左子节点(因为其原来的父节点root是3，小于4，所以会取代Pivot的左节点的位置)取代C,所以把Pivot的左子节点放到父节点3的右子节点上，然后把Root(3)放到Pivot的左子节点上。然后变成了左左的情况，进行右旋。参考上面的说明操作。
• 右左失衡(先右旋，逆时针): 先找到失衡的三个节点的中间值(因为要以这个中间值作为三者新的根节点),这种情况和左右失衡是一样的，也是高度最低的那个值。然后图中同样是先以Pivot的父节点和左子节点Root(5),Pivot(4)和D进行右旋，然后转化为右右情况，进行左旋。先把Pivot的parent指针指向parent的parent节点，也就是5，取代其右节点的位置。然后把Pivot原来的右节点C放到Root(5)的左节点的位置(填补Pivot走后留下的空缺),然后把Root(5)放到Pivot的右节点位置(填补C走后留下的空缺)。转化为右右情况之后参考上面的情况进行左旋。

关键点

• 构造树
• 插入
• 查找其实是比较高效的，就是找对应的节点即可。
• 找最大和最小同理。
• 删除(删除后的调整)怎么识别怎么替换的问题?
• 左旋右旋操作本身怎么写，以及什么情况下左旋右旋。
• 调整的逻辑边界需要再思考一下。
• 如何检查是否合法。

源代码

package net.xiaoyuyu.ds.ds;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 参考博文二叉查找树
 */
public class BinarySearchTree> {

    public BinarySearchTree() {
    }

    public BinarySearchTree(INodeCreator creator) {
        this.creator = creator;
    }

    private int modifications = 0;

    protected static final Random RANDOM = new Random();

    protected enum Position {
        LEFT, RIGHT
    };

    protected Node root = null;
    protected int size = 0;
    protected INodeCreator creator = null;

    // =====常规操作 ADD DELETE SEARCH UPDATE=====//
    public boolean add(T value) {
        Node nodeAdded = this.addValue(value);
        return (nodeAdded != null);
    }

    protected Node addValue(T value) {
        Node newNode = null;
        if (this.creator == null) {
            newNode = new Node(null, value);
        } else {
            // 创建的时候还不知道他爸是谁
            this.creator.createNewNode(null, value);
        }

        // 如果根节点为空，则把新增节点弄到根节点
        if (root == null) {
            root = newNode;
            size++;
            return newNode;
        }

        Node node = root;
        while (node != null) {
            if (newNode.id.compareTo(node.id) <= 0) { less than or equal to goes left, 其实可以不考虑等于的情况，但是代码不能这么写啊 if (node.lesser="=" null) node.lesser="newNode;" newnode.parent="node;" size++; return newnode; } else 否则用while来递归找到左子树为空的位置放下为止 node="node.lesser;" end left creator right (node.greater="=" node.greater="newNode;" while ** 查看某个值是否存在 * public boolean contains(t value) node node = getNode(value);
        return (node != null);
    }

    /** Locate T in the tree , 也可以用建索引的形式 */
    protected Node getNode(T value) {
        Node current = root;
        while (current != null && current.id != null) {
            if (value.compareTo(current.id) == 0) {
                return current;
            } else if (value.compareTo(current.id) < 0) {
                current = current.lesser;
            } else {
                current = current.greater;
            }
        }
        return null;
    }

    /** 其实就是找最右边的 */
    protected Node getGreatest(Node startingNode) {
        if (startingNode == null) {
            return null;
        }

        Node greater = startingNode.greater;
        while (greater != null && greater.id != null) {
            Node node = greater.greater;
            if (node != null && node.id != null) {
                greater = node;
            } else {
                break;
            }
        }

        return greater;
    }

    protected Node getLeast(Node startingNode) {
        if (startingNode == null) {
            return null;
        }

        Node lesser = startingNode.lesser;
        while (lesser != null && lesser.id != null) {
            Node node = lesser.lesser;
            if (node != null && node.id != null) {
                lesser = node;
            } else {
                break;
            }
        }
        return lesser;
    }

    public boolean remove(T value) {
        Node nodeToRemove = this.removeValue(value);
        return (nodeToRemove != null);
    }

    protected Node removeValue(T value) {
        Node nodeToRemoved = this.getNode(value);
        if (nodeToRemoved != null) {
            Node replacementNode = this.getReplacementNode(nodeToRemoved);
            replaceNodeWithNode(nodeToRemoved, replacementNode);
        }
        return nodeToRemoved;
    }

    /** 找到合适的替换这个节点的节点补上他的位置 */
    protected Node getReplacementNode(Node nodeToRemoved) {
        Node replacement = null;
        Node parent = nodeToRemoved.parent;
        if (parent == null) {// 是根节点的情况
            // Replacing the root node
            if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
                // Replace with lesser subtree. 因为左子树不为空，右子树为空
                replacement = nodeToRemoved.lesser;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser == null) {
                replacement = nodeToRemoved.greater;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser != null) {
                replacement = this.getLeast(nodeToRemoved.greater); // 找到右子树里面最小的
                if (replacement == null) {
                    replacement = nodeToRemoved.greater; // 没找到就用右子树根节点了
                }
            } else {
                // TODO: shengl 两者都为空咋搞?
            }
        } else if (parent.lesser != null && (parent.lesser.id.compareTo(nodeToRemoved.id) == 0)) {
            // 不是根节点，父节点的左子树不为空，且父节点左子树也就是兄弟节点正好和我相等。也就是删除的是左儿子
            // 那么从下面的搞一个上来替换
            if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
                // 左子树不为空且右子树为空，那直接找左子节点好了。
                replacement = nodeToRemoved.lesser;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser == null) {
                // 同上
                replacement = nodeToRemoved.greater;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser != null) {
                replacement = this.getLeast(nodeToRemoved.greater);  // 从右子树里面找最小的
                if (replacement == null) { // 没找到就直接用右子节点了
                    replacement = nodeToRemoved.greater;
                }
            } else {
                // TODO 都为空没说咋搞
            }
        } else if (parent.greater != null && (parent.greater.id.compareTo(nodeToRemoved.id) == 0)) {
            // 如果删除的是右子节点
            if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
                replacement = nodeToRemoved.lesser;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser == null) {
                replacement = nodeToRemoved.greater;
            } else if (nodeToRemoved.greater != null && nodeToRemoved.lesser != null) {
                //Two children - use either the greatest child in the lesser branch or the least child in the greater branch
                //Add some randomness to deletions, so we don't always use the greatest/least on deletion
                if (modifications % 2 != 0) {
                    replacement = this.getGreatest(nodeToRemoved.lesser);
                    if (replacement == null) {
                        replacement = nodeToRemoved.lesser;
                    }
                } else {
                    replacement = this.getLeast(nodeToRemoved.greater);
                    if (replacement == null) {
                        replacement = nodeToRemoved.greater;
                    }
                }
                modifications++;
            }
        }
        return replacement;
    }

    protected void replaceNodeWithNode(Node nodeToRemoved, Node replacementNode) {
        if (replacementNode != null) {
            // save for later
            Node replacementNodeLesser = replacementNode.lesser;
            Node replacementNodeGreater = replacementNode.greater;

            // Replace replacementNode's branches with nodeToRemove's branches,把原来的节点用新节点替换掉
            Node nodeToRemovedLesser = nodeToRemoved.lesser;
            if (nodeToRemovedLesser != null && !nodeToRemovedLesser.equals(replacementNode)) {
                replacementNode.lesser = nodeToRemovedLesser;
                nodeToRemovedLesser.parent = replacementNode;
            }
            Node nodeToRemovedGreater = nodeToRemoved.greater;
            if (nodeToRemovedGreater != null && !nodeToRemovedGreater.equals(replacementNode)) {
                replacementNode.greater = nodeToRemovedGreater;
                nodeToRemovedGreater.parent = replacementNode;
            }

            // Remove link from replacementNode's parent to replacement
            // 因为replacement已经换了位置，他爸不能再指向他了。
            // 把各个指针指向正确的位置
            Node replacementParent = replacementNode.parent;
            if (replacementParent != null && !replacementParent.equals(nodeToRemoved)) {
                // 不为空且没被remove掉
                Node replacementParentLesser = replacementParent.lesser;
                Node replacementParentGreater = replacementParent.greater;
                if (replacementParentLesser != null && replacementParentLesser.equals(replacementNode)) {
                    // 如果替换节点是左儿子，那就把父节点的左儿子指向左儿子的右儿子,并且把替换节点的右儿子的爸换成自己的爸爸。
                    // 如果本来就是空，那就指向空就好了。自己的儿子本来都可以带走，但是不能带走就留给爸爸就好了，理论上是找的最小的。
                    replacementParent.lesser = replacementNodeGreater;
                    if (replacementNodeGreater != null) {
                        replacementNodeGreater.parent = replacementParent;
                    }
                } else if (replacementParentGreater != null && replacementParentGreater.equals(replacementNode)) {
                    // 如果替换节点是他爸的右儿子。
                    replacementParent.greater = replacementNodeLesser;
                    if (replacementNodeLesser != null) {
                        replacementNodeLesser.parent = replacementParent;//同上
                    }
                }
            }
        }

        // Update the link in the tree from the nodeToRemoved to the replacementNode
        Node parent = nodeToRemoved.parent;
        if (parent == null) {
            // replacing the root node
            root = replacementNode;
            if (root != null) {
                root.parent = null;
            } // 替换完了的操作，把根节点的parent指向改掉，否则会错。
        } else if (parent.lesser != null && (parent.lesser.id.compareTo(nodeToRemoved.id) == 0)) {
            // 如果被移除的节点是他爸的左儿子
            parent.lesser = replacementNode;
            if (replacementNode != null) {
                // 把自己的父指针改一下，改到原来node的父指针。
                replacementNode.parent = parent;
            }
        } else if (parent.greater != null && (parent.greater.id.compareTo(nodeToRemoved.id) == 0)) {
            parent.greater = replacementNode;
            if (replacementNode != null) {
                replacementNode.parent = parent;
            }
        }
    }

    public int size() {
        return size;
    }

    public boolean validate() {
        if (root == null) {
            return true;
        }
        return validateNode(root);
    }

    protected boolean validateNode(Node node) {
        Node lesser = node.lesser;
        Node greater = node.greater;

        // 递归检查每一个节点
        boolean lesserCheck = true;
        if (lesser != null && lesser.id != null) {
            lesserCheck = (lesser.id.compareTo(node.id) <= 0); if (lessercheck) { lessercheck="validateNode(lesser);" } (!lessercheck) return false; boolean greatercheck="true;" (greater !="null" && greater.id> 0);
            if (greaterCheck) {
                greaterCheck = validateNode(greater);
            }
        }
        return greaterCheck;
    }
    // =====END ADD DELETE SEARCH UPDATE=====//

    /** 获取一个排序后的数组 */
    public T[] getSorted() {
        // 深度优先遍历
        List> added = new ArrayList>(2);
        T[] nodes = (T[]) new Comparable[size];
        int index = 0;
        Node node = root;
        while (index < size && node != null) {
            Node parent = node.parent;
            Node lesser = (node.lesser != null && !added.contains(node.lesser)) ? node.lesser : null;
            Node greater = (node.greater != null && !added.contains(node.greater)) ? node.greater : null;

            if (parent == null && lesser == null && greater == null) {
                if (!added.contains(node)) {
                    nodes[index++] = node.id;
                    break;
                }
            }

            if (lesser != null) {
                node = lesser;
            } else {
                if (!added.contains(node)) {
                    nodes[index++] = node.id;
                    added.add(node);
                }
                if (greater != null) {
                    node = greater;
                } else if (greater == null && added.contains(node)) {
                    node = parent;
                } else {
                    // We should not get here
                    node = null;
                }
            }
        }
        return nodes;
    }

    @Override
    public String toString() {
        return TreePrinter.getString(this);
    }

    // ===左旋，右旋等非常规操作，主要是为了调整树==//
    /**
     * @param node Root of tree to rotate left. 也就是平衡因素大于2的节点
     *             B                                        B
     *           /   \                                    /   \
     *          L     R(Node)                           L       RR(Pivot)
     *               /  \                                      /    \
     *              RL  RR(Pivot)   ------->                R(Node)   RRR
     *                  / \                               /   \       /   \
     *                RRL   RRR                         RL    RRL     RRRL  RRRR
     *                      /  \
     *                   RRRL   RRRR
     *     对比图
     *             54                                        54
     *           /    \                                     /   \
     *          22     70(Node)                            22    76(Pivot)
     *                /     \                                   /   \
     *               58      76(Pivot) ------>            (Node)70    89
     *                      /   \                           /    \   /  \
     *                     72   89                        58    72  83  101
     *                          /  \
     *                         83   101
     *  解释: 找到Pivot(不平衡节点下两层的节点的中间值), 找到Pivot的父节点(Node), 这里不平衡的需要旋转的是70,76,89这棵树枝
     *  Pivot的parent指针指向root-parent(取代),即76->parent=54,54->right=76
     *  Pivot原来的左节点RRL变成Node的右节点, 即72->parent=Node(70), Node(70)->right=72
     *  Pivot的现在的左节点变成Node,即76->left=Node, Node(70)->parent=76(Pivot)
     */
    protected void rotateLeft(Node node) {
        Position parentPosition = null;// 
        Node parent = node.parent;
        // 现在要找node节点的父亲节点。记录node节点是其父亲的右节点还是左节点，因为后续Pivot要取代其位置的，这里记录一下，后续好处理Pivot的位置
        if (parent != null) {// 
            if (node.equals(parent.lesser)) {
                // Lesser
                parentPosition = Position.LEFT;
            } else {
                // Greater
                parentPosition = Position.RIGHT;
            }
        }

        // 找到右子节点
        Node greater = node.greater;// Pivot
        // 把右子节点置为null,因为要放Pivot的leftson的。
        node.greater = null;
        // 找到左子节点，要动手了，先把他的两个儿子记录下来而已。
        Node lesser = greater.lesser; // 这个lesser要放到node的greater位置的，因为他恰好是最接近的(72)。

        // 把node放到Pivot(右子节点)的Left上去。即降级Root到Pivot的左子树上
        greater.lesser = node;
        // 取代了之后要把node的parent置到Pivot上，不然乱套了
        node.parent = greater;

        // 把Pivot的左子节点变成node的右子节点 
        node.greater = lesser; // 这里有可能是空的，上面画的图只是最完整的情况
        if (lesser != null) {
            lesser.parent = node; // 同样也是把其父节点指针指向node，不然乱套了
        }

        if (parentPosition != null) {
            if (parentPosition == Position.LEFT) {
                parent.lesser = greater;
            } else {
                parent.greater = greater;
            }
            greater.parent = parent;
        } else {
            // 如果没有父节点，那就直接pivot作为新的root节点了。
            root = greater;
            greater.parent = null;
        }
    }

    public void rotateRight(Node node) {
        Position parentPosition = null;
        Node parent = node.parent; // 找到Pivot(失衡三个节点的中间值)的父节点
        if (parent != null) {
            if (node.equals(parent.lesser)) {
                parentPosition = Position.LEFT;
            } else {
                // Greater
                parentPosition = Position.RIGHT;
            }
        }

        Node lesser = node.lesser;
        node.lesser = null;
        Node greater = lesser.greater;

        lesser.greater = node;
        node.parent = lesser;

        node.lesser = greater;
        if (greater != null) {
            greater.parent = node;
        }

        if (parentPosition != null) {
            if (parentPosition == Position.LEFT) {
                parent.lesser = lesser;
            } else {
                parent.greater = lesser;
            }
            lesser.parent = parent;
        } else {
            root = lesser;
            lesser.parent = null;
        }
    }
    // ===End 左旋，右旋等非常规操作，主要是为了调整树==//

    protected static class Node> {
        protected T id = null;
        protected Node parent = null;
        protected Node lesser = null;// prev?
        protected Node greater = null;// next?

        /**
         * Node constructor
         * 
         * @param parent Parent link in the tree, parent can be NULL.
         * @param id     T representing the node in the tree.
         */
        protected Node(Node parent, T id) {
            this.parent = parent;
            this.id = id;
        }

        @Override
        public String toString() {
            return "Node [id=" + id + ", parent=" + parent + ", lesser=" + lesser + ", greater=" + greater + "]";
        }

    }

    protected static interface INodeCreator> {
        /**
         * Create a new Node with the following parameters
         * 
         * @param parent of this node.
         * @param id     of this node
         * @return new Node.
         */
        public Node createNewNode(Node parent, T id);
    }

    protected static class TreePrinter {
        public static > String getString(BinarySearchTree tree) {
            if (tree.root == null)
                return "Tree has no nodes.";
            return getString(tree.root, "", true);
        }

        private static > String getString(Node node, String prefix, boolean isTail) {
            StringBuilder builder = new StringBuilder();

            if (node.parent != null) {
                String side = "left";
                if (node.equals(node.parent.greater))
                    side = "right";
                builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + side + ") " + node.id + "\n");
            } else {
                builder.append(prefix + (isTail ? "└── " : "├── ") + node.id + "\n");
            }
            List> children = null;
            if (node.lesser != null || node.greater != null) {
                children = new ArrayList>(2);
                if (node.lesser != null)
                    children.add(node.lesser);
                if (node.greater != null)
                    children.add(node.greater);
            }
            if (children != null) {
                for (int i = 0; i < children.size() - 1; i++) {
                    builder.append(getString(children.get(i), prefix + (isTail ? "    " : "│   "), false));
                }
                if (children.size() >= 1) {
                    builder.append(
                            getString(children.get(children.size() - 1), prefix + (isTail ? "    " : "│   "), true));
                }
            }

            return builder.toString();
        }
    }
}

运行结果

public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.add(27);
        bst.add(7);
        bst.add(29);
        bst.add(13);
        bst.add(24);
        bst.add(5);
        bst.add(11);
        bst.add(98);
        bst.add(33);
        bst.add(45);
        System.out.println(bst);

        bst.remove(13);
        System.out.println(bst);
    }

└── 27
    ├── (left) 7
    │   ├── (left) 5
    │   └── (right) 13
    │       ├── (left) 11
    │       └── (right) 24
    └── (right) 29
        └── (right) 98
            └── (left) 33
                └── (right) 45
└── 27
    ├── (left) 7
    │   ├── (left) 5
    │   └── (right) 24
    │       └── (left) 11
    └── (right) 29
        └── (right) 98
            └── (left) 33
                └── (right) 45

版权声明

本文标题:50-BST二叉排序树

文章作者:盛领

发布时间:2018年08月19日 - 20:18:13

原始链接:http://blog.xiaoyuyu.net/post/73f47dbe.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如您有任何商业合作或者授权方面的协商，请给我留言：sunsetxiao@126.com

欢迎您扫一扫上面的微信公众号，订阅我的博客！

坚持原创技术分享，您的支持将鼓励我继续创作！

赏

微信打赏

支付宝打赏

数据结构专题 技术专题 二叉树 BST

关于贸易战的一些碎碎念-1

57-从2-3-4树的角度理解红黑树-1