《漫画算法2》源码整理-1 二分查找树 AVL树红黑树

本文主要是介绍《漫画算法2》源码整理-1 二分查找树 AVL树红黑树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分查找树

public class BinarySearchTree {
    private Node root;

    //查找结点
    public Node search(int data) {
        Node targetNode = root;
        while (targetNode!=null && targetNode.data != data) {
            if (data > targetNode.data) {
                targetNode = targetNode.right;
            } else {
                targetNode = targetNode.left;
            }
        }
        if(targetNode == null){
            System.out.println("未找到结点：" + data);
        } else {
            System.out.println("已找到结点：" + data);
        }
        return targetNode;
    }

    //中序遍历
    public static void inOrderTraversal(Node node){
        if(node == null){
            return;
        }
        inOrderTraversal(node.left);

        System.out.print(node.data + " ");
        inOrderTraversal(node.right);
    }

    //插入结点
    public boolean insert(int data) {
        Node node = new Node(data);
        if(root == null){
            root = node;
            return true;
        }
        Node targetNode  = root;
        while (targetNode != null) {
            if( data == targetNode.data){
                System.out.println("二叉查找树中已有重复的结点：" + data);
                return false;
            }
            else if (data > targetNode.data) {
                if(targetNode.right == null){
                    targetNode.right = node;
                    return true;
                }
                targetNode = targetNode.right;
            }
            else {
                if(targetNode.left == null){
                    targetNode.left = node;
                    return true;
                }
                targetNode = targetNode.left;
            }
        }
        return true;
    }

    //删除结点
    public boolean delete(int data) {
        Node targetNode = root;
        Node parentNode = new Node(data);
        //判断待删除结点是否存在
        while (targetNode.data != data) {
            parentNode = targetNode;
            if (data > targetNode.data) {
                targetNode = targetNode.right;
            } else {
                targetNode = targetNode.left;
            }
            if (targetNode == null) {
                // 没有找到待删除结点
                return false;
            }
        }
        // 待删除结点没有子节点
        if (targetNode.right==null && targetNode.left==null) {
            if (targetNode == root) {
                //待删除结点是根结点
                root = null;
            } else {
                if (parentNode.right == targetNode) {
                    parentNode.right = null;
                } else {
                    parentNode.left = null;
                }
            }
        }
        //待删除结点有一个子结点（右）
        else if(targetNode.left == null) {
            if(targetNode == root) {
                root = targetNode.right;
            } else if(parentNode.right == targetNode) {
                parentNode.right = targetNode.right;
            } else {
                parentNode.left = targetNode.right;
            }
        }
        //待删除结点有一个子结点（左）
        else if(targetNode.right == null) {
            if(targetNode == root) {
                root = targetNode.left;
            } else if(parentNode.right == targetNode) {
                parentNode.right = targetNode.left;
            } else {
                parentNode.left = targetNode.left;
            }
        }
        //待删除结点有两个子结点
        else {
            //待删除结点的后继结点的父结点
            Node successParentNode = targetNode;
            //待删除结点的后继结点
            Node successNode = targetNode.right;
            while(successNode.left != null)
            {
                successParentNode = successNode;
                successNode = successNode.left;
            }
            //把后继结点复制到待删除结点位置
            targetNode.data = successNode.data;
            //删除后继结点
            if(successParentNode.right == successNode) {
                successParentNode.right = successNode.right;
            } else {
                successParentNode.left = successNode.right;
            }
        }
        return true;
    }

    // 结点类
    private class Node {
        int data;
        Node right;
        Node left;

        Node(int data){
            this.data = data;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        int input[]= {6,3,8,2,5,7,9,1,4};
        for(int i=0; i<input.length; i++) {
            tree.insert(input[i]);
        }
        inOrderTraversal(tree.root);
        System.out.println();
        tree.search(3);
        tree.delete(3);
        tree.search(3);
        tree.delete(6);
        inOrderTraversal(tree.root);
    }
}

AVL树

import java.util.LinkedList;
import java.util.Queue;

public class AVLTree {
    private TreeNode root;
    /*
     * 获取树的高度
     */
    private int height(TreeNode node) {
        if (node != null)
            return node.height;

        return 0;
    }

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

