Java Treap树

软件发布|下载排行|最新软件

当前位置：首页 → IT学院 → IT技术 →

Java Treap树

lolxxs   2022-09-08 我要评论

Treap树

Treap树是平衡二叉搜索树的一种实现方式，但它不是完全平衡的。平衡二叉搜索树的实现方式还有AVL树、红黑树、替罪羊树、伸展树

数据结构

Treap树的节点除了有二叉搜索树的必须有的值，还有一个随机生成的优先级priority，供构造小顶堆使用，小顶堆的特性就是父节点、左右子结点中永远是父节点的优先级最小，最多和子结点的相等。而大顶堆则是父节点的最大。堆中左右子结点的优先级并没有特定要求

class TreeNode {
    int value;
    int priority;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value, int priority) {
        this.value = value;
        this.priority = priority;
    }
}

遍历

Treap树虽然是不完全平衡树，但是其完全满足二叉搜索树的特征，即中序遍历得到的是有序数组

public void printTree(TreeNode root) {
   if (root != null) {
        printTree(root.left);
        System.out.println(root.value);
        printTree(root.right);
    }
}

查询

Treap树满足二叉搜索树的特征，则直接根据其特征查询

// 查询
// 根据二叉搜索树性质查询
public TreeNode query(TreeNode root, int value) {
    //这里的root才是真root，上面的方法只是局部变量
    //所以不能在查询中改变根节点
    TreeNode temp = root;
    while (temp != null) {
        if (temp.value > value) {
            temp = temp.left;
        } else if (temp.value < value) {
            temp = temp.right;
        } else {
            return temp;
        }
    }
    return null;
}

增加

步骤

  • 按照二叉搜索树的插入方式，将节点插入到叶子节点，如果在查找的过程找到要插入的值，则不会进行插入，具有去重效果
  • 插入节点后，根据随机生成的priority优先级，按照小顶堆，即priority较小的成为父节点，来进行左旋右旋
//增加
//  1.按照二叉查找树的插入方式，将节点插入到树叶中
//  2.再根据priority优先级的小顶堆性质进行左旋右旋
public TreeNode insert(int value, TreeNode root) {
     // 如果父节点为空，则创建一个父节点并返回
     // 第一次父节点为根节点
     if (root == null) {
         return new TreeNode(value, random.nextInt());
     }

     // 如果要根节点的值大于要插入结点的值，则应该插入到根节点的左边
     if (root.value > value) {
         // 递归进行插入，一直递归到叶子节点才会插入
         // 如果递归到一个相等的节点，则不会创建一个新节点，会直接返回
         root.left = insert(value, root.left);

         // 插入完成后，根据堆的优先级进行旋转操作
         // 左子结点的优先级值小于根结点的优先级，
         // 根据小顶堆的规则，需要进行右旋操作
         if (root.left.priority < root.priority) {
             // 传入root根结点，返回的是左子结点，
             // 但此时左子结点已经旋转成为根结点所以赋值给根结点
             root = rightRotate(root);
         }
     }
     // 如果根节点的值小于要插入结点的值大于，则应该插入到根节点的右边
     else if (root.value < value) {
         // 递归插入
         root.right = insert(value, root.right);
         // 右子结点的优先级值小于根结点的优先级，
         // 根据小顶堆的规则，需要进行左旋操作
         if (root.right.priority < root.priority) {
             root = leftRotate(root);
         }
     }
     // 如果已经有该值，则无须插入，什么都不动
     else {

     }
     // 返回根结点
     return root;
 }

删除

步骤

  • 按照二叉搜索树的特点，先找到对应的节点
  • 若该结点为叶子结点，则直接删除，若该结点为非叶子节点， 则进行相应的旋转，直到该结点为叶子节点，然后进行删除
 //删除、
