Splay Tree

xiaoxiao2021-03-01  2

Splay Tree 是二叉查找树的一种,它与平衡二叉树、红黑树不同的是,Splay Tree从不强制地保持自身的平衡,每当查找到某个节点n的时候,在返回节点n的同时,Splay Tree会将节点n旋转到树根的位置,这样就使得Splay Tree天生有着一种类似缓存的能力,因为每次被查找到的节点都会被搬到树根的位置,所以当80%的情况下我们需要查找的元素都是某个固定的节点,或者是一部分特定的节点时,那么在很多时候,查找的效率会是O(1)的效率!当然如果查找的节点是很均匀地分布在不同的地方时,Splay Tree的性能就会变得很差了,但Splay Tree的期望的时间复杂度还是O(nlogn)的。

 

这里先介绍一下左旋(zag)和右旋(zig)的操作

然后就是Splay Tree进行Splay操作的具体步骤,主要分两种情况:

先看图中的左边,查找到的x节点的父节点是y,x是y的左子树,y的父节点z是根节点,y也是z的左子树,要把x旋转到根节点的位置,就要进行zig(y),然后再进行zig(x)操作

再看图中的右边,查找到的z节点的父节点是y,z是y的右子树,y的父节点x是根节点,y也是x的右子树,要把z旋转到根节点的位置,就要进行zag(y),然后进行zag(x)操作

若是途中的情况,若需要把x移动到根节点,则需要先进行zig(x),然后再进行zag(x)操作

还有一种y是z的左子树,x是y的右子树的情况,这时就需要先进行zag(x),然后再进行zig(x)操作了

下面就给出我自己写的Java版的Splay Tree的一种实现(为了方便,自己定义了类似于Map的接口,仅供参考):

Splay Tree Node

public class SplayTreeNode implements Serializable { private static final long serialVersionUID = 72651428543015658L; protected int key; protected Object value; protected SplayTreeNode father; protected SplayTreeNode leftChild; protected SplayTreeNode rightyChild; // get, set 方法 }

 Splay Tree 的接口

public interface SplayTree {     /**      * 添加/更新node结点      * @param node      * @return      */     public void put(SplayTreeNode node);     /**      * 根据key获取对应的node结点,若该结点不存在,则返回null      * @param key      * @return      */     public SplayTreeNode get(int key);     /**      * 根据key删除对应的node结点,若该结点不存在,则什么都不做      * @param key      */     public void remove(int key);          /**      * 返回SplayTree中结点的个数      * @return      */     public int size();          /**      * 显示SplayTree的树形结构      */     public void showTree(); /** * 显示SplayTree各个结点的详细信息 */ public void showDetail();