    //查找结点
    public TreeNode search(TreeNode node, int data) {
        while (node!=null) {
            if (data < node.data)
                node = node.left;
            else if (data > node.data)
                node = node.right;
            else
                return node;
        }
        return node;
    }

    //左左局面旋转
    private TreeNode leftLeftRotation(TreeNode node) {
        //leftChildNode 对应示意图中的结点B
        TreeNode leftChildNode = node.left;
        node.left = leftChildNode.right;
        leftChildNode.right = node;
        //刷新结点A和结点B的高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        leftChildNode.height = Math.max(height(leftChildNode.left), node.height) + 1;
        //返回旋转后的父结点
        return leftChildNode;
    }

    //右右局面旋转
    private TreeNode rightRightRotation(TreeNode node) {
        //rightChildNode 对应示意图中的结点B
        TreeNode rightChildNode = node.right;
        node.right = rightChildNode.left;
        rightChildNode.left = node;
        //刷新结点A和结点B的高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        rightChildNode.height = Math.max(height(rightChildNode.right), node.height) + 1;
        //返回旋转后的父结点
        return rightChildNode;
    }

    //左右局面旋转
    private TreeNode leftRightRotation(TreeNode node) {
        //先做左旋
        node.left = rightRightRotation(node.left);
        //再做右旋
        return leftLeftRotation(node);
    }

    //右左局面旋转
    private TreeNode rightLeftRotation(TreeNode node) {
        //先做右旋
        node.right = leftLeftRotation(node.right);
        //再做左旋
        return rightRightRotation(node);
    }

    //插入结点
    public void insert(int data) {
        root = insert(root, data);
    }