//     1.根据二叉搜索树的性质找到相应的结点
//     2.若该结点为叶子结点，则直接删除，若该结点为非叶子节点，
//       则进行相应的旋转，直到该结点为叶子节点，然后进行删除。
public TreeNode delete(int value, TreeNode root) {
    // 当树不为空才进行删除
    if (root != null) {
        // 先进行查找
        // 往左找
        if (root.value > value) {
            // 因为可能找到了后会进行左旋右旋，
            // 所以其实左子结点会改变
            root.left = delete(value, root.left);
        }
        // 往右找
        else if (root.value < value) {
            root.right = delete(value, root.right);
        }
        //找到了
        else {
            // 首先找到这里，root已经变为目标结点，如果root是叶子结点删去即可
            if (root.left == null && root.right == null) {
                // 返回当前节点，即删除后的样子 null
                // 会递归到其父节点的root.right = delete(value, root.right);
                // 即指向了root.right = null 或 root.left = null，即删除了我们要删除的节点
                return null;
            } else if (root.left != null && root.right != null) {
                // 如果root左右子结点健在
                // 此时就是想把目标结点旋转到底层去，
                // 然后需要选择一个优先级值比较小的结点放在目标结点位置
                // 如果左子结点优先级较小
                if (root.left.priority < root.right. priority) {
                    // 旋转root已经变为左子结点，原来的根结点变为右子节点
                    root = rightRotate(root);
                    // 去找那被换下去的节点，将它删除掉
                    root.right = delete(value, root.right);
                } else {
                    root = leftRotate(root);
                    // 去找那被换下去的节点，将它删除掉
                    root.left = delete(value, root.left);
                }
            }
           else if (root.left != null) {
                // 没有右子节点，只能右旋了
                root = rightRotate(root);
                // 去找那被换下去的节点，将它删除掉
                root.right = delete(value, root.right);
            }

            else if (root.right != null) {
                // 没有左子节点，只能左旋了
                root = leftRotate(root);
                // 去找那被换下去的节点，将它删除掉
                root.left = delete(value, root.left);
            }
        }
    }

    return root;
}

完整代码

public class Treap {
    // 优先级随机数发生器
    private static final Random random = new Random();

    //增加
//  1.按照二叉查找树的插入方式，将节点插入到树叶中
//  2.再根据priority优先级的小顶堆性质进行左旋右旋
    public TreeNode insert(int value, TreeNode root) {
        // 如果父节点为空，则创建一个父节点并返回
        // 第一次父节点为根节点
        if (root == null) {
            return new TreeNode(value, random.nextInt());
        }

        // 如果要根节点的值大于要插入结点的值，则应该插入到根节点的左边
        if (root.value > value) {
            // 递归进行插入，一直递归到叶子节点才会插入
            // 如果递归到一个相等的节点，则不会创建一个新节点，会直接返回
            root.left = insert(value, root.left);

            // 插入完成后，根据堆的优先级进行旋转操作
            // 左子结点的优先级值小于根结点的优先级，
            // 根据小顶堆的规则，需要进行右旋操作
            if (root.left.priority < root.priority) {
                // 传入root根结点，返回的是左子结点，
                // 但此时左子结点已经旋转成为根结点所以赋值给根结点
                root = rightRotate(root);
            }
        }
        // 如果根节点的值小于要插入结点的值大于，则应该插入到根节点的右边
        else if (root.value < value) {
            // 递归插入
            root.right = insert(value, root.right);
            // 右子结点的优先级值小于根结点的优先级，
            // 根据小顶堆的规则，需要进行左旋操作
            if (root.right.priority < root.priority) {
                root = leftRotate(root);
            }
        }
        // 如果已经有该值，则无须插入，什么都不动
        else {

        }
        // 返回根结点
        return root;
    }

