一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 901|回复: 0
收起左侧

[树/链表/图] 伸展树递增序列插入

[复制链接] |试试Instant~ |关注本帖
杰西Jesse 发表于 2015-11-22 10:42:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
想问下大家伸展树递增序列插入是不是最后还是会变成一条链呢?因为感觉递增序列的一直输入并不会调用splay方法啊。。。
  1. package google;

  2. import java.util.ArrayList;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Queue;

  6. public class SplayTree {
  7.         TreeNode root;
  8.         public SplayTree() {
  9.                 root = null;
  10.         }
  11.         public void insert(int num){
  12.                 root = insert(root, num);
  13.                 splay(num);
  14.         }
  15.         public TreeNode insert(TreeNode root, int num){
  16.                 if (root == null) {
  17.                         root = new TreeNode(num);
  18.                        
  19.                 }
  20.                 if (num < root.val) {
  21.                         root.left = insert(root.left,num);
  22.                 }
  23.                 else if( num > root.val){
  24.                         root.right = insert(root.right,num);
  25.                 }
  26.                 return root;
  27.         }
  28.         public boolean search(int num){
  29.                 if (search(root,num)) {
  30.                         splay(num);
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.         private boolean search(TreeNode r,int num){
  36.                 if (r==null) {
  37.                         return false;
  38.                 }
  39.                 if (r.val == num) {
  40.                         return true;
  41.                 }
  42.                 if (num < r.val) {
  43.                         return search(r.left,num);
  44.                 }
  45.                 else return search(r.right, num);
  46.         }
  47.         public void splay(int num){
  48.                 root = splay(root,num);
  49.         }
  50.         private TreeNode splay(TreeNode r,int num){
  51.                 if (r==null || r.val == num) {
  52.                         return r;
  53.                 }
  54.                 if (num < r.val) {
  55.                         //left tree
  56.                         if (r.left!=null) {
  57.                                 if (num <r.left.val) {
  58.                                         root.left.left = splay(r.left.left,num);
  59.                                         r = rightRightRotate(r);
  60.                                 }
  61.                                 else if(num > r.left.val){
  62.                                         r.left.right = splay(r.left.right, num);
  63.                                         r = leftRightRotate(r);
  64.                                 }
  65.                                 else {
  66.                                         r = rightRotate(r);
  67.                                 }
  68.                         }
  69.                         return r;
  70.                 }
  71.                 else{
  72.                         if (r.right!=null) {
  73.                                 if (num > r.right.val) {
  74.                                         r.right.right = splay(r.right.right, num);
  75.                                         r = leftLeftRotate(r);
  76.                                 }
  77.                                 else if (num < r.right.val){
  78.                                         r.right.left = splay(r.right.left, num);
  79.                                         r = rightLeftRotate(r);
  80.                                 }
  81.                                 else {
  82.                                         r = leftRotate(r);
  83.                                 }
  84.                         }
  85.                         return r;
  86.                 }
  87.         }
  88.         private TreeNode rightRotate(TreeNode root){
  89.                 TreeNode temp = root.left;
  90.                 root.left = temp.right;
  91.                 temp.right = root;
  92.                 return temp;
  93.         }

  94.         private TreeNode leftRotate(TreeNode root){
  95.                 TreeNode temp  = root.right;
  96.                 root.right = temp.left;
  97.                 temp.left = root;
  98.                 return temp;
  99.         }
  100.         private TreeNode rightRightRotate(TreeNode root){
  101.                 root = rightRotate(root);
  102.                 return rightRotate(root);
  103.         }
  104.         private TreeNode leftRightRotate(TreeNode root){
  105.                 root.left = leftRotate(root.left);
  106.                 return rightRotate(root);
  107.         }
  108.         private TreeNode leftLeftRotate(TreeNode root){
  109.                 root = leftRotate(root);
  110.                 return leftRotate(root);
  111.         }
  112.         private TreeNode rightLeftRotate(TreeNode root){
  113.                 root.right = rightRotate(root.right);
  114.                 return leftRotate(root);
  115.         }
  116.         private List<List<Integer>> levelOrder() {
  117.                 List<List<Integer>> result = new ArrayList<>();
  118.                 Queue<TreeNode> que = new LinkedList<>();
  119.                 if (root != null) {
  120.                         que.offer(root);
  121.                 }
  122.                 while (!que.isEmpty()) {
  123.                         int len = que.size();
  124.                         List<Integer> list = new ArrayList<Integer>();
  125.                         for (int i = 0; i < len; i++) {
  126.                                 TreeNode temp = que.poll();
  127.                                 list.add(temp.val);
  128.                                 if (temp.left != null)
  129.                                         que.offer(temp.left);
  130.                                 if (temp.right != null)
  131.                                         que.offer(temp.right);
  132.                         }
  133.                         result.add(list);
  134.                 }
  135.                 return result;
  136.         }
  137.         public static void main(String[] args) {
  138.                 // TODO Auto-generated method stub
  139.                 SplayTree tree = new SplayTree();
  140.                 tree.insert(1);
  141.                 tree.insert(2);
  142.                 tree.insert(3);
  143.                 tree.insert(4);
  144.                 tree.insert(5);
  145.                 tree.insert(6);
  146. //                tree.search(3);
  147.                 System.out.println(tree.levelOrder());
  148.         }

  149. }
复制代码
输出就是[[6], [5], [4], [3], [2], [1]]
而如果调用一次search(3)那么就会平衡了。。
[[3], [2, 5], [1, 4, 6]]

所以想问下是这样的么?
谢谢大家~

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 02:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表