    //插入结点详细过程（递归）
    private TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            node = new TreeNode(data);
        } else {
            if (data < node.data) {
                //新结点小于当前结点，选择当前结点的左子树插入
                node.left = insert(node.left, data);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (node.getBalance() == 2) {
                    if (data < node.left.data) {
                        node = leftLeftRotation(node);
                    } else {
                        node = leftRightRotation(node);
                    }
                }
            } else if (data > node.data)  {
                //新结点大于当前结点，选择当前结点的右子树插入
                node.right = insert(node.right, data);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (node.getBalance() == -2) {
                    if (data > node.right.data) {
                        node = rightRightRotation(node);
                    } else {
                        node = rightLeftRotation(node);
                    }
                }
            } else {
                System.out.println("AVL树中已有重复的结点！");
            }
        }
        //刷新结点的高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        return node;
    }

    //删除结点
    public void remove(int data) {
        TreeNode deletedNode;
        if ((deletedNode = search(root, data)) != null)
            root = remove(root, deletedNode);
    }

    //删除结点详细过程（递归）
    private TreeNode remove(TreeNode node, TreeNode deletedNode) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (node==null || deletedNode==null)
            return null;
        if (deletedNode.data < node.data){
            //待删除结点小于当前结点，在当前结点的左子树继续执行
            node.left = remove(node.left, deletedNode);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(node.right) - height(node.left) == 2) {
                TreeNode r =  node.right;
                if (height(r.left) > height(r.right))
                    node = rightLeftRotation(node);
                else
                    node = rightRightRotation(node);
            }
        } else  if (deletedNode.data > node.data) {
            //待删除结点大于当前结点，在当前结点的右子树继续执行
            node.right = remove(node.right, deletedNode);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(node.left) - height(node.right) == 2) {
                TreeNode l =  node.left;
                if (height(l.right) > height(l.left))
                    node = leftRightRotation(node);
                else
                    node = leftLeftRotation(node);
            }
        } else {
            // tree的左右孩子都非空
            if ((node.left!=null) && (node.right!=null)) {
                if (height(node.left) > height(node.right)) {
                    // 如果node的左子树比右子树高，找出左子树最大结点赋值给Node，并删除最小结点
                    TreeNode max = maximum(node.left);
                    node.data = max.data;
                    node.left = remove(node.left, max);
                } else {
                    // 如果node的右子树比左子树高，找出右子树最小结点赋值给Node，并删除最小结点
                    TreeNode min = minimum(node.right);
                    node.data = min.data;
                    node.right = remove(node.right, min);
                }
            } else {
                node = (node.left!=null) ? node.left : node.right;
            }
        }
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        return node;
    }

    //找出结点node为根的子树的最大节点
    private TreeNode maximum(TreeNode node) {
        if (node == null)
            return null;
        while(node.right != null)
            node = node.right;
        return node;
    }

    //找出结点node为根的子树的最小节点
    private TreeNode minimum(TreeNode node) {
        if (node == null)
            return null;
        while(node.left != null)
            node = node.left;
        return node;
    }

    //中序遍历
    public static void inOrderTraversal(TreeNode node) {
        if(node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data+" ");
            inOrderTraversal(node.right);
        }
    }

    //层序遍历
    public static void levelOrderTraversal(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.data+" ");
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

    class TreeNode {
        int data;
        int height;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
            this.height = 0;
        }

        //获得结点的平衡因子
        public int getBalance(){
            int left =  (this.left==null ? 0:this.left.height);
            int right = (this.right==null ? 0:this.right.height);
            return left - right;
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        int input[]= {5,3,7,2,4,6,9,1};
        for(int i=0; i<input.length; i++) {
            tree.insert(input[i]);
        }
        System.out.println("中序遍历: ");
        inOrderTraversal(tree.root);
        System.out.println();
        System.out.println("层序遍历: ");
        levelOrderTraversal(tree.root);
        System.out.println();
        System.out.printf("高度: %d\n", tree.height());
        int deletedData = 3;

        System.out.printf("删除根节点: %d\n", deletedData);
        tree.remove(deletedData);

        System.out.println("中序遍历: ");
        inOrderTraversal(tree.root);
        System.out.println();
        System.out.println("层序遍历: ");
        levelOrderTraversal(tree.root);
        System.out.println();
        System.out.printf("高度: %d\n", tree.height());
    }
}

红黑树