    //删除、
//     1.根据二叉搜索树的性质找到相应的结点
//     2.若该结点为叶子结点，则直接删除，若该结点为非叶子节点，
//       则进行相应的旋转，直到该结点为叶子节点，然后进行删除。
    public TreeNode delete(int value, TreeNode root) {
        // 当树不为空才进行删除
        if (root != null) {
            // 先进行查找
            // 往左找
            if (root.value > value) {
                // 因为可能找到了后会进行左旋右旋，
                // 所以其实左子结点会改变
                root.left = delete(value, root.left);
            }
            // 往右找
            else if (root.value < value) {
                root.right = delete(value, root.right);
            }
            //找到了
            else {
                // 首先找到这里，root已经变为目标结点，如果root是叶子结点删去即可
                if (root.left == null && root.right == null) {
                    // 返回当前节点，即删除后的样子 null
                    // 会递归到其父节点的root.right = delete(value, root.right);
                    // 即指向了root.right = null 或 root.left = null，即删除了我们要删除的节点
                    return null;
                } else if (root.left != null && root.right != null) {
                    // 如果root左右子结点健在
                    // 此时就是想把目标结点旋转到底层去，
                    // 然后需要选择一个优先级值比较小的结点放在目标结点位置
                    // 如果左子结点优先级较小
                    if (root.left.priority < root.right. priority) {
                        // 旋转root已经变为左子结点，原来的根结点变为右子节点
                        root = rightRotate(root);
                        // 去找那被换下去的节点，将它删除掉
                        root.right = delete(value, root.right);
                    } else {
                        root = leftRotate(root);
                        // 去找那被换下去的节点，将它删除掉
                        root.left = delete(value, root.left);
                    }
                }
               else if (root.left != null) {
                    // 没有右子节点，只能右旋了
                    root = rightRotate(root);
                    // 去找那被换下去的节点，将它删除掉
                    root.right = delete(value, root.right);
                }

                else if (root.right != null) {
                    // 没有左子节点，只能左旋了
                    root = leftRotate(root);
                    // 去找那被换下去的节点，将它删除掉
                    root.left = delete(value, root.left);
                }
            }
        }

        return root;
    }

    // 查询
    // 根据二叉搜索树性质查询
    public TreeNode query(TreeNode root, int value) {
        //这里的root才是真root，上面的方法只是局部变量
        //所以不能在查询中改变根节点
        TreeNode temp = root;
        while (temp != null) {
            if (temp.value > value) {
                temp = temp.left;
            } else if (temp.value < value) {
                temp = temp.right;
            } else {
                return temp;
            }
        }
        return null;
    }

    // 右旋，左子节点右旋
    public TreeNode rightRotate(TreeNode treeNode) {
        // temp为左子结点
        TreeNode temp = treeNode.left;
        //将父结点的左边指向 temp的右子结点
        treeNode.left = temp.right;
        // 将temp结点的右边指向父结点
        temp.right = treeNode;
        // 进行上面两步操作，在纸上画一下就找到其右旋成功了，
        // 即左子结点变为根结点了

        // 返回此时旋转后的真正根结点
        return temp;
    }

    // 左旋，右子结点左旋
    public TreeNode leftRotate(TreeNode treeNode) {
        // temp为右子结点
        TreeNode temp = treeNode.right;
        //将父结点的右边指向 temp的左子结点
        treeNode.right = temp.left;
        // 将temp结点的左边指向父结点
        temp.left = treeNode;
        // 进行上面两步操作，在纸上画一下就找到其左旋成功了，
        // 即右子结点变为根结点了

        // 返回此时旋转后的真正根结点
        return temp;
    }

    public void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.println(root.value);
            printTree(root.right);
        }
    }

    public static void main(String[] args) {
        Treap treap = new Treap();
        TreeNode root = null;
        root = treap.insert(1, root);
        root = treap.insert(2, root);
        root = treap.insert(3, root);
        root = treap.insert(4, root);
        root = treap.insert(5, root);
        root = treap.insert(6, root);

        //中序遍历，如果打印的值由小到大，说明满足二叉搜索树特征
        treap.printTree(root);

        System.out.println();

        // 测试查询
        TreeNode query = treap.query(root, 1);
        System.out.println(query.value);
        query = treap.query(root, 2);
        System.out.println(query.value);
        query = treap.query(root, 3);
        System.out.println(query.value);
        query = treap.query(root, 4);
        System.out.println(query.value);
        query = treap.query(root, 5);
        System.out.println(query.value);
        query = treap.query(root, 6);
        System.out.println(query.value);
        query = treap.query(root, 7);
        System.out.println(query);

        System.out.println();
        // 测试删除
        root = treap.delete(2,root);
        root = treap.delete(3,root);
        root = treap.delete(5,root);
        root = treap.delete(7,root);
        treap.printTree(root);

    }
}


class TreeNode {
    int value;
    int priority;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value, int priority) {
        this.value = value;
        this.priority = priority;
    }
}

相关文章

猜您喜欢

今日热门

Copyright 2022 版权所有 软件发布 访问手机版

声明：所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们