• SplayTree高分测试用例

    测试用例结果展示

    覆盖率

     变异得分

    测试注意点

    1. 从SplayTree测起，然后再测SubSplayTree，因为前者调用后者。
    2. SplaySubTree的remove方法大部分内容需要通过反射才能测到。
    3. value和index在SplayTree当中都不是唯一的。一个index可能对应多个value。

    不足之处

    1. 没考虑到异常怎么接住。
    2. 对SplayTree这个数据结构的理解还很浅显。

    测试文件MyTest.java

    1. package net.mooctest;
    2.  
    3. import static org.junit.Assert.*;
    4.  
    5. import java.lang.reflect.Field;
    6. import java.util.Arrays;
    7.  
    8. import org.junit.Before;
    9. import org.junit.Test;
    10.  
    11. public class MyTest {
    12. 	
    13. 	private Integer valArr[];
    14. 	private Integer remArr[];
    15. 	private Integer conArr[];
    16. 	private SplayTree splayTree;
    17. 	private int howmanynumbers;
    18. 	private int removeCnt;
    19. 	private int containsCnt;
    20. 	
    21. 	@Before
    22. 	public void initializeValArr() {
    23. 		
    24. 		this.howmanynumbers = 100;
    25. 		this.removeCnt = 0;
    26. 		this.containsCnt = 0;
    27. 		
    28. 		valArr = new Integer[howmanynumbers];  
    29. 		remArr = new Integer[howmanynumbers/7+1];  
    30. 		conArr = new Integer[howmanynumbers/9+1];
    31. 		
    32. 		for(int i=0;i<this.howmanynumbers;i++) {
    33. 			int val = (int)(Math.random()*100);
    34. //			System.out.println(val);
    35. 			valArr[i] = val;
    36. 			if(i%7==0) {
    37. 				remArr[this.removeCnt++] = val;
    38. 			}
    39. 			if(i%9==0) {
    40. 				conArr[this.containsCnt++] = val;
    41. 			}
    42. 		}
    43. 		
    44. 	}
    45.  
    46. 	@Test
    47. 	public void testMain() {
    48. 		SplayTree.main(null);
    49. 	}
    50. 	
    51. 	// 测试remove和contains
    52. 	@Test
    53. 	public void test001() {
    54. 		splayTree = new SplayTree();
    55. 		for(int i=0;i<this.howmanynumbers;i++) {
    56. 			splayTree.add(valArr[i]);
    57. 			assertNull(splayTree.root.join(splayTree.root));
    58. 		}
    59. 		assertNotNull(splayTree.root.add(null));
    60. 		assertEquals(howmanynumbers, splayTree.size());
    61. 		
    62. 		for(int i=0;i<this.removeCnt;i++) {
    63. 			int valToRemove = remArr[i];
    64. 			assertTrue(splayTree.contains(valToRemove));
    65. 			splayTree.remove(valToRemove);
    66. 		}
    67. 		assertEquals(howmanynumbers-removeCnt, splayTree.size());
    68. 		
    69. 		for(int i=0;i<this.containsCnt;i++) {
    70. 			int valToVarify = conArr[i];
    71. 			assertTrue(splayTree.contains(valToVarify));
    72. 		}
    73. 	}
    74. 	
    75. 	// 测试remove和contains
    76. 	@Test
    77. 	public void test002() {
    78. 		splayTree = new SplayTree();
    79. 		for(int i=0;i<this.howmanynumbers;i++) {
    80. 			splayTree.add(valArr[i]);
    81. 			assertNull(splayTree.root.split(splayTree.root.getData()));
    82. 		}
    83. 		assertEquals(howmanynumbers, splayTree.size());
    84. 		
    85. 		for(int i=0;i<this.removeCnt;i++) {
    86. 			int valToRemove = remArr[i];
    87. 			assertTrue(splayTree.contains(valToRemove));
    88. 			splayTree.remove(valToRemove);
    89. 		}
    90. 		assertEquals(howmanynumbers-removeCnt, splayTree.size());
    91. 		
    92. 		for(int i=0;i<this.containsCnt;i++) {
    93. 			int valToVarify = conArr[i];
    94. 			assertTrue(splayTree.contains(valToVarify));
    95. 		}
    96. 	}
    97. 	
    98. 	// 测试get和indexOf
    99. 	// 不能再用随机生成的数据，因为随机数据很可能重复
    100. 	@Test
    101. 	public void test003() {
    102. 		splayTree = new SplayTree();
    103. 		for(int i=0;i<this.howmanynumbers;i++) {
    104. 			splayTree.add(i*17);
    105. 		}
    106. 		assertEquals(howmanynumbers, splayTree.size());
    107. 		
    108. 		long idxArr[] = new long[howmanynumbers];
    109. 		
    110. 		for(int i=0;i
    111. 			idxArr[i] = splayTree.indexOf(i*17);
    112. 		}
    113. 		
    114. 		for(int i=0;i
    115. 			assertEquals(i*17, (int)splayTree.get(idxArr[i]));
    116. 		}
    117. 		assertNull(splayTree.get(-1));
    118. 		assertNull(splayTree.get(splayTree.size()+1));
    119. 	}
    120. 	
    121. 	
    122. 	//测试toString()
    123. 	@Test
    124. 	public void test004() {
    125. 		int primeArr[] = {
    126. 			2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 	
    127. 		};
    128. 		
    129. 		splayTree = new SplayTree();
    130. 		
    131. 		for(int i=0;i
    132. 			splayTree.add(primeArr[i]);
    133. 		}
    134. 		
    135. //		System.out.println(splayTree.toString());
    136. //		String expectedStr = " data=2 left= null right null sz=1 cnt=1\n";
    137. //		assertEquals(expectedStr, splayTree.toString());
    138. 		
    139. 		String expectedStr = " data=71 left=67 right null sz=20 cnt=1\n" + 
    140. 				" data=67 left=61 right null sz=19 cnt=1\n" + 
    141. 				" data=61 left=59 right null sz=18 cnt=1\n" + 
    142. 				" data=59 left=53 right null sz=17 cnt=1\n" + 
    143. 				" data=53 left=47 right null sz=16 cnt=1\n" + 
    144. 				" data=47 left=43 right null sz=15 cnt=1\n" + 
    145. 				" data=43 left=41 right null sz=14 cnt=1\n" + 
    146. 				" data=41 left=37 right null sz=13 cnt=1\n" + 
    147. 				" data=37 left=31 right null sz=12 cnt=1\n" + 
    148. 				" data=31 left=29 right null sz=11 cnt=1\n" + 
    149. 				" data=29 left=23 right null sz=10 cnt=1\n" + 
    150. 				" data=23 left=19 right null sz=9 cnt=1\n" + 
    151. 				" data=19 left=17 right null sz=8 cnt=1\n" + 
    152. 				" data=17 left=13 right null sz=7 cnt=1\n" + 
    153. 				" data=13 left=11 right null sz=6 cnt=1\n" + 
    154. 				" data=11 left=7 right null sz=5 cnt=1\n" + 
    155. 				" data=7 left=5 right null sz=4 cnt=1\n" + 
    156. 				" data=5 left=3 right null sz=3 cnt=1\n" + 
    157. 				" data=3 left=2 right null sz=2 cnt=1\n" + 
    158. 				" data=2 left= null right null sz=1 cnt=1\n";
    159. 		
    160. 		assertEquals(expectedStr, splayTree.toString());
    161. 	}
    162. 	
    163. 	//测试SplaySubTree--find
    164. 	@Test(timeout=4000)
    165. 	public void test005() {
    166. 		SplaySubTree splaySubTree = new SplaySubTree(null);
    167. 		assertNull(splaySubTree.find(1));
    168. 		int primeArr[] = {
    169. 			2, 41, 5, 7, 67, 23, 11,  17, 19
    170. 		};
    171. 		for(int i=0;i
    172. 			splaySubTree = splaySubTree.add(primeArr[i]);
    173. 		}
    174. //		System.out.println(splaySubTree.toString());
    175. 		assertNull(splaySubTree.find(20));
    176. 	}
    177. 	
    178. 	//测试SplaySubTree--remove
    179. 	@Test(timeout=4000)
    180. 	public void test006() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
    181. 		SplaySubTree splaySubTree = new SplaySubTree(0);
    182. 		
    183. 		int primeArr[] = {
    184. 			2, 41, 5, 7, 23, 11, 67, 17, 19
    185. 		};
    186. 		
    187. 		System.out.println(primeArr.length);
    188. 		
    189. 		for(int i=0;i
    190. 			splaySubTree = splaySubTree.add(primeArr[i]);
    191. 		}
    192. 		
    193. 		assertNotNull(splaySubTree.remove(20));
    194. 		
    195. 		assertEquals(primeArr.length+1,splaySubTree.remove(null).size());
    196.  
    197.   
    198.         // 获取 SplaySubTree 的 Class 对象  
    199.         Class splaySubTreeClass = splaySubTree.getClass();  
    200.   
    201.         // 获取私有属性 count 的 Field 对象  
    202.         Field countField = splaySubTreeClass.getDeclaredField("count");  
    203.   
    204.         // 设置私有属性 count 的可访问性  
    205.         countField.setAccessible(true); 
    206. 		
    207. 		splaySubTree = splaySubTree.remove(7);
    208. 		// 访问私有属性 count 的值  
    209.         int countValue = (int) countField.get(splaySubTree);  
    210. //        System.out.println("countValue: " + countValue);
    211.         assertEquals(0, countValue);
    212. //		System.out.println(splaySubTree.toString());
    213. 		splaySubTree = splaySubTree.remove(7);
    214. 		countValue = (int) countField.get(splaySubTree);  
    215. //        System.out.println("countValue: " + countValue); 
    216.         assertEquals(-1, countValue);
    217.  
    218. 	}
    219. 	
    220. 		//测试SplaySubTree--remove
    221. 		@Test(timeout=4000)
    222. 		public void test007() {
    223. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    224. 			splaySubTree.remove(1);
    225. 		}
    226. 		
    227. 		//测试SplaySubTree--remove
    228. 		@Test(timeout=4000)
    229. 		public void test008() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
    230. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    231. 			// 获取 SplaySubTree 的 Class 对象  
    232. 	        Class splaySubTreeClass = splaySubTree.getClass();  
    233. 	        // 获取私有属性 count 的 Field 对象  
    234. 	        Field leftField = splaySubTreeClass.getDeclaredField("left");  
    235. 	        // 设置私有属性 count 的可访问性  
    236. 	        leftField.setAccessible(true);         
    237. 			SplaySubTree splaySubTree2 = new SplaySubTree(2);
    238. 			
    239. 			leftField.set(splaySubTree,splaySubTree2);
    240. 			
    241. 			
    242. 			
    243. 			splaySubTree.remove(1);
    244. 		}
    245. 		
    246. 		//测试SplaySubTree--remove
    247. 		@Test(timeout=4000)
    248. 		public void test009() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
    249. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    250. 			// 获取 SplaySubTree 的 Class 对象  
    251. 	        Class splaySubTreeClass = splaySubTree.getClass();  
    252. 	        // 获取私有属性 count 的 Field 对象  
    253. 	        Field rightField = splaySubTreeClass.getDeclaredField("right");  
    254. 	        // 设置私有属性 count 的可访问性  
    255. 	        rightField.setAccessible(true);         
    256. 			SplaySubTree splaySubTree2 = new SplaySubTree(2);
    257. 			
    258. 			rightField.set(splaySubTree,splaySubTree2);
    259. 		
    260. 			splaySubTree.remove(1);
    261. 		}
    262. 				
    263. 		
    264. 		//测试SplaySubTree--remove
    265. 		@Test(timeout=4000)
    266. 		public void test0010() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
    267. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    268. 			// 获取 SplaySubTree 的 Class 对象  
    269. 	        Class splaySubTreeClass = splaySubTree.getClass();  
    270. 	        // 获取私有属性 count 的 Field 对象  
    271. 	        Field leftField = splaySubTreeClass.getDeclaredField("left");
    272. 	        Field parentField = splaySubTreeClass.getDeclaredField("parent");  
    273. 	        // 设置私有属性 count 的可访问性  
    274. 	        leftField.setAccessible(true);   
    275. 	        parentField.setAccessible(true);   
    276. 	        
    277. 			SplaySubTree splaySubTree2 = new SplaySubTree(2);
    278. 			leftField.set(splaySubTree,splaySubTree2);
    279. 			SplaySubTree splaySubTree3 = new SplaySubTree(3);
    280. 			parentField.set(splaySubTree,splaySubTree3);
    281. 		
    282. 			splaySubTree.remove(1);
    283. 		}
    284. 		
    285. 		//测试SplaySubTree--remove
    286. 		@Test(timeout=4000)
    287. 		public void test0011() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
    288. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    289. 			// 获取 SplaySubTree 的 Class 对象  
    290. 	        Class splaySubTreeClass = splaySubTree.getClass();  
    291. 	        // 获取私有属性 count 的 Field 对象  
    292. 	        Field rightField = splaySubTreeClass.getDeclaredField("right");  
    293. 	        Field parentField = splaySubTreeClass.getDeclaredField("parent"); 
    294. 	        // 设置私有属性 count 的可访问性  
    295. 	        rightField.setAccessible(true);   
    296. 	        parentField.setAccessible(true); 
    297. 	        
    298. 			SplaySubTree splaySubTree2 = new SplaySubTree(2);
    299. 			rightField.set(splaySubTree,splaySubTree2);
    300. 			SplaySubTree splaySubTree3 = new SplaySubTree(3);
    301. 			parentField.set(splaySubTree,splaySubTree3);
    302. 		
    303. 			splaySubTree.remove(1);
    304. 		}
    305. 		
    306. 		//测试SplaySubTree--remove
    307. 		@Test(timeout=4000)
    308. 		public void test0012() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
    309. 			SplaySubTree splaySubTree = new SplaySubTree(1);
    310. 			// 获取 SplaySubTree 的 Class 对象  
    311. 	        Class splaySubTreeClass = splaySubTree.getClass();  
    312. 	        // 获取私有属性 count 的 Field 对象  
    313. 	        Field rightField = splaySubTreeClass.getDeclaredField("right");  
    314. 	        Field leftField = splaySubTreeClass.getDeclaredField("left"); 
    315. 	        // 设置私有属性 count 的可访问性  
    316. 	        rightField.setAccessible(true);   
    317. 	        leftField.setAccessible(true); 
    318. 	        
    319. 			SplaySubTree splaySubTree2 = new SplaySubTree(2);
    320. 			rightField.set(splaySubTree,splaySubTree2);
    321. 			SplaySubTree splaySubTree3 = new SplaySubTree(3);
    322. 			leftField.set(splaySubTree,splaySubTree3);
    323.  
    324. 			String expectedStr = " data=1 left=3 right=2 sz=1 cnt=1\n" + 
    325. 					" data=3 left= null right null sz=1 cnt=1\n" + 
    326. 					" data=2 left= null right null sz=1 cnt=1\n";
    327. 			
    328. 			assertEquals(expectedStr, splaySubTree.toString());
    329. 		}
    330.  
    331. }

    被测文件(1/2)SplayTree.java

    1. package net.mooctest;
    2.  
    3. import java.util.Arrays;
    4.  
    5. public class SplayTree extends Comparable> {
    6. 	SplaySubTree root;
    7. 	
    8. 	public SplayTree(){
    9. 		root = new SplaySubTree(null);
    10. 	}
    11. 	
    12. 	/**
    13. 	 * @param index - of the node to search for.
    14. 	 * @return  - null if index<=0 or index>=size otherwise SubTree at index. 
    15. 	 */
    16. 	public T get(long index) {
    17. 		SplaySubTree cT = root.get(index);
    18. 		if(cT==null)return null;
    19. 		cT.splay();
    20. 		root = cT;
    21. 		return cT.getData();
    22. 	}
    23. 	
    24. 	/**
    25. 	 * @return - the number of nodes in the tree.
    26. 	 */
    27. 	public long size() { return root.size();}
    28.  
    29. 	/**
    30. 	 * @param node - to search for.
    31. 	 * @return - the index of node. All nodes are ordered according to the compareTo(T) method.
    32. 	 *         
    33. 	 */
    34. 	public long indexOf(T node) {
    35. 		long index = root.indexOf(node);
    36. 		get(index);
    37. 		return index;
    38. 	}
    39. 	
    40. 	/**
    41. 	 * @param node - is added to the tree.
    42. 	 *             If node is null tree is unchanged.
    43. 	 */
    44. 	public void add(T node) {
    45. 		root = root.add(node);
    46. 	}
    47. 	
    48. 	/**
    49. 	 * @param node - is removed from the tree.
    50. 	 *             If node is null tree is unchanged.
    51. 	 */
    52. 	public void remove(T node) {
    53. 		root = root.remove(node);
    54. 	}
    55. 	
    56. 	/**
    57. 	 * @param node
    58. 	 * @return
    59. 	 */
    60. 	public boolean contains(T node) {
    61. 		SplaySubTree temp = root.find(node);
    62. 		if(temp!=null){
    63. 			temp.splay();
    64. 			root = temp;
    65. 		}
    66. 		return temp != null;
    67. 	}
    68. 	
    69. 	@Override
    70. 	public String toString(){
    71. 		return root.toString();
    72. 	}
    73.  
    74. 	public static void main(String[] args) {
    75. 		SplayTree test = new SplayTree();
    76. 		int howmanynumbers = 10000;
    77. 		for (int i = 0; i < howmanynumbers; i++) {
    78. 			int val = (int)(Math.random()*100);
    79. 			test.add(val);
    80. 		}
    81. 		
    82.  
    83. 		System.out.println(test);
    84. 	}
    85. }

    被测文件(2/2)SubSplayTree.java

    1. package net.mooctest;
    2.  
    3. public class SplaySubTreeextends Comparable> {
    4.  
    5. 	private T data;
    6. 	private SplaySubTree left, right, parent;
    7. 	private long size; // number of nodes in tree
    8. 	private int count;
    9.  
    10. 	/**
    11. 	 * @param node
    12. 	 *            - If node==null then size will be 0 otherwise node will be in the
    13. 	 *            tree and size will be 1
    14. 	 */
    15. 	public SplaySubTree(T node) {
    16. 		data = node;
    17. 		if (node != null) {
    18. 			size = count = 1;
    19. 		}
    20. 	}
    21. 	
    22. 	
    23.  
    24. 	public String toString() {
    25. 		String lft = "";
    26. 		String rght = "";
    27. 		String myData = " data=" + data;
    28. 		if (left != null) {
    29. 			myData += " left=" + left.data;
    30. 			lft = left.toString();
    31. 		} else {
    32. 			myData += " left= null";
    33. 		}
    34. 		if (right != null) {
    35. 			myData += " right=" + right.data;
    36. 			rght = right.toString();
    37. 		} else {
    38. 			myData += " right null";
    39. 		}
    40. 		myData += " sz="+size + " cnt="+count;
    41. 		return myData + "\n" + lft + rght;
    42. 	}
    43.  
    44. 	public T getData() {
    45. 		return data;
    46. 	}
    47.  
    48. 	/**
    49. 	 * @param index
    50. 	 *            - of the node to search for.
    51. 	 * @return - null if index<=0 or index>=size otherwise SubTree at index.
    52. 	 */
    53. 	public SplaySubTree get(long index) {
    54. 		if (index > size || index < 0)
    55. 			return null;
    56. 		long cS = 1;
    57. 		SplaySubTree cT = this;
    58. 		if (cT.left != null)
    59. 			cS += cT.left.size;
    60. 		while (cS != index) {
    61. 			if (cS > index) {
    62. 				cS--;
    63. 				cT = cT.left;
    64. 				if (cT != null && cT.right != null)
    65. 					cS -= cT.right.size;
    66. 			} else {
    67. 				cS++;
    68. 				cT = cT.right;
    69. 				if (cT != null && cT.left != null)
    70. 					cS += cT.left.size;
    71. 			}
    72. 		}
    73. 		return cT;
    74. 	}
    75.  
    76. 	/**
    77. 	 * @return - the number of nodes in the tree.
    78. 	 */
    79. 	public long size() {
    80. 		return size;
    81. 	}
    82.  
    83. 	/**
    84. 	 * @param node
    85. 	 *            - to search for.
    86. 	 * @return - the index of node. All nodes are ordered according to the
    87. 	 *         compareTo(T) method.
    88. 	 * 
    89. 	 */
    90. 	public long indexOf(T node) {
    91. 		if (node == null)
    92. 			return -1;
    93. 		long cI = 1;
    94. 		SplaySubTree cT = this;
    95. 		if (cT.left != null)
    96. 			cI += cT.left.size;
    97. 		while (!cT.data.equals(node)) {
    98. 			if (cT.data.compareTo(node) > 0) {
    99. 				cI--;
    100. 				cT = cT.left;
    101. 				if (cT != null && cT.right != null)
    102. 					cI -= cT.right.size;
    103. 			} else {
    104. 				cI++;
    105. 				cT = cT.right;
    106. 				if (cT != null && cT.left != null)
    107. 					cI += cT.left.size;
    108. 			}
    109. 			if (cT == null)
    110. 				return -1;
    111. 		}
    112.  
    113. 		return cI;
    114. 	}
    115.  
    116. 	/**
    117. 	 * @param node
    118. 	 *            - is added to the tree. If node is null tree is unchanged.
    119. 	 * @return - New root of the tree.
    120. 	 */
    121. 	public SplaySubTree add(T node) {
    122. 		if (node == null)
    123. 			return this;
    124. 		if (this.data == null)
    125. 			return new SplaySubTree(node);
    126. 		SplaySubTree current = this;
    127. 		SplaySubTree child = null;
    128.  
    129. 		if (this.data.compareTo(node) < 0)
    130. 			child = this.right;
    131. 		else if(this.data.compareTo(node)>0)
    132. 			child = this.left;
    133. 		while (child != null && current.data.compareTo(node)!=0) {
    134. 			current = child;
    135. 			if (current.data.compareTo(node) < 0)
    136. 				child = current.right;
    137. 			else if(current.data.compareTo(node)>0)
    138. 				child = current.left;
    139. 		}
    140. 		
    141. 		SplaySubTree newNode = new SplaySubTree(node);
    142. 		if (current.data.compareTo(node) < 0) {
    143. 			current.right = newNode;
    144. 		} else if(current.data.compareTo(node)>0){
    145. 			current.left = newNode;
    146. 		}else {
    147. 			current.size++;
    148. 			current.count++;
    149. 			newNode = current;
    150. 			current = newNode.parent;
    151. 		}
    152. 		newNode.parent = current;
    153. 		if (newNode.splay())
    154. 			return newNode;
    155. 		return this;
    156. 	}
    157.  
    158. 	/**
    159. 	 * @param node
    160. 	 *            - is removed from the tree. If node is null tree is unchanged.
    161. 	 * @return - New root of the tree.
    162. 	 */
    163. 	public SplaySubTree remove(T node) {
    164. 		if (node == null)
    165. 			return this;
    166. 		SplaySubTree x = find(node);
    167. 		if (x == null)
    168. 			return this;
    169. 		if(x.data.equals(node)) {
    170. 			x.count--;
    171. 			x.size--;
    172. 			if(size>0) {
    173. 				x.splay();
    174. 				return x;
    175. 			}
    176. 		}
    177. 		// To delete a node x:
    178. 		// if x has no children remove it.
    179.  
    180. 		if (x.left == null && x.right == null) {
    181. 			if (x.parent != null) {
    182. 				if (x.parent.left == x) {
    183. 					parent.left = null;
    184. 				} else
    185. 					parent.right = null;
    186. 			} else
    187. 				return new SplaySubTree(null);
    188.  
    189. 		}
    190. 		// if x has one child remove x, and put the child in place of x
    191. 		if (x.left == null) {
    192. 			if (x.parent != null) {
    193. 				if (x.parent.left == x) {
    194. 					parent.left = x.right;
    195. 					x.right.parent = parent;
    196. 					x = x.right;
    197. 				} else {
    198. 					parent.right = x.right;
    199. 					x.right.parent = parent;
    200. 					x = x.right;
    201. 				}
    202. 			} else {
    203. 				x.right.parent = null;
    204. 				return x.right;
    205. 			}
    206. 		} else if (x.right == null) {
    207. 			if (x.parent != null) {
    208. 				if (x.parent.left == x) {
    209. 					parent.left = x.left;
    210. 					x.left.parent = parent;
    211. 					x = x.left;
    212. 				} else {
    213. 					parent.right = x.left;
    214. 					x.left.parent = parent;
    215. 					x = x.left;
    216. 				}
    217. 			} else {
    218. 				x.left.parent = null;
    219. 				return x.left;
    220. 			}
    221. 		} else {
    222. 			// if x has two children, swap its value with that of
    223. 			// the rightmost node of its left sub tree
    224. 			SplaySubTree rmc = x.left;
    225. 			while (rmc.right != null)
    226. 				rmc = rmc.right;
    227. 			x.data = rmc.data;
    228. 			// Then remove that node instead.
    229. 			rmc.left.parent = rmc.parent;
    230. 			if (rmc.parent == x) {
    231. 				x.left = rmc.left;
    232. 			} else {
    233. 				rmc.parent.right = rmc.left;
    234. 			}
    235. 			x = rmc;
    236. 		}
    237.  
    238. 		// After deletion, splay the parent of the removed node to the top of
    239. 		// the tree.
    240. 		x.splay();
    241. 		return x;
    242. 	}
    243.  
    244. 	/**
    245. 	 * @param other
    246. 	 * @return
    247. 	 */
    248. 	public SplaySubTree join(SplaySubTree other) {
    249. 		return null;
    250.  
    251. 	}
    252.  
    253. 	/**
    254. 	 * @param node
    255. 	 * @return
    256. 	 */
    257. 	public SplaySubTree split(T node) {
    258. 		return null;
    259. 	}
    260.  
    261. 	/**
    262. 	 * @param node
    263. 	 * @return
    264. 	 */
    265. 	public SplaySubTree find(T node) {
    266. 		SplaySubTree current = this;
    267. 		if (this.data == null)
    268. 			return null;
    269. 		while (current != null) {
    270. 			if (node.equals(current.data))
    271. 				return current;
    272. 			if (node.compareTo(current.data) < 0)
    273. 				current = current.left;
    274. 			else
    275. 				current = current.right;
    276. 		}
    277. 		return current;
    278. 	}
    279.  
    280. 	/**
    281. 	 * Assuming this node is an interior or leaf node of a larger tree this method
    282. 	 * moves this node up to the root balancing the tree in the process
    283. 	 */
    284. 	public boolean splay() {
    285. 		
    286. 		while (this.parent != null) {
    287. 			SplaySubTree p = this.parent;
    288. 			SplaySubTree g = p.parent;
    289. 			if (g == null && this == p.left) {
    290. 				zig();
    291. 			} else if (g == null && this == p.right) {
    292. 				zag();
    293. 			} else if (p.left == this && g.left == p) {
    294. 				zigzig();
    295. 			} else if (p.right == this && g.right == p) {
    296. 				zagzag();
    297. 			} else if (p.right == this && g.left == p) {
    298. 				zigzag();
    299. 			} else {
    300. 				zagzig();
    301. 			}
    302. 		}
    303. 		return true;
    304. 	}
    305.  
    306. 	/**
    307. 	 * This is a helper method used in the splay() operation
    308. 	 */
    309. 	private void zig() {
    310. 		SplaySubTree b = this.right;
    311. 		SplaySubTree p = this.parent;
    312.  
    313. 		this.right = p;
    314. 		p.parent = this;
    315. 		p.left = b;
    316. 		if (b != null)
    317. 			b.parent = p;
    318. 		this.parent = null;
    319. 		p.size = p.count;
    320. 		if (p.right != null)
    321. 			p.size += p.right.size;
    322. 		if (b != null)
    323. 			p.size += b.size;
    324. 		this.size = p.size + this.count;
    325. 		if (this.left != null)
    326. 			this.size += this.left.size;
    327. 	}
    328.  
    329. 	/**
    330. 	 * This is a helper method used in the splay() operation
    331. 	 */
    332. 	private void zag() {
    333. 		SplaySubTree b = this.left;
    334. 		SplaySubTree p = this.parent;
    335.  
    336. 		this.left = p;
    337. 		p.parent = this;
    338. 		p.right = b;
    339. 		if (b != null)
    340. 			b.parent = p;
    341. 		this.parent = null;
    342. 		p.size = p.count;
    343. 		if (b != null)
    344. 			p.size += b.size;
    345. 		if (p.left != null)
    346. 			p.size += p.left.size;
    347. 		this.size = p.size + this.count;
    348. 		if (this.right != null)
    349. 			this.size += this.right.size;
    350. 	}
    351.  
    352. 	/**
    353. 	 * This is a helper method used by zigzig, zagzag, zigzag, zagzig This "fixes"
    354. 	 * the great grandparent
    355. 	 */
    356. 	private void fixGG(SplaySubTree g) {
    357. 		SplaySubTree gg = g.parent;
    358. 		if (gg != null) {
    359. 			if (g == gg.left)
    360. 				gg.left = this;
    361. 			if (g == gg.right)
    362. 				gg.right = this;
    363. 		}
    364. 		this.parent = gg;
    365. 		// might need to update size
    366. 	}
    367.  
    368. 	/**
    369. 	 * This is a helper method used in the splay() operation
    370. 	 */
    371. 	private void zigzig() {
    372. 		SplaySubTree g = parent.parent;
    373. 		SplaySubTree b = this.right;
    374. 		SplaySubTree p = this.parent;
    375. 		SplaySubTree c = p.right;
    376. 		fixGG(g);
    377.  
    378. 		if (b != null)
    379. 			b.parent = p;
    380. 		p.left = b;
    381. 		if (c != null)
    382. 			c.parent = g;
    383. 		g.left = c;
    384. 		g.parent = p;
    385. 		p.right = g;
    386. 		p.parent = this;
    387. 		this.right = p;
    388.  
    389. 		g.size = g.count;
    390. 		if (c != null)
    391. 			g.size += c.size;
    392. 		if (g.right != null)
    393. 			g.size += g.right.size;
    394. 		p.size = p.count;
    395. 		if (g != null)
    396. 			p.size += g.size;
    397. 		if (b != null)
    398. 			p.size += b.size;
    399. 		this.size = p.size + this.count;
    400. 		if (this.left != null)
    401. 			this.size += this.left.size;
    402. 	}
    403.  
    404. 	/**
    405. 	 * This is a helper method used in the splay() operation
    406. 	 */
    407. 	private void zagzag() {
    408. 		SplaySubTree g = parent.parent;
    409. 		SplaySubTree b = this.left;
    410. 		SplaySubTree p = this.parent;
    411. 		SplaySubTree c = p.left;
    412.  
    413. 		fixGG(g);
    414. 		if (b != null)
    415. 			b.parent = p;
    416. 		// above line throws java.lang.NullPointerException
    417.  
    418. 		p.right = b;
    419. 		if (c != null)
    420. 			c.parent = g;
    421. 		g.right = c;
    422. 		g.parent = p;
    423. 		p.left = g;
    424. 		p.parent = this;
    425. 		this.left = p;
    426. 		g.size = g.count;
    427. 		if (g.left != null)
    428. 			g.size += g.left.size;
    429. 		if (c != null)
    430. 			g.size += c.size;
    431. 		p.size = g.size + p.count;
    432. 		if (b != null)
    433. 			p.size += b.size;
    434. 		this.size = p.size + this.count;
    435. 		if (this.right != null)
    436. 			this.size += this.right.size;
    437. 	}
    438.  
    439. 	/**
    440. 	 * This is a helper method used in the splay() operation
    441. 	 */
    442. 	private void zigzag() {
    443. 		SplaySubTree g = parent.parent;
    444. 		SplaySubTree b = this.left;
    445. 		SplaySubTree p = this.parent;
    446. 		SplaySubTree c = this.right;
    447.  
    448. 		fixGG(g);
    449. 		if (b != null)
    450. 			b.parent = p;
    451. 		p.right = b;
    452. 		if (c != null)
    453. 			c.parent = g;
    454. 		g.left = c;
    455. 		p.parent = this;
    456. 		this.left = p;
    457. 		g.parent = this;
    458. 		this.right = g;
    459. 		g.size = g.count;
    460. 		if (g.right != null)
    461. 			g.size += g.right.size;
    462. 		if (c != null)
    463. 			g.size += c.size;
    464. 		p.size = p.count;
    465. 		if (p.left != null)
    466. 			p.size += p.left.size;
    467. 		if (b != null)
    468. 			p.size += b.size;
    469. 		this.size = g.size + p.size + this.count;
    470. 	}
    471.  
    472. 	/**
    473. 	 * This is a helper method used in the splay() operation
    474. 	 */
    475. 	private void zagzig() {
    476.  
    477. 		SplaySubTree g = parent.parent;
    478. 		SplaySubTree b = this.right;
    479. 		SplaySubTree p = this.parent;
    480. 		SplaySubTree c = this.left;
    481. 		fixGG(g);
    482. 		if (b != null)
    483. 			b.parent = p;
    484. 		p.left = b;
    485. 		if (c != null)
    486. 			c.parent = g;
    487. 		g.right = c;
    488. 		p.parent = this;
    489. 		this.right = p;
    490. 		g.parent = this;
    491. 		this.left = g;
    492. 		g.size = g.count;
    493. 		if (g.left != null)
    494. 			g.size += g.left.size;
    495. 		if (c != null)
    496. 			g.size += c.size;
    497. 		p.size = p.count;
    498. 		if (p.right != null)
    499. 			p.size += p.right.size;
    500. 		if (b != null)
    501. 			p.size += b.size;
    502. 		this.size = g.size + p.size + this.count;
    503. 	}
    504.  
    505. }

  • 相关阅读:
    `Algorithm-Solution` `LeetCode` 6256. 将节点分成尽可能多的组
    MapReduce & YARN 的部署
    python协整与异步调用，压榨程序的摸鱼时间——使用异步编写需要循环执行的程序，并获取返回值（2）
    URL和URI
    【mysql】linux安装安装 mysql
    从 C 到 C++ 编程 — 基于 template 的泛型编程
    Dubbo中的Triple协议和应用级服务发现
    10.19QT作业
    线性表的插入、删除和查询操作
    43、Flink之Hive 读写及详细验证示例
  • 原文地址：https://blog.csdn.net/weixin_44997802/article/details/134353947