import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTree {
    TreeNode root;
    final static boolean RED = true;
    final static boolean BLACK = false;

    //查找结点
    public TreeNode search(int data) {
        TreeNode tmp = root;
        while (tmp != null) {
            if (tmp.data == data)
                return tmp;
            else if (tmp.data > data)
                tmp = tmp.left;
            else
                tmp = tmp.right;
        }
        return null;
    }

    //插入结点
    public boolean insert(int data) {
        TreeNode node = new TreeNode(data);
        //局面1：新结点位于树根，没有父结点。
        if (root == null) {
            root = node;
            node.color = BLACK;
            return true;
        }
        TreeNode targetNode = root;
        while (targetNode != null) {
            if( data == targetNode.data){
                System.out.println("红黑树中已有重复的结点：" + data);
                return false;
            } else if (data > targetNode.data) {
                if(targetNode.right == null){
                    targetNode.right = node;
                    node.parent = targetNode;
                    insertAdjust(node);
                    return true;
                }
                targetNode = targetNode.right;
            } else {
                if(targetNode.left == null){
                    targetNode.left = node;
                    node.parent = targetNode;
                    insertAdjust(node);
                    return true;
                }
                targetNode = targetNode.left;
            }
        }
        return true;
    }

    //插入后自我调整
    private void insertAdjust(TreeNode node) {
        //创建父结点和祖父结点指针
        TreeNode parent, grandParent;
        //局面3的调整有可能引发后续的一系列调整，所以使用while循环。
        while (node.parent != null && node.parent.color == RED) {
            parent = node.parent;
            grandParent = parent.parent;
            if (grandParent.left == parent) {
                TreeNode uncle = grandParent.right;
                //局面3：新结点的父结点和叔叔结点都是红色。
                if (uncle != null && uncle.color == RED) {
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;
                    continue;
                }
                //局面4：新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点是祖父结点的左孩子。
                if (node == parent.right) {
                    leftRotate(parent);
                    TreeNode tmp = node;
                    node = parent;
                    parent = tmp;
                }
                //局面5：新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点是祖父结点的左孩子。
                parent.color = BLACK;
                grandParent.color = RED;
                rightRotate(grandParent);
            } else {
                TreeNode uncle = grandParent.left;
                //局面3（镜像）：新结点的父结点和叔叔结点都是红色。
                if (uncle != null && uncle.color == RED) {
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;
                    continue;
                }
                //局面4（镜像）：新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点是祖父结点的右孩子。
                if (node == parent.left) {
                    rightRotate(parent);
                    TreeNode tmp = node;
                    node = parent;
                    parent = tmp;
                }
                //局面5（镜像）：新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点是祖父结点的右孩子。
                parent.color = BLACK;
                grandParent.color = RED;
                leftRotate(grandParent);
            }
        }
        //经过局面3的调整，有可能把根结点变为红色，此时再变回黑色即可。
        if(root.color == RED){
            root.color = BLACK;
        }
    }

    //删除节点
    public void remove(int key) {
        remove(search(key));
    }

    //删除节点详细逻辑
    private void remove(TreeNode node) {
        TreeNode targetNode = node;
        if (node == null)
            return;
        //第一步：如果待删除结点有两个非空的孩子结点，转化成待删除结点只有一个孩子（或没有孩子）的情况。
        if (node.left != null && node.right != null) {
            //待删除结点的后继结点
            TreeNode successNode = targetNode.right;
            while(successNode.left != null) {
                successNode = successNode.left;
            }
            if(targetNode == root) {
                root = successNode;
            }
            //把后继结点复制到待删除结点位置
            targetNode.data = successNode.data;
            remove(successNode);
            return;
        }
        //第二步：根据待删除结点和其唯一子结点的颜色，分情况处理。
        TreeNode successNode = node.left!= null ? node.left : node.right;
        TreeNode parent = node.parent;
        if (parent == null) {
            //子情况1，被删除结点是红黑树的根结点：
            root = successNode;
            if (successNode != null)
                successNode.parent = null;
        } else {
            if (successNode != null)
                successNode.parent = parent;
            if (parent.left == node)
                parent.left = successNode;
            else {
                parent.right = successNode;
            }
        }
        if (node.color == BLACK )
            //第三步：遇到双黑结点，在子结点顶替父结点之后，分成6种子情况处理。
            removeAdjust(parent, successNode);

    }

    //删除结点后的自我调整
    private void removeAdjust(TreeNode parent, TreeNode node) {
        while ((node == null || node.color == BLACK) && node != root) {
            if (parent.left == node) {
                //node的兄弟节点
                TreeNode sibling = parent.right;
                //子情况3，node的兄弟结点是红色：
                if (sibling != null && sibling.color == RED) {
                    parent.color = RED;
                    sibling.color = BLACK;
                    leftRotate(parent);
                    sibling = parent.right;
                }
                if (sibling == null || ((sibling.left == null || sibling.left.color == BLACK) && (sibling.right == null || sibling.right.color == BLACK))) {
                    //子情况2（镜像），node的父结点是黑色，兄弟和侄子结点是黑色：
                    if(parent.color == BLACK){
                        sibling.color = RED;
                        node = parent;
                        parent = node.parent;
                        continue;
                    }
                    //子情况4（镜像），node的父结点是红色，兄弟和侄子结点是黑色：
                    else {
                        sibling.color = RED;
                        break;
                    }
                }
                //子情况5，node的父结点随意，兄弟结点是黑色右孩子，左侄子结点是红色，右侄子结点是黑色：
                if (sibling.left == null || sibling.color == RED) {
                    sibling.left.color = BLACK;
                    sibling.color = RED;
                    rightRotate(sibling);
                    sibling = sibling.parent;
                }
                //子情况6，结点2的父结点随意，兄弟结点B是黑色右孩子，右侄子结点是红色：
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.right.color = BLACK;
                leftRotate(parent);
                node = root; //跳出循环
            } else {
                //node的兄弟节点
                TreeNode sibling = parent.left;
                //子情况3（镜像），node的兄弟结点是红色：
                if (sibling != null && sibling.color == RED) {
                    parent.color = RED;
                    sibling.color = BLACK;
                    rightRotate(parent);
                    sibling = parent.left;
                }
                if (sibling == null || ((sibling.left == null || sibling.left.color == BLACK) && (sibling.right == null || sibling.right.color == BLACK))) {
                    //子情况2（镜像），node的父结点是黑色，兄弟和侄子结点是黑色：
                    if(parent.color == BLACK){
                        sibling.color = RED;
                        node = parent;
                        parent = node.parent;
                        continue;
                    }
                    //子情况4（镜像），node的父结点是红色，兄弟和侄子结点是黑色：
                    else {
                        sibling.color = RED;
                        break;
                    }
                }
                //子情况5（镜像），node的父结点随意，兄弟结点是黑色左孩子，右侄子结点是红色，左侄子结点是黑色：
                if (sibling.right == null || sibling.right.color == RED) {
                    sibling.right.color = BLACK;
                    sibling.color = RED;
                    leftRotate(sibling);
                    sibling = sibling.parent;
                }
                //子情况6（镜像），结点2的父结点随意，兄弟结点是黑色左孩子，左侄子结点是红色：
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.left.color = BLACK;
                rightRotate(parent);
                node = root; //跳出循环
            }
        }
        if (node != null) {
            node.color = BLACK;
        }
    }

    //左旋转
    private void leftRotate(TreeNode node) {
        TreeNode right = node.right;
        TreeNode parent = node.parent;
        if (parent == null) {
            root = right;
            right.parent = null;
        } else {
            if (parent.left != null && parent.left == node) {
                parent.left = right;
            } else {
                parent.right = right;
            }
            right.parent = parent;
        }
        node.parent = right;
        node.right = right.left;
        if (right.left != null) {
            right.left.parent = node;
        }
        right.left = node;
    }

    //右旋转
    private void rightRotate(TreeNode node) {
        TreeNode left = node.left;
        TreeNode parent = node.parent;
        if (parent == null) {
            root = left;
            left.parent = null;
        } else {
            if (parent.left != null && parent.left == node) {
                parent.left = left;
            } else {
                parent.right = left;
            }
            left.parent = parent;
        }
        node.parent = left;
        node.left = left.right;
        if (left.right != null) {
            left.right.parent = node;
        }
        left.right = node;
    }

    //中序遍历
    public static void inOrderTraversal(TreeNode node) {
        if(node != null) {
            inOrderTraversal(node.left);
            System.out.print(node);
            inOrderTraversal(node.right);
        }
    }

    //层序遍历
    public static void levelOrderTraversal(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

    class TreeNode {
        int data;
        boolean color;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        public TreeNode(int data) {
            this.data = data;
            this.color = RED;
        }

        @Override
        public String toString() {
            return  data + (color?"(red)":"(black)") + "  " ;
        }
    }

    public static void main(String[] args) {
        RedBlackTree rbTree = new RedBlackTree();
        int input[]= {13,8,17,1,11,15,25,6,22,27};
        for(int i=0; i<input.length; i++) {
            rbTree.insert(input[i]);
        }
        rbTree.remove(8);
        System.out.println("中序遍历: ");
        inOrderTraversal(rbTree.root);
        System.out.println();
        System.out.println("层序遍历: ");
        levelOrderTraversal(rbTree.root);
        System.out.println();
    }
}

这篇关于《漫画算法2》源码整理-1 二分查找树 AVL树红黑树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

《漫画算法2》源码整理-1 二分查找树 AVL树红黑树

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

《漫画算法2》源码整理-1 二分查找树 AVL树 红黑树

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

《漫画算法2》源码整理-1 二分查找树 AVL树红黑树