注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
想问下大家伸展树递增序列插入是不是最后还是会变成一条链呢?因为感觉递增序列的一直输入并不会调用splay方法啊。。。- package google;
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.Queue;
- public class SplayTree {
- TreeNode root;
- public SplayTree() {
- root = null;
- }
- public void insert(int num){
- root = insert(root, num);
- splay(num);
- }
- public TreeNode insert(TreeNode root, int num){
- if (root == null) {
- root = new TreeNode(num);
-
- }
- if (num < root.val) {
- root.left = insert(root.left,num);
- }
- else if( num > root.val){
- root.right = insert(root.right,num);
- }
- return root;
- }
- public boolean search(int num){
- if (search(root,num)) {
- splay(num);
- return true;
- }
- else return false;
- }
- private boolean search(TreeNode r,int num){
- if (r==null) {
- return false;
- }
- if (r.val == num) {
- return true;
- }
- if (num < r.val) {
- return search(r.left,num);
- }
- else return search(r.right, num);
- }
- public void splay(int num){
- root = splay(root,num);
- }
- private TreeNode splay(TreeNode r,int num){
- if (r==null || r.val == num) {
- return r;
- }
- if (num < r.val) {
- //left tree
- if (r.left!=null) {
- if (num <r.left.val) {
- root.left.left = splay(r.left.left,num);
- r = rightRightRotate(r);
- }
- else if(num > r.left.val){
- r.left.right = splay(r.left.right, num);
- r = leftRightRotate(r);
- }
- else {
- r = rightRotate(r);
- }
- }
- return r;
- }
- else{
- if (r.right!=null) {
- if (num > r.right.val) {
- r.right.right = splay(r.right.right, num);
- r = leftLeftRotate(r);
- }
- else if (num < r.right.val){
- r.right.left = splay(r.right.left, num);
- r = rightLeftRotate(r);
- }
- else {
- r = leftRotate(r);
- }
- }
- return r;
- }
- }
- private TreeNode rightRotate(TreeNode root){
- TreeNode temp = root.left;
- root.left = temp.right;
- temp.right = root;
- return temp;
- }
- private TreeNode leftRotate(TreeNode root){
- TreeNode temp = root.right;
- root.right = temp.left;
- temp.left = root;
- return temp;
- }
- private TreeNode rightRightRotate(TreeNode root){
- root = rightRotate(root);
- return rightRotate(root);
- }
- private TreeNode leftRightRotate(TreeNode root){
- root.left = leftRotate(root.left);
- return rightRotate(root);
- }
- private TreeNode leftLeftRotate(TreeNode root){
- root = leftRotate(root);
- return leftRotate(root);
- }
- private TreeNode rightLeftRotate(TreeNode root){
- root.right = rightRotate(root.right);
- return leftRotate(root);
- }
- private List<List<Integer>> levelOrder() {
- List<List<Integer>> result = new ArrayList<>();
- Queue<TreeNode> que = new LinkedList<>();
- if (root != null) {
- que.offer(root);
- }
- while (!que.isEmpty()) {
- int len = que.size();
- List<Integer> list = new ArrayList<Integer>();
- for (int i = 0; i < len; i++) {
- TreeNode temp = que.poll();
- list.add(temp.val);
- if (temp.left != null)
- que.offer(temp.left);
- if (temp.right != null)
- que.offer(temp.right);
- }
- result.add(list);
- }
- return result;
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- SplayTree tree = new SplayTree();
- tree.insert(1);
- tree.insert(2);
- tree.insert(3);
- tree.insert(4);
- tree.insert(5);
- tree.insert(6);
- // tree.search(3);
- System.out.println(tree.levelOrder());
- }
- }
复制代码 输出就是[[6], [5], [4], [3], [2], [1]]
而如果调用一次search(3)那么就会平衡了。。
[[3], [2, 5], [1, 4, 6]]
所以想问下是这样的么?  谢谢大家~
|