devbox
酷酷是懒虫
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法数据结构（三十三）----有序表_数据结构有序表

作者：酷酷是懒虫 | 2024-07-20 23:11:18

赞

踩

数据结构有序表

 二叉树

定义：二叉树是每个结点最多有两个子树的树结构。
性质：
    1）二叉树的每个结点至多只有二棵子树(不存在度大于2的结点
    2）二叉树的子树有左右之分，次序不能颠倒
    3）二叉树的第i层至多有2^{i-1}个结点
    4）深度为k的二叉树至多有2^k-1个结点

 满二叉树

定义：一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。
性质：每一层上的节点数都是最大节点数

 完全二叉树

定义：一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点
性质：
    1）具有n个节点的完全二叉树的深度为log2(n+1)
    2）深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点

 线索二叉树

定义：利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）

 哈夫曼树（最优二叉树）

定义：哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近

 二叉搜索树/二叉排序树/二叉查找树

定义：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

 平衡二叉树

定义：平衡二叉树又称AVL树，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1

 伸展树

定义：伸展树是在查询或删除时对二叉查找树进行伸展操作，并保证从空树开始任意连续M次对树的操作最多花费O(MlogN)的时间。对二叉查找树进行伸展的意义是将访问路径上的节点尽可能的推向离树根最近的地方，有益于在下次访问时用时最少。通常一个节点被访问时，很可能不久会被再次访问。

红黑树

定义：是一种自平衡二叉查找树，其性质决定了最大一条路径节点个数不会超过最小的两倍
1）性质1. 节点是红色或黑色。
2）性质2. 根节点是黑色。
3）性质3 每个叶节点（NIL节点，空节点）是黑色的。
4）性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5）性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

 B树

定义：二叉搜索树
性质：
    1）所有非叶子结点至多拥有两个儿子（Left和Right）；
    2）所有结点存储一个关键字；
    3）非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

 B-树

定义：是一种多路搜索树

 B+树

定义：B+树是B-树的变体，也是一种多路搜索树，所有关键字都在叶子结点出现

 B*树

定义：是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，节点分裂优先给兄弟节点

 搜索二叉树

搜索二叉树一定要说明以什么标准来排序

经典的搜索二叉树，树上没有重复的用来排序的key值

如果有重复节点的需求，可以在一个节点内部增加数据项

 搜索二叉树查询key（查询某个key存在还是不存在）

1）如果当前节点的value==key，返回true

2）如果当前节点的value<key，当前节点向左移动

3）如果当前节点的value>key，当前节点向右移动

4）如果当前节点变成null，返回false

 搜索二叉树插入新的key

和查询过程一样，但当前节点滑到空的时候，就插入在这里

 搜索二叉树删除key

0）先找到key所在的节点

1）如果该节点没有左孩子、没有右孩子，直接删除即可

2）如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点

3）如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点

4）如果该节点有左孩子、有右孩子，用该节点后继节点顶替该节点

 搜索二叉树特别不讲究

1）基础的搜索二叉树，添加、删除时候不照顾平衡性

2）数据状况很差时，性能就很差

给搜索二叉树引入两个动作：左旋、右旋

 

  AVL树、SB树、红黑树的共性：给搜索二叉树引入两个动作：左旋、右旋，调整平衡性

1）都是搜索二叉树

2）插入、删除、查询（一切查询）搜索二叉树怎么做，这些结构都这么做

3）使用调整的基本动作都只有左旋、右旋

4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查

5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)

 AVL树、SB树、红黑树的不同

1）平衡性的约束不同

AVL树最严格、SB树稍宽松、红黑树最宽松

2）插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整。各自的平衡性调整所使用的动作都是左旋或者右旋

 AVL树

1）最严格的平衡性，任何节点左树高度和右树高度差不超过1

2）往上沿途检查每个节点时，都去检查四种违规情况：LL、RR、LR、RL

3）不同情况虽然看起来复杂，但是核心点是：

LL（做一次右旋）、RR（做一次左旋）

