Treap樹的節(jié)點除了有二叉搜索樹的必須有的值，還有一個隨機生成的優(yōu)先級priority，供構(gòu)造小頂堆使用，小頂堆的特性就是父節(jié)點、左右子結(jié)點中永遠是父節(jié)點的優(yōu)先級最小，最多和子結(jié)點的相等。而大頂堆則是父節(jié)點的最大。堆中左右子結(jié)點的優(yōu)先級并沒有特定要求

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

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

遍歷

Treap樹雖然是不完全平衡樹，但是其完全滿足二叉搜索樹的特征，即中序遍歷得到的是有序數(shù)組

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

查詢

Treap樹滿足二叉搜索樹的特征，則直接根據(jù)其特征查詢

// 查詢
// 根據(jù)二叉搜索樹性質(zhì)查詢
public TreeNode query(TreeNode root, int value) {
    //這里的root才是真root，上面的方法只是局部變量
    //所以不能在查詢中改變根節(jié)點
    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;
}

增加

步驟

按照二叉搜索樹的插入方式，將節(jié)點插入到葉子節(jié)點，如果在查找的過程找到要插入的值，則不會進行插入，具有去重效果
插入節(jié)點后，根據(jù)隨機生成的priority優(yōu)先級，按照小頂堆，即priority較小的成為父節(jié)點，來進行左旋右旋

//增加
// ?1.按照二叉查找樹的插入方式，將節(jié)點插入到樹葉中
// ?2.再根據(jù)priority優(yōu)先級的小頂堆性質(zhì)進行左旋右旋
public TreeNode insert(int value, TreeNode root) {
? ? ?// 如果父節(jié)點為空，則創(chuàng)建一個父節(jié)點并返回
? ? ?// 第一次父節(jié)點為根節(jié)點
? ? ?if (root == null) {
? ? ? ? ?return new TreeNode(value, random.nextInt());
? ? ?}

? ? ?// 如果要根節(jié)點的值大于要插入結(jié)點的值，則應(yīng)該插入到根節(jié)點的左邊
? ? ?if (root.value > value) {
? ? ? ? ?// 遞歸進行插入，一直遞歸到葉子節(jié)點才會插入
? ? ? ? ?// 如果遞歸到一個相等的節(jié)點，則不會創(chuàng)建一個新節(jié)點，會直接返回
? ? ? ? ?root.left = insert(value, root.left);

? ? ? ? ?// 插入完成后，根據(jù)堆的優(yōu)先級進行旋轉(zhuǎn)操作
? ? ? ? ?// 左子結(jié)點的優(yōu)先級值小于根結(jié)點的優(yōu)先級，
? ? ? ? ?// 根據(jù)小頂堆的規(guī)則，需要進行右旋操作
? ? ? ? ?if (root.left.priority < root.priority) {
? ? ? ? ? ? ?// 傳入root根結(jié)點，返回的是左子結(jié)點，
? ? ? ? ? ? ?// 但此時左子結(jié)點已經(jīng)旋轉(zhuǎn)成為根結(jié)點所以賦值給根結(jié)點
? ? ? ? ? ? ?root = rightRotate(root);
? ? ? ? ?}
? ? ?}
? ? ?// 如果根節(jié)點的值小于要插入結(jié)點的值大于，則應(yīng)該插入到根節(jié)點的右邊
? ? ?else if (root.value < value) {
? ? ? ? ?// 遞歸插入
? ? ? ? ?root.right = insert(value, root.right);
? ? ? ? ?// 右子結(jié)點的優(yōu)先級值小于根結(jié)點的優(yōu)先級，
? ? ? ? ?// 根據(jù)小頂堆的規(guī)則，需要進行左旋操作
? ? ? ? ?if (root.right.priority < root.priority) {
? ? ? ? ? ? ?root = leftRotate(root);
? ? ? ? ?}
? ? ?}
? ? ?// 如果已經(jīng)有該值，則無須插入，什么都不動
? ? ?else {

? ? ?}
? ? ?// 返回根結(jié)點
? ? ?return root;
?}