 Splay Tree 的实现

public class DefaultSplayTree implements SplayTree, Serializable {     private static final long serialVersionUID = 4967206515246041054L;          protected int size;     protected SplayTreeNode root;          public DefaultSplayTree() {         this.size = 0;         this.root = null;     }          /* (non-Javadoc)      * @see SplayTree#get(int)      */     @Override     public SplayTreeNode get(int key) {                SplayTreeNode currentNode = this.root;         while (true) {             // 找不到对应的结点,返回null             if (currentNode == null) {                 return null;             }                          // 当前结点就是要找的结点             if (key == currentNode.getKey()) {                 this.splay(currentNode);                 return currentNode;             // key比当前结点的key要小             } else if (key < currentNode.getKey()) {                 currentNode = currentNode.getLeftChild();             // key比当前结点的key要大             } else {                 currentNode = currentNode.getRightyChild();             }         }     }     /* (non-Javadoc)      * @see SplayTree#put(SplayTreeNode)      */     @Override     public void put(SplayTreeNode node) {         if (node == null) {             return;         }                  // 当前的splay树为空         if (this.root == null) {             this.root = node;             this.size ++;             return;         }                  // 当前结点         SplayTreeNode currentNode = this.root;         // 当前结点的父结点         SplayTreeNode currentNodeFather = null;         // 当前结点是否是父结点的左子树         boolean isLeft = false;;         while (true) {             // 当前结点为null,则此位置为添加结点的插入位置             if (currentNode == null) {                 node.setFather(currentNodeFather);                 if (isLeft) {                     currentNodeFather.setLeftChild(node);                 } else {                     currentNodeFather.setRightyChild(node);                 }                 this.size ++;                 this.splay(node);                 return;             }                                // 若当前结点的key比添加的结点的key要小,则在当前结点的左子树中查找             if (node.getKey() < currentNode.getKey()) {                 currentNodeFather = currentNode;                 isLeft = true;                 currentNode = currentNode.getLeftChild();                              // 若当前结点的key比添加的结点的key要大,则在当前结点的右子树中查找             } else if (node.getKey() > currentNode.getKey()) {                 currentNodeFather = currentNode;                 isLeft = false;                 currentNode = currentNode.getRightyChild();                          // 当前结点的key和要添加的结点的key相等,则更新该结点             } else {                 currentNode.setValue(node.getValue());                 node = currentNode;                 this.splay(node);                 return;             }         }      }     /* (non-Javadoc)      * @see SplayTree#remove(int)      */     @Override     public void remove(int key) {         SplayTreeNode node = this.get(key);         if (node != null) {             this.join(node.getLeftChild(), node.getRightyChild());             this.size --;         }     }          /**      * 对node结点进行右旋      * @param node      */     protected void zig(SplayTreeNode node) {         // 获取旋转结点的父结点         SplayTreeNode father = node.getFather();                  // 将旋转结点的右子树设为父结点的左子树         father.setLeftChild(node.getRightyChild());         // 若旋转结点的右子树不为空,则将父结点设为右子树的父结点         if (node.getRightyChild() != null) {             node.getRightyChild().setFather(father);         }                       // 将父结点的父结点(爷爷结点)设为旋转结点的父结点         node.setFather(father.getFather());         // 若爷爷结点不为空         if (father.getFather() != null) {             // 若父结点为爷爷结点的左子树,则将旋转结点设为爷爷结点的左子树             if (father == father.getFather().getLeftChild()) {                 father.getFather().setLeftChild(node);                              // 若父结点为爷爷结点的右子树,则将旋转结点设为爷爷结点的右子树             } else {                 father.getFather().setRightyChild(node);             }         }                   // 将父结点设为旋转结点的右子树         node.setRightyChild(father);         // 更新父结点的父结点为旋转结点         father.setFather(node);     }          /**      * 对node结点进行左旋      * @param node      */     protected void zag(SplayTreeNode node) {         // 获取旋转结点的父结点         SplayTreeNode father = node.getFather();                  // 将旋转结点的左子树设为父结点的右子树         father.setRightyChild(node.getLeftChild());         // 若旋转结点的左子树不为空,则将父结点设为左子树的父结点         if (node.getLeftChild() != null) {             node.getLeftChild().setFather(father);         }                  // 将父结点的父结点(爷爷结点)设为旋转结点的父结点         node.setFather(father.getFather());         // 若爷爷结点不为空         if (father.getFather() != null) {             // 若父结点为爷爷结点的左子树,则将旋转结点设为爷爷结点的左子树             if (father == father.getFather().getLeftChild()) {                 father.getFather().setLeftChild(node);                          // 若父结点为爷爷结点的右子树,则将旋转结点设为爷爷结点的右子树             } else {                 father.getFather().setRightyChild(node);             }         }                  // 将父结点设为旋转结点的左子树         node.setLeftChild(father);         // 更新父结点的父结点为旋转结点         father.setFather(node);     }          /**      * 对node结点进行伸展      * @param node      */     protected void splay(SplayTreeNode node) {         if (this.root == null) {             return;         }                  while (node.getFather() != null) {             if (node.getFather() == this.root) {                 if (node == node.getFather().getLeftChild()) {                     this.zig(node);                 } else {                     this.zag(node);                 }             } else if (node.getFather().getFather().getLeftChild() == node.getFather()) {                 if (node == node.getFather().getLeftChild()) {                     this.zig(node.getFather());                     this.zig(node);                 } else {                     this.zag(node);                     this.zig(node);                 }             } else {                 if (node == node.getFather().getRightyChild()) {                     this.zag(node.getFather());                     this.zag(node);                 } else {                     this.zig(node);                     this.zag(node);                 }             }         }         this.root = node;     }          /**      * 合并treeA, treeB,更新root      * @param treeA      * @param treeB      */     protected void join(SplayTreeNode treeA, SplayTreeNode treeB) {         if (treeA != null) {             treeA.setFather(null);         }         if (treeB != null) {             treeB.setFather(null);         }                  if (treeA == null) {             this.root = treeB;             return;         }         if (treeB == null) {             this.root = treeA;             return;         }                  SplayTreeNode node = treeA;         while (node.getRightyChild() != null) {             this.splay(node.getRightyChild());             node = node.getRightyChild();         }                  node.setRightyChild(treeB);         treeB.setFather(node);         this.root = node;     }     /* (non-Javadoc)      * @see SplayTree#size()      */     @Override     public int size() {         return this.size;     }          /* (non-Javadoc)      * @see SplayTree#showTree()      */     @Override     public void showTree() {         List<SplayTreeNode> nodeList = new ArrayList<SplayTreeNode>();         nodeList.add(this.root);         this.bfs(nodeList);          }          /**      * 广度优先遍历SplayTree的每个结点,若结点不为空则输出key值,若为空则输出*      * @param nodeList      */     protected void bfs(List<SplayTreeNode> nodeList) {         List<SplayTreeNode> newNodeList = new ArrayList<SplayTreeNode>();         boolean found = false;         for (SplayTreeNode node : nodeList) {             if (node != null) {                 found = true;                 System.out.print(node.getKey() + " ");                 newNodeList.add(node.getLeftChild());                 newNodeList.add(node.getRightyChild());             } else {                 System.out.print("* ");                 newNodeList.add(null);                 newNodeList.add(null);             }         }         System.out.println("");                  if (found) {             this.bfs(newNodeList);         }     }          /* (non-Javadoc)      * @see SplayTree#showDetail()      */     @Override     public void showDetail() {         this.inorderTraversal(this.root);        }          /**      * 中序遍历SplayTree的每个结点,并输出结点的详细信息      * @param node      */     protected void inorderTraversal(SplayTreeNode node) {         if (node != null) {             System.out.println(node.toString());             this.inorderTraversal(node.getLeftChild());             this.inorderTraversal(node.getRightyChild());         }     } }  
转载请注明原文地址: https://www.6miu.com/read-3850219.html

最新回复(0)