LR和RL（利用旋转让底层那个上到顶部）

  1. //定义结构
  2. public static class AVLNode<K extends Comparable<K>, V> {
  3. 		public K k;
  4. 		public V v;
  5. 		public AVLNode<K, V> l;
  6. 		public AVLNode<K, V> r;
  7. 		public int h;
  8.  
  9. 		public AVLNode(K key, V value) {
  10. 			k = key;
  11. 			v = value;
  12. 			h = 1;
  13. 		}
  14. 	}
  15.  
  16. 	public static class AVLTreeMap<K extends Comparable<K>, V> {
  17. 		private AVLNode<K, V> root;
  18. 		private int size;
  19.  
  20. 		public AVLTreeMap() {
  21. 			root = null;
  22. 			size = 0;
  23. 		}
  24.         
  25.         //右旋
  26. 		private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {
  27. 			AVLNode<K, V> left = cur.l;
  28. 			cur.l = left.r;
  29. 			left.r = cur;
  30. 			cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
  31. 			left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;
  32. 			return left;
  33. 		}
  34.  
  35.         //左旋
  36. 		private AVLNode<K, V> leftRotate(AVLNode<K, V> cur) {
  37. 			AVLNode<K, V> right = cur.r;
  38. 			cur.r = right.l;
  39. 			right.l = cur;
  40. 			cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;
  41. 			right.h = Math.max((right.l != null ? right.l.h : 0), (right.r != null ? right.r.h : 0)) + 1;
  42. 			return right;
  43. 		}
  44.  
  45.         //调整平衡性
  46. 		private AVLNode<K, V> maintain(AVLNode<K, V> cur) {
  47. 			if (cur == null) {
  48. 				return null;
  49. 			}
  50. 			int leftHeight = cur.l != null ? cur.l.h : 0;
  51. 			int rightHeight = cur.r != null ? cur.r.h : 0;
  52. 			if (Math.abs(leftHeight - rightHeight) > 1) {
  53. 				if (leftHeight > rightHeight) {
  54. 					int leftLeftHeight = cur.l != null && cur.l.l != null ? cur.l.l.h : 0;
  55. 					int leftRightHeight = cur.l != null && cur.l.r != null ? cur.l.r.h : 0;
  56. 					if (leftLeftHeight >= leftRightHeight) {
  57. 						cur = rightRotate(cur);
  58. 					} else {
  59. 						cur.l = leftRotate(cur.l);
  60. 						cur = rightRotate(cur);
  61. 					}
  62. 				} else {
  63. 					int rightLeftHeight = cur.r != null && cur.r.l != null ? cur.r.l.h : 0;
  64. 					int rightRightHeight = cur.r != null && cur.r.r != null ? cur.r.r.h : 0;
  65. 					if (rightRightHeight >= rightLeftHeight) {
  66. 						cur = leftRotate(cur);
  67. 					} else {
  68. 						cur.r = rightRotate(cur.r);
  69. 						cur = leftRotate(cur);
  70. 					}
  71. 				}
  72. 			}
  73. 			return cur;
  74. 		}
  75.  
  76. 		private AVLNode<K, V> findLastIndex(K key) {
  77. 			AVLNode<K, V> pre = root;
  78. 			AVLNode<K, V> cur = root;
  79. 			while (cur != null) {
  80. 				pre = cur;
  81. 				if (key.compareTo(cur.k) == 0) {
  82. 					break;
  83. 				} else if (key.compareTo(cur.k) < 0) {
  84. 					cur = cur.l;
  85. 				} else {
  86. 					cur = cur.r;
  87. 				}
  88. 			}
  89. 			return pre;
  90. 		}
  91.  
  92. 		private AVLNode<K, V> findLastNoSmallIndex(K key) {
  93. 			AVLNode<K, V> ans = null;
  94. 			AVLNode<K, V> cur = root;
  95. 			while (cur != null) {
  96. 				if (key.compareTo(cur.k) == 0) {
  97. 					ans = cur;
  98. 					break;
  99. 				} else if (key.compareTo(cur.k) < 0) {
  100. 					ans = cur;
  101. 					cur = cur.l;
  102. 				} else {
  103. 					cur = cur.r;
  104. 				}
  105. 			}
  106. 			return ans;
  107. 		}
  108.  
  109. 		private AVLNode<K, V> findLastNoBigIndex(K key) {
  110. 			AVLNode<K, V> ans = null;
  111. 			AVLNode<K, V> cur = root;
  112. 			while (cur != null) {
  113. 				if (key.compareTo(cur.k) == 0) {
  114. 					ans = cur;
  115. 					break;
  116. 				} else if (key.compareTo(cur.k) < 0) {
  117. 					cur = cur.l;
  118. 				} else {
  119. 					ans = cur;
  120. 					cur = cur.r;
  121. 				}
  122. 			}
  123. 			return ans;
  124. 		}
  125.  
  126.         //添加节点
  127. 		private AVLNode<K, V> add(AVLNode<K, V> cur, K key, V value) {
  128. 			if (cur == null) {
  129. 				return new AVLNode<K, V>(key, value);
  130. 			} else {
  131. 				if (key.compareTo(cur.k) < 0) {
  132. 					cur.l = add(cur.l, key, value);
  133. 				} else {
  134. 					cur.r = add(cur.r, key, value);
  135. 				}
  136. 				cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;
  137. 				return maintain(cur);
  138. 			}
  139. 		}
  140.  
  141. 		// 在cur这棵树上，删掉key所代表的节点
  142. 		// 返回cur这棵树的新头部
  143. 		private AVLNode<K, V> delete(AVLNode<K, V> cur, K key) {
  144. 			if (key.compareTo(cur.k) > 0) {
  145. 				cur.r = delete(cur.r, key);
  146. 			} else if (key.compareTo(cur.k) < 0) {
  147. 				cur.l = delete(cur.l, key);
  148. 			} else {
  149. 				if (cur.l == null && cur.r == null) {
  150. 					cur = null;
  151. 				} else if (cur.l == null && cur.r != null) {
  152. 					cur = cur.r;
  153. 				} else if (cur.l != null && cur.r == null) {
  154. 					cur = cur.l;
  155. 				} else {
  156. 					AVLNode<K, V> des = cur.r;
  157. 					while (des.l != null) {
  158. 						des = des.l;
  159. 					}
  160. 					cur.r = delete(cur.r, des.k);
  161. 					des.l = cur.l;
  162. 					des.r = cur.r;
  163. 					cur = des;
  164. 				}
  165. 			}
  166. 			if (cur != null) {
  167. 				cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;
  168. 			}
  169. 			return maintain(cur);
  170. 		}
  171.  
  172. 		public int size() {
  173. 			return size;
  174. 		}
  175.  
  176.         //是否包含某个key
  177. 		public boolean containsKey(K key) {
  178. 			if (key == null) {
  179. 				return false;
  180. 			}
  181. 			AVLNode<K, V> lastNode = findLastIndex(key);
  182. 			return lastNode != null && key.compareTo(lastNode.k) == 0 ? true : false;
  183. 		}
  184.  
  185. 		public void put(K key, V value) {
  186. 			if (key == null) {
  187. 				return;
  188. 			}
  189. 			AVLNode<K, V> lastNode = findLastIndex(key);
  190. 			if (lastNode != null && key.compareTo(lastNode.k) == 0) {
  191. 				lastNode.v = value;
  192. 			} else {
  193. 				size++;
  194. 				root = add(root, key, value);
  195. 			}
  196. 		}
  197.  
  198. 		public void remove(K key) {
  199. 			if (key == null) {
  200. 				return;
  201. 			}
  202. 			if (containsKey(key)) {
  203. 				size--;
  204. 				root = delete(root, key);
  205. 			}
  206. 		}
  207.  
  208. 		public V get(K key) {
  209. 			if (key == null) {
  210. 				return null;
  211. 			}
  212. 			AVLNode<K, V> lastNode = findLastIndex(key);
  213. 			if (lastNode != null && key.compareTo(lastNode.k) == 0) {
  214. 				return lastNode.v;
  215. 			}
  216. 			return null;
  217. 		}
  218.  
  219. 		public K firstKey() {
  220. 			if (root == null) {
  221. 				return null;
  222. 			}
  223. 			AVLNode<K, V> cur = root;
  224. 			while (cur.l != null) {
  225. 				cur = cur.l;
  226. 			}
  227. 			return cur.k;
  228. 		}
  229.  
  230. 		public K lastKey() {
  231. 			if (root == null) {
  232. 				return null;
  233. 			}
  234. 			AVLNode<K, V> cur = root;
  235. 			while (cur.r != null) {
  236. 				cur = cur.r;
  237. 			}
  238. 			return cur.k;
  239. 		}
  240.  
  241. 		public K floorKey(K key) {
  242. 			if (key == null) {
  243. 				return null;
  244. 			}
  245. 			AVLNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
  246. 			return lastNoBigNode == null ? null : lastNoBigNode.k;
  247. 		}
  248.  
  249. 		public K ceilingKey(K key) {
  250. 			if (key == null) {
  251. 				return null;
  252. 			}
  253. 			AVLNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
  254. 			return lastNoSmallNode == null ? null : lastNoSmallNode.k;
  255. 		}
  256.  
  257. 	}

 SB树（size-balance-tree）