刪除

步驟

按照二叉搜索樹的特點，先找到對應(yīng)的節(jié)點
若該結(jié)點為葉子結(jié)點，則直接刪除，若該結(jié)點為非葉子節(jié)點，則進行相應(yīng)的旋轉(zhuǎn)，直到該結(jié)點為葉子節(jié)點，然后進行刪除

?//刪除、
// ? ? 1.根據(jù)二叉搜索樹的性質(zhì)找到相應(yīng)的結(jié)點
// ? ? 2.若該結(jié)點為葉子結(jié)點，則直接刪除，若該結(jié)點為非葉子節(jié)點，
// ? ? ? 則進行相應(yīng)的旋轉(zhuǎn)，直到該結(jié)點為葉子節(jié)點，然后進行刪除。
public TreeNode delete(int value, TreeNode root) {
? ? // 當(dāng)樹不為空才進行刪除
? ? if (root != null) {
? ? ? ? // 先進行查找
? ? ? ? // 往左找
? ? ? ? if (root.value > value) {
? ? ? ? ? ? // 因為可能找到了后會進行左旋右旋，
? ? ? ? ? ? // 所以其實左子結(jié)點會改變
? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? }
? ? ? ? // 往右找
? ? ? ? else if (root.value < value) {
? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? }
? ? ? ? //找到了
? ? ? ? else {
? ? ? ? ? ? // 首先找到這里，root已經(jīng)變?yōu)槟繕?biāo)結(jié)點，如果root是葉子結(jié)點刪去即可
? ? ? ? ? ? if (root.left == null && root.right == null) {
? ? ? ? ? ? ? ? // 返回當(dāng)前節(jié)點，即刪除后的樣子 null
? ? ? ? ? ? ? ? // 會遞歸到其父節(jié)點的root.right = delete(value, root.right);
? ? ? ? ? ? ? ? // 即指向了root.right = null 或 root.left = null，即刪除了我們要刪除的節(jié)點
? ? ? ? ? ? ? ? return null;
? ? ? ? ? ? } else if (root.left != null && root.right != null) {
? ? ? ? ? ? ? ? // 如果root左右子結(jié)點健在
? ? ? ? ? ? ? ? // 此時就是想把目標(biāo)結(jié)點旋轉(zhuǎn)到底層去，
? ? ? ? ? ? ? ? // 然后需要選擇一個優(yōu)先級值比較小的結(jié)點放在目標(biāo)結(jié)點位置
? ? ? ? ? ? ? ? // 如果左子結(jié)點優(yōu)先級較小
? ? ? ? ? ? ? ? if (root.left.priority < root.right. priority) {
? ? ? ? ? ? ? ? ? ? // 旋轉(zhuǎn)root已經(jīng)變?yōu)樽笞咏Y(jié)點，原來的根結(jié)點變?yōu)橛易庸?jié)點
? ? ? ? ? ? ? ? ? ? root = rightRotate(root);
? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? root = leftRotate(root);
? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ?else if (root.left != null) {
? ? ? ? ? ? ? ? // 沒有右子節(jié)點，只能右旋了
? ? ? ? ? ? ? ? root = rightRotate(root);
? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? ? ? }

? ? ? ? ? ? else if (root.right != null) {
? ? ? ? ? ? ? ? // 沒有左子節(jié)點，只能左旋了
? ? ? ? ? ? ? ? root = leftRotate(root);
? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? return root;
}

完整代碼

public class Treap {
? ? // 優(yōu)先級隨機數(shù)發(fā)生器
? ? private static final Random random = new Random();

? ? //增加
// ?1.按照二叉查找樹的插入方式，將節(jié)點插入到樹葉中
// ?2.再根據(jù)priority優(yōu)先級的小頂堆性質(zhì)進行左旋右旋
? ? public TreeNode insert(int value, TreeNode root) {
? ? ? ? // 如果父節(jié)點為空，則創(chuàng)建一個父節(jié)點并返回
? ? ? ? // 第一次父節(jié)點為根節(jié)點
? ? ? ? if (root == null) {
? ? ? ? ? ? return new TreeNode(value, random.nextInt());
? ? ? ? }

? ? ? ? // 如果要根節(jié)點的值大于要插入結(jié)點的值，則應(yīng)該插入到根節(jié)點的左邊
? ? ? ? if (root.value > value) {
? ? ? ? ? ? // 遞歸進行插入，一直遞歸到葉子節(jié)點才會插入
? ? ? ? ? ? // 如果遞歸到一個相等的節(jié)點，則不會創(chuàng)建一個新節(jié)點，會直接返回
? ? ? ? ? ? root.left = insert(value, root.left);

? ? ? ? ? ? // 插入完成后，根據(jù)堆的優(yōu)先級進行旋轉(zhuǎn)操作
? ? ? ? ? ? // 左子結(jié)點的優(yōu)先級值小于根結(jié)點的優(yōu)先級，
? ? ? ? ? ? // 根據(jù)小頂堆的規(guī)則，需要進行右旋操作
? ? ? ? ? ? if (root.left.priority < root.priority) {
? ? ? ? ? ? ? ? // 傳入root根結(jié)點，返回的是左子結(jié)點，
? ? ? ? ? ? ? ? // 但此時左子結(jié)點已經(jīng)旋轉(zhuǎn)成為根結(jié)點所以賦值給根結(jié)點
? ? ? ? ? ? ? ? root = rightRotate(root);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 如果根節(jié)點的值小于要插入結(jié)點的值大于，則應(yīng)該插入到根節(jié)點的右邊
? ? ? ? else if (root.value < value) {
? ? ? ? ? ? // 遞歸插入
? ? ? ? ? ? root.right = insert(value, root.right);
? ? ? ? ? ? // 右子結(jié)點的優(yōu)先級值小于根結(jié)點的優(yōu)先級，
? ? ? ? ? ? // 根據(jù)小頂堆的規(guī)則，需要進行左旋操作
? ? ? ? ? ? if (root.right.priority < root.priority) {
? ? ? ? ? ? ? ? root = leftRotate(root);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 如果已經(jīng)有該值，則無須插入，什么都不動
? ? ? ? else {

? ? ? ? }
? ? ? ? // 返回根結(jié)點
? ? ? ? return root;
? ? }

? ? //刪除、
// ? ? 1.根據(jù)二叉搜索樹的性質(zhì)找到相應(yīng)的結(jié)點
// ? ? 2.若該結(jié)點為葉子結(jié)點，則直接刪除，若該結(jié)點為非葉子節(jié)點，
// ? ? ? 則進行相應(yīng)的旋轉(zhuǎn)，直到該結(jié)點為葉子節(jié)點，然后進行刪除。
? ? public TreeNode delete(int value, TreeNode root) {
? ? ? ? // 當(dāng)樹不為空才進行刪除
? ? ? ? if (root != null) {
? ? ? ? ? ? // 先進行查找
? ? ? ? ? ? // 往左找
? ? ? ? ? ? if (root.value > value) {
? ? ? ? ? ? ? ? // 因為可能找到了后會進行左旋右旋，
? ? ? ? ? ? ? ? // 所以其實左子結(jié)點會改變
? ? ? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? ? ? }
? ? ? ? ? ? // 往右找
? ? ? ? ? ? else if (root.value < value) {
? ? ? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? ? ? }
? ? ? ? ? ? //找到了
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? // 首先找到這里，root已經(jīng)變?yōu)槟繕?biāo)結(jié)點，如果root是葉子結(jié)點刪去即可
? ? ? ? ? ? ? ? if (root.left == null && root.right == null) {
? ? ? ? ? ? ? ? ? ? // 返回當(dāng)前節(jié)點，即刪除后的樣子 null
? ? ? ? ? ? ? ? ? ? // 會遞歸到其父節(jié)點的root.right = delete(value, root.right);
? ? ? ? ? ? ? ? ? ? // 即指向了root.right = null 或 root.left = null，即刪除了我們要刪除的節(jié)點
? ? ? ? ? ? ? ? ? ? return null;
? ? ? ? ? ? ? ? } else if (root.left != null && root.right != null) {
? ? ? ? ? ? ? ? ? ? // 如果root左右子結(jié)點健在
? ? ? ? ? ? ? ? ? ? // 此時就是想把目標(biāo)結(jié)點旋轉(zhuǎn)到底層去，
? ? ? ? ? ? ? ? ? ? // 然后需要選擇一個優(yōu)先級值比較小的結(jié)點放在目標(biāo)結(jié)點位置
? ? ? ? ? ? ? ? ? ? // 如果左子結(jié)點優(yōu)先級較小
? ? ? ? ? ? ? ? ? ? if (root.left.priority < root.right. priority) {
? ? ? ? ? ? ? ? ? ? ? ? // 旋轉(zhuǎn)root已經(jīng)變?yōu)樽笞咏Y(jié)點，原來的根結(jié)點變?yōu)橛易庸?jié)點
? ? ? ? ? ? ? ? ? ? ? ? root = rightRotate(root);
? ? ? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? root = leftRotate(root);
? ? ? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?else if (root.left != null) {
? ? ? ? ? ? ? ? ? ? // 沒有右子節(jié)點，只能右旋了
? ? ? ? ? ? ? ? ? ? root = rightRotate(root);
? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? root.right = delete(value, root.right);
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? else if (root.right != null) {
? ? ? ? ? ? ? ? ? ? // 沒有左子節(jié)點，只能左旋了
? ? ? ? ? ? ? ? ? ? root = leftRotate(root);
? ? ? ? ? ? ? ? ? ? // 去找那被換下去的節(jié)點，將它刪除掉
? ? ? ? ? ? ? ? ? ? root.left = delete(value, root.left);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? return root;
? ? }

? ? // 查詢
? ? // 根據(jù)二叉搜索樹性質(zhì)查詢
? ? public TreeNode query(TreeNode root, int value) {
? ? ? ? //這里的root才是真root，上面的方法只是局部變量
? ? ? ? //所以不能在查詢中改變根節(jié)點
? ? ? ? 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;
? ? }

? ? // 右旋，左子節(jié)點右旋
? ? public TreeNode rightRotate(TreeNode treeNode) {
? ? ? ? // temp為左子結(jié)點
? ? ? ? TreeNode temp = treeNode.left;
? ? ? ? //將父結(jié)點的左邊指向 temp的右子結(jié)點
? ? ? ? treeNode.left = temp.right;
? ? ? ? // 將temp結(jié)點的右邊指向父結(jié)點
? ? ? ? temp.right = treeNode;
? ? ? ? // 進行上面兩步操作，在紙上畫一下就找到其右旋成功了，
? ? ? ? // 即左子結(jié)點變?yōu)楦Y(jié)點了

? ? ? ? // 返回此時旋轉(zhuǎn)后的真正根結(jié)點
? ? ? ? return temp;
? ? }

? ? // 左旋，右子結(jié)點左旋
? ? public TreeNode leftRotate(TreeNode treeNode) {
? ? ? ? // temp為右子結(jié)點
? ? ? ? TreeNode temp = treeNode.right;
? ? ? ? //將父結(jié)點的右邊指向 temp的左子結(jié)點
? ? ? ? treeNode.right = temp.left;
? ? ? ? // 將temp結(jié)點的左邊指向父結(jié)點
? ? ? ? temp.left = treeNode;
? ? ? ? // 進行上面兩步操作，在紙上畫一下就找到其左旋成功了，
? ? ? ? // 即右子結(jié)點變?yōu)楦Y(jié)點了

? ? ? ? // 返回此時旋轉(zhuǎn)后的真正根結(jié)點
? ? ? ? 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;
? ? }
}

到此這篇關(guān)于Java實現(xiàn)Treap樹的示例代碼的文章就介紹到這了,更多相關(guān)Java Treap樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: