Java Treap树
lolxxs 人气:0Treap树
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;
}
}加载全部内容