1）让每一个叔叔节点为头的数，节点个数都不少于其任何一个侄子节点

2）也是从底层被影响节点开始向上做路径每个节点检查

3）与AVL树非常像，也是四种违规类型：LL、RR、LR、RL

4）与AVL树非常像，核心点是：

LL（做一次右旋）、RR（做一次左旋）

LR和RL（利用旋转让底层那个上到顶部）

5）与AVL树不同的是，每轮经过调整后，谁的孩子发生变化了，谁就再查

 SB树在使用时候的改进

1）删除时候可以不用检查

2）就把平衡性的调整放在插入的时候

3）因为这种只要变就递归的特性，别的树没有

4）可以在节点上封装别的数据项，来增加功能 

  1. public static class SBTNode<K extends Comparable<K>, V> {
  2. 		public K key;
  3. 		public V value;
  4. 		public SBTNode<K, V> l;
  5. 		public SBTNode<K, V> r;
  6. 		public int size; // 不同的key的数量
  7.  
  8. 		public SBTNode(K key, V value) {
  9. 			this.key = key;
  10. 			this.value = value;
  11. 			size = 1;
  12. 		}
  13. 	}
  14.  
  15. 	public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
  16. 		private SBTNode<K, V> root;
  17.  
  18. 		private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
  19. 			SBTNode<K, V> leftNode = cur.l;
  20. 			cur.l = leftNode.r;
  21. 			leftNode.r = cur;
  22. 			leftNode.size = cur.size;
  23. 			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
  24. 			return leftNode;
  25. 		}
  26.  
  27. 		private SBTNode<K, V> leftRotate(SBTNode<K, V> cur) {
  28. 			SBTNode<K, V> rightNode = cur.r;
  29. 			cur.r = rightNode.l;
  30. 			rightNode.l = cur;
  31. 			rightNode.size = cur.size;
  32. 			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
  33. 			return rightNode;
  34. 		}
  35.  
  36. 		private SBTNode<K, V> maintain(SBTNode<K, V> cur) {
  37. 			if (cur == null) {
  38. 				return null;
  39. 			}
  40. 			int leftSize = cur.l != null ? cur.l.size : 0;
  41. 			int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;
  42. 			int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
  43. 			int rightSize = cur.r != null ? cur.r.size : 0;
  44. 			int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;
  45. 			int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
  46. 			if (leftLeftSize > rightSize) {
  47. 				cur = rightRotate(cur);
  48. 				cur.r = maintain(cur.r);
  49. 				cur = maintain(cur);
  50. 			} else if (leftRightSize > rightSize) {
  51. 				cur.l = leftRotate(cur.l);
  52. 				cur = rightRotate(cur);
  53. 				cur.l = maintain(cur.l);
  54. 				cur.r = maintain(cur.r);
  55. 				cur = maintain(cur);
  56. 			} else if (rightRightSize > leftSize) {
  57. 				cur = leftRotate(cur);
  58. 				cur.l = maintain(cur.l);
  59. 				cur = maintain(cur);
  60. 			} else if (rightLeftSize > leftSize) {
  61. 				cur.r = rightRotate(cur.r);
  62. 				cur = leftRotate(cur);
  63. 				cur.l = maintain(cur.l);
  64. 				cur.r = maintain(cur.r);
  65. 				cur = maintain(cur);
  66. 			}
  67. 			return cur;
  68. 		}
  69.  
  70. 		private SBTNode<K, V> findLastIndex(K key) {
  71. 			SBTNode<K, V> pre = root;
  72. 			SBTNode<K, V> cur = root;
  73. 			while (cur != null) {
  74. 				pre = cur;
  75. 				if (key.compareTo(cur.key) == 0) {
  76. 					break;
  77. 				} else if (key.compareTo(cur.key) < 0) {
  78. 					cur = cur.l;
  79. 				} else {
  80. 					cur = cur.r;
  81. 				}
  82. 			}
  83. 			return pre;
  84. 		}
  85.  
  86. 		private SBTNode<K, V> findLastNoSmallIndex(K key) {
  87. 			SBTNode<K, V> ans = null;
  88. 			SBTNode<K, V> cur = root;
  89. 			while (cur != null) {
  90. 				if (key.compareTo(cur.key) == 0) {
  91. 					ans = cur;
  92. 					break;
  93. 				} else if (key.compareTo(cur.key) < 0) {
  94. 					ans = cur;
  95. 					cur = cur.l;
  96. 				} else {
  97. 					cur = cur.r;
  98. 				}
  99. 			}
  100. 			return ans;
  101. 		}
  102.  
  103. 		private SBTNode<K, V> findLastNoBigIndex(K key) {
  104. 			SBTNode<K, V> ans = null;
  105. 			SBTNode<K, V> cur = root;
  106. 			while (cur != null) {
  107. 				if (key.compareTo(cur.key) == 0) {
  108. 					ans = cur;
  109. 					break;
  110. 				} else if (key.compareTo(cur.key) < 0) {
  111. 					cur = cur.l;
  112. 				} else {
  113. 					ans = cur;
  114. 					cur = cur.r;
  115. 				}
  116. 			}
  117. 			return ans;
  118. 		}
  119.  
  120. 		// 现在，以cur为头的树上，新增，加(key, value)这样的记录
  121. 		// 加完之后，会对cur做检查，该调整调整
  122. 		// 返回，调整完之后，整棵树的新头部
  123. 		private SBTNode<K, V> add(SBTNode<K, V> cur, K key, V value) {
  124. 			if (cur == null) {
  125. 				return new SBTNode<K, V>(key, value);
  126. 			} else {
  127. 				cur.size++;
  128. 				if (key.compareTo(cur.key) < 0) {
  129. 					cur.l = add(cur.l, key, value);
  130. 				} else {
  131. 					cur.r = add(cur.r, key, value);
  132. 				}
  133. 				return maintain(cur);
  134. 			}
  135. 		}
  136.  
  137. 		// 在cur这棵树上，删掉key所代表的节点
  138. 		// 返回cur这棵树的新头部
  139. 		private SBTNode<K, V> delete(SBTNode<K, V> cur, K key) {
  140. 			cur.size--;
  141. 			if (key.compareTo(cur.key) > 0) {
  142. 				cur.r = delete(cur.r, key);
  143. 			} else if (key.compareTo(cur.key) < 0) {
  144. 				cur.l = delete(cur.l, key);
  145. 			} else { // 当前要删掉cur
  146. 				if (cur.l == null && cur.r == null) {
  147. 					// free cur memory -> C++
  148. 					cur = null;
  149. 				} else if (cur.l == null && cur.r != null) {
  150. 					// free cur memory -> C++
  151. 					cur = cur.r;
  152. 				} else if (cur.l != null && cur.r == null) {
  153. 					// free cur memory -> C++
  154. 					cur = cur.l;
  155. 				} else { // 有左有右
  156. 					SBTNode<K, V> pre = null;
  157. 					SBTNode<K, V> des = cur.r;
  158. 					des.size--;
  159. 					while (des.l != null) {
  160. 						pre = des;
  161. 						des = des.l;
  162. 						des.size--;
  163. 					}
  164. 					if (pre != null) {
  165. 						pre.l = des.r;
  166. 						des.r = cur.r;
  167. 					}
  168. 					des.l = cur.l;
  169. 					des.size = des.l.size + (des.r == null ? 0 : des.r.size) + 1;
  170. 					// free cur memory -> C++
  171. 					cur = des;
  172. 				}
  173. 			}
  174. 			// cur = maintain(cur);
  175. 			return cur;
  176. 		}
  177.  
  178. 		private SBTNode<K, V> getIndex(SBTNode<K, V> cur, int kth) {
  179. 			if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
  180. 				return cur;
  181. 			} else if (kth <= (cur.l != null ? cur.l.size : 0)) {
  182. 				return getIndex(cur.l, kth);
  183. 			} else {
  184. 				return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
  185. 			}
  186. 		}
  187.  
  188. 		public int size() {
  189. 			return root == null ? 0 : root.size;
  190. 		}
  191.  
  192. 		public boolean containsKey(K key) {
  193. 			if (key == null) {
  194. 				throw new RuntimeException("invalid parameter.");
  195. 			}
  196. 			SBTNode<K, V> lastNode = findLastIndex(key);
  197. 			return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
  198. 		}
  199.  
  200. 		// （key，value） put -> 有序表 新增、改value
  201. 		public void put(K key, V value) {
  202. 			if (key == null) {
  203. 				throw new RuntimeException("invalid parameter.");
  204. 			}
  205. 			SBTNode<K, V> lastNode = findLastIndex(key);
  206. 			if (lastNode != null && key.compareTo(lastNode.key) == 0) {
  207. 				lastNode.value = value;
  208. 			} else {
  209. 				root = add(root, key, value);
  210. 			}
  211. 		}
  212.  
  213. 		public void remove(K key) {
  214. 			if (key == null) {
  215. 				throw new RuntimeException("invalid parameter.");
  216. 			}
  217. 			if (containsKey(key)) {
  218. 				root = delete(root, key);
  219. 			}
  220. 		}
  221.  
  222. 		public K getIndexKey(int index) {
  223. 			if (index < 0 || index >= this.size()) {
  224. 				throw new RuntimeException("invalid parameter.");
  225. 			}
  226. 			return getIndex(root, index + 1).key;
  227. 		}
  228.  
  229. 		public V getIndexValue(int index) {
  230. 			if (index < 0 || index >= this.size()) {
  231. 				throw new RuntimeException("invalid parameter.");
  232. 			}
  233. 			return getIndex(root, index + 1).value;
  234. 		}
  235.  
  236. 		public V get(K key) {
  237. 			if (key == null) {
  238. 				throw new RuntimeException("invalid parameter.");
  239. 			}
  240. 			SBTNode<K, V> lastNode = findLastIndex(key);
  241. 			if (lastNode != null && key.compareTo(lastNode.key) == 0) {
  242. 				return lastNode.value;
  243. 			} else {
  244. 				return null;
  245. 			}
  246. 		}
  247.  
  248. 		public K firstKey() {
  249. 			if (root == null) {
  250. 				return null;
  251. 			}
  252. 			SBTNode<K, V> cur = root;
  253. 			while (cur.l != null) {
  254. 				cur = cur.l;
  255. 			}
  256. 			return cur.key;
  257. 		}
  258.  
  259. 		public K lastKey() {
  260. 			if (root == null) {
  261. 				return null;
  262. 			}
  263. 			SBTNode<K, V> cur = root;
  264. 			while (cur.r != null) {
  265. 				cur = cur.r;
  266. 			}
  267. 			return cur.key;
  268. 		}
  269.  
  270. 		public K floorKey(K key) {
  271. 			if (key == null) {
  272. 				throw new RuntimeException("invalid parameter.");
  273. 			}
  274. 			SBTNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
  275. 			return lastNoBigNode == null ? null : lastNoBigNode.key;
  276. 		}
  277.  
  278. 		public K ceilingKey(K key) {
  279. 			if (key == null) {
  280. 				throw new RuntimeException("invalid parameter.");
  281. 			}
  282. 			SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
  283. 			return lastNoSmallNode == null ? null : lastNoSmallNode.key;
  284. 		}
  285.  
  286. 	}

聊聊红黑树

1）平衡性规定非常诡异

2）平衡性调整最为复杂

3）优点在于每次插入删除扰动较好，但是在今天看来这个优势也极其微弱了

原因：贪图扰动小的话，B+树、2-3-4树可能更好，还是那句话，到底图什么

4）除此之外，红黑树并不比AVL树、SB树、跳表更加优秀

5）面试上遇到，说清楚道理，不行就举报。。。

 跳表（skiplist）

1）结构上根本和搜索二叉树无关

2）利用随机概率分布来使得高层索引可以无视数据规律，做到整体性能优良

3）思想是所有有序表中最先进的

4）结构简单就是多级单链表

  1. // 跳表的节点定义
  2. 	public static class SkipListNode<K extends Comparable<K>, V> {
  3. 		public K key;
  4. 		public V val;
  5. 		public ArrayList<SkipListNode<K, V>> nextNodes;
  6.  
  7. 		public SkipListNode(K k, V v) {
  8. 			key = k;
  9. 			val = v;
  10. 			nextNodes = new ArrayList<SkipListNode<K, V>>();
  11. 		}
  12.  
  13. 		// 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束
  14. 		// 头(null), 头节点的null，认为最小
  15. 		// node  -> 头，node(null, "")  node.isKeyLess(!null)  true
  16. 		// node里面的key是否比otherKey小，true，不是false
  17. 		public boolean isKeyLess(K otherKey) {
  18. 			//  otherKey == null -> false 
  19. 			return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
  20. 		}
  21.  
  22. 		public boolean isKeyEqual(K otherKey) {
  23. 			return (key == null && otherKey == null)
  24. 					|| (key != null && otherKey != null && key.compareTo(otherKey) == 0);
  25. 		}
  26.  
  27. 	}
  28.  
  29. 	public static class SkipListMap<K extends Comparable<K>, V> {
  30. 		private static final double PROBABILITY = 0.5; // < 0.5 继续做，>=0.5 停
  31. 		private SkipListNode<K, V> head;
  32. 		private int size;
  33. 		private int maxLevel;
  34.  
  35. 		public SkipListMap() {
  36. 			head = new SkipListNode<K, V>(null, null);
  37. 			head.nextNodes.add(null); // 0
  38. 			size = 0;
  39. 			maxLevel = 0;
  40. 		}
  41.  
  42. 		// 从最高层开始，一路找下去，
  43. 		// 最终，找到第0层的<key的最右的节点
  44. 		private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
  45. 			if (key == null) {
  46. 				return null;
  47. 			}
  48. 			int level = maxLevel;
  49. 			SkipListNode<K, V> cur = head;
  50. 			while (level >= 0) { // 从上层跳下层
  51. 				//  cur  level  -> level-1
  52. 				cur = mostRightLessNodeInLevel(key, cur, level--);
  53. 			}
  54. 			return cur;
  55. 		}
  56.  
  57. 		// 在level层里，如何往右移动
  58. 		// 现在来到的节点是cur，来到了cur的level层，在level层上，找到<key最后一个节点并返回
  59. 		private SkipListNode<K, V> mostRightLessNodeInLevel(K key, 
  60. 				SkipListNode<K, V> cur, 
  61. 				int level) {
  62. 			SkipListNode<K, V> next = cur.nextNodes.get(level);
  63. 			while (next != null && next.isKeyLess(key)) {
  64. 				cur = next;
  65. 				next = cur.nextNodes.get(level);
  66. 			}
  67. 			return cur;
  68. 		}
  69.  
  70. 		public boolean containsKey(K key) {
  71. 			if (key == null) {
  72. 				return false;
  73. 			}
  74. 			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  75. 			SkipListNode<K, V> next = less.nextNodes.get(0);
  76. 			return next != null && next.isKeyEqual(key);
  77. 		}
  78.  
  79. 		// 新增、改value
  80. 		public void put(K key, V value) {
  81. 			if (key == null) {
  82. 				return;
  83. 			}
  84. 			// 0层上，最右一个，< key 的Node -> >key
  85. 			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  86. 			SkipListNode<K, V> find = less.nextNodes.get(0);
  87. 			if (find != null && find.isKeyEqual(key)) {
  88. 				find.val = value;
  89. 			} else { // find == null   8   7   9
  90. 				size++;
  91. 				int newNodeLevel = 0;
  92. 				while (Math.random() < PROBABILITY) {
  93. 					newNodeLevel++;
  94. 				}
  95. 				// newNodeLevel
  96. 				while (newNodeLevel > maxLevel) {
  97. 					head.nextNodes.add(null);
  98. 					maxLevel++;
  99. 				}
  100. 				SkipListNode<K, V> newNode = new SkipListNode<K, V>(key, value);
  101. 				for (int i = 0; i <= newNodeLevel; i++) {
  102. 					newNode.nextNodes.add(null);
  103. 				}
  104. 				int level = maxLevel;
  105. 				SkipListNode<K, V> pre = head;
  106. 				while (level >= 0) {
  107. 					// level 层中，找到最右的 < key 的节点
  108. 					pre = mostRightLessNodeInLevel(key, pre, level);
  109. 					if (level <= newNodeLevel) {
  110. 						newNode.nextNodes.set(level, pre.nextNodes.get(level));
  111. 						pre.nextNodes.set(level, newNode);
  112. 					}
  113. 					level--;
  114. 				}
  115. 			}
  116. 		}
  117.  
  118. 		public V get(K key) {
  119. 			if (key == null) {
  120. 				return null;
  121. 			}
  122. 			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  123. 			SkipListNode<K, V> next = less.nextNodes.get(0);
  124. 			return next != null && next.isKeyEqual(key) ? next.val : null;
  125. 		}
  126.  
  127. 		public void remove(K key) {
  128. 			if (containsKey(key)) {
  129. 				size--;
  130. 				int level = maxLevel;
  131. 				SkipListNode<K, V> pre = head;
  132. 				while (level >= 0) {
  133. 					pre = mostRightLessNodeInLevel(key, pre, level);
  134. 					SkipListNode<K, V> next = pre.nextNodes.get(level);
  135. 					// 1）在这一层中，pre下一个就是key
  136. 					// 2）在这一层中，pre的下一个key是>要删除key
  137. 					if (next != null && next.isKeyEqual(key)) {
  138. 						// free delete node memory -> C++
  139. 						// level : pre -> next(key) -> ...
  140. 						pre.nextNodes.set(level, next.nextNodes.get(level));
  141. 					}
  142. 					// 在level层只有一个节点了，就是默认节点head
  143. 					if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
  144. 						head.nextNodes.remove(level);
  145. 						maxLevel--;
  146. 					}
  147. 					level--;
  148. 				}
  149. 			}
  150. 		}
  151.  
  152. 		public K firstKey() {
  153. 			return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
  154. 		}
  155.  
  156. 		public K lastKey() {
  157. 			int level = maxLevel;
  158. 			SkipListNode<K, V> cur = head;
  159. 			while (level >= 0) {
  160. 				SkipListNode<K, V> next = cur.nextNodes.get(level);
  161. 				while (next != null) {
  162. 					cur = next;
  163. 					next = cur.nextNodes.get(level);
  164. 				}
  165. 				level--;
  166. 			}
  167. 			return cur.key;
  168. 		}
  169.  
  170. 		public K ceilingKey(K key) {
  171. 			if (key == null) {
  172. 				return null;
  173. 			}
  174. 			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  175. 			SkipListNode<K, V> next = less.nextNodes.get(0);
  176. 			return next != null ? next.key : null;
  177. 		}
  178.  
  179. 		public K floorKey(K key) {
  180. 			if (key == null) {
  181. 				return null;
  182. 			}
  183. 			SkipListNode<K, V> less = mostRightLessNodeInTree(key);
  184. 			SkipListNode<K, V> next = less.nextNodes.get(0);
  185. 			return next != null && next.isKeyEqual(key) ? next.key : less.key;
  186. 		}
  187.  
  188. 		public int size() {
  189. 			return size;
  190. 		}
  191.  
  192. 	}

有序表题目

题目一

 给定一个数组arr，和两个整数a和b（a<=b）

求arr中有多少个子数组，累加和在[a,b]这个范围上

返回达标的子数组数量

 

         使用这种方式构建有序表：每一个节点第一个数字代表value，排序就根据这个value进行。第二个数字表示，自己+左孩子+右孩子value个数。如图代表3有3个，6有两个，5有2个

        这种结构，即可以接收重复值，还可以很快的算出，大于或者小于某个值的个数。

 题目二

有一个滑动窗口（讲过的）：

1）L是滑动窗口最左位置、R是滑动窗口最右位置，一开始LR都在数组左侧

2）任何一步都可能R往右动，表示某个数进了窗口

3）任何一步都可能L往右动，表示某个数出了窗口

想知道每一个窗口状态的中位数

        与题目一相同的存储结构，剩下的就是R往右移，就往结构中加数据，L往右移就从结构总移出数据 

题目三

 设计一个结构包含如下两个方法：

void add(int index, int num)：把num加入到index位置

int get(int index) ：取出index位置的值

void remove(int index) ：把index位置上的值删除

要求三个方法时间复杂度O(logN)

 

        设计一种数据结构，按照自然序排序：第一个数据为节点的value，第二个数字，表示该节点下有几个节点。

        如图，节点按自然序排序，所以图中记录的数据原始数据为：3 3 7 5 6

改写有序表的题目核心点 

1）分析增加什么数据项可以支持题目

2）有序表一定要保持内部参与排序的key不重复

3）增加这个数据项了，在平衡性调整时，保证这个数据项也能更新正确

4）做到上面3点，剩下就是搜索二叉树怎么实现你想要的接口的问题了

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/858772
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号