我们知道，二叉查找树相对来说比较容易形成最坏的链表情况，所以前辈们想尽了各种优化策略，包括AVL，红黑，以及今天
要讲的Treap树。
Treap树算是一种简单的优化策略，这名字大家也能猜到，树和堆的合体，其实原理比较简单，在树中维护一个"优先级“，”优先级“
采用随机数的方法，但是”优先级“必须满足根堆的性质，当然是“大根堆”或者“小根堆”都无所谓，比如下面的一棵树：
从树中我们可以看到：
①：节点中的key满足“二叉查找树”。
②：节点中的“优先级”满足小根堆。
一：基本操作
1：定义
1 #region Treap树节点 2 ///3 /// Treap树 4 /// 5 ///6 /// 7 public class TreapNode 8 { 9 /// 10 /// 节点元素11 /// 12 public K key;13 14 ///15 /// 优先级（采用随机数）16 /// 17 public int priority;18 19 ///20 /// 节点中的附加值21 /// 22 public HashSetattach = new HashSet ();23 24 /// 25 /// 左节点26 /// 27 public TreapNodeleft;28 29 /// 30 /// 右节点31 /// 32 public TreapNoderight;33 34 public TreapNode() { }35 36 public TreapNode(K key, V value, TreapNode left, TreapNode right)37 {38 //KV键值对39 this.key = key;40 this.priority = new Random(DateTime.Now.Millisecond).Next(0,int.MaxValue);41 this.attach.Add(value);42 43 this.left = left;44 this.right = right;45 }46 }47 #endregion
节点里面定义了一个priority作为“堆定义”的旋转因子，因子采用“随机数“。
2：添加
首先我们知道各个节点的“优先级”是采用随机数的方法，那么就存在一个问题，当我们插入一个节点后，优先级不满足“堆定义"的
时候我们该怎么办，前辈说此时需要旋转，直到满足堆定义为止。
旋转有两种方式，如果大家玩转了AVL，那么对Treap中的旋转的理解轻而易举。
①： 左左情况旋转
从图中可以看出，当我们插入“节点12”的时候，此时“堆性质”遭到破坏，必须进行旋转，我们发现优先级是6
左左情况旋转，最终也就形成了我们需要的结果。
②： 右右情况旋转
既然理解了”左左情况旋转“，右右情况也是同样的道理，优先级中发现“6
1 #region 添加操作 2 ///3 /// 添加操作 4 /// 5 /// 6 /// 7 public void Add(K key, V value) 8 { 9 node = Add(key, value, node);10 }11 #endregion12 13 #region 添加操作14 ///15 /// 添加操作16 /// 17 /// 18 /// 19 /// 20 ///21 public TreapNode Add(K key, V value, TreapNode tree)22 {23 if (tree == null)24 tree = new TreapNode (key, value, null, null);25 26 //左子树27 if (key.CompareTo(tree.key) 0)40 {41 tree.right = Add(key, value, tree.right);42 43 //根据小根堆性质，需要”右右情况旋转”44 if (tree.right.priority
3:删除
跟普通的二叉查找树一样，删除结点存在三种情况。
①：叶子结点
跟普通查找树一样，直接释放本节点即可。
②：单孩子结点
跟普通查找树一样操作。
③：满孩子结点
其实在treap中删除满孩子结点有两种方式。
第一种：跟普通的二叉查找树一样，找到“右子树”的最左结点（15），拷贝元素的值，但不拷贝元素的优先级，然后在右子树中
删除“结点15”即可，最终效果如下图。
第二种：将”结点下旋“，直到该节点不是”满孩子的情况“，该赋null的赋null，该将孩子结点顶上的就顶上，如下图：
当然从理论上来说，第二种删除方法更合理，这里我写的就是第二种情况的代码。
1 #region 删除当前树中的节点 2 ///3 /// 删除当前树中的节点 4 /// 5 /// 6 ///7 public void Remove(K key, V value) 8 { 9 node = Remove(key, value, node);10 }11 #endregion12 13 #region 删除当前树中的节点14 /// 15 /// 删除当前树中的节点16 /// 17 /// 18 /// 19 ///20 public TreapNode Remove(K key, V value, TreapNode tree)21 {22 if (tree == null)23 return null;24 25 //左子树26 if (key.CompareTo(tree.key) 0)32 {33 tree.right = Remove(key, value, tree.right);34 }35 /*相等的情况*/36 if (key.CompareTo(tree.key) == 0)37 {38 //判断里面的HashSet是否有多值39 if (tree.attach.Count > 1)40 {41 //实现惰性删除42 tree.attach.Remove(value);43 }44 else45 {46 //有两个孩子的情况47 if (tree.left != null && tree.right != null)48 {49 //如果左孩子的优先级低就需要“左旋”50 if (tree.left.priority
4:总结
treap树在CURD中是期望的logN，由于我们加了”优先级“,所以会出现”链表“的情况几乎不存在，但是他的Add和Remove相比严格的
平衡二叉树有更少的旋转操作，可以说性能是在”普通二叉树“和”平衡二叉树“之间。
最后是总运行代码，不过这里我就不做测试了。
View Code
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace DataStruct 7 { 8 #region Treap树节点 9 ///10 /// Treap树 11 /// 12 ///13 /// 14 public class TreapNode 15 { 16 /// 17 /// 节点元素 18 /// 19 public K key; 20 21 ///22 /// 优先级（采用随机数） 23 /// 24 public int priority; 25 26 ///27 /// 节点中的附加值 28 /// 29 public HashSetattach = new HashSet (); 30 31 /// 32 /// 左节点 33 /// 34 public TreapNodeleft; 35 36 /// 37 /// 右节点 38 /// 39 public TreapNoderight; 40 41 public TreapNode() { } 42 43 public TreapNode(K key, V value, TreapNode left, TreapNode right) 44 { 45 //KV键值对 46 this.key = key; 47 this.priority = new Random(DateTime.Now.Millisecond).Next(0,int.MaxValue); 48 this.attach.Add(value); 49 50 this.left = left; 51 this.right = right; 52 } 53 } 54 #endregion 55 56 public class TreapTree where K : IComparable 57 { 58 public TreapNode node = null; 59 60 #region 添加操作 61 /// 62 /// 添加操作 63 /// 64 /// 65 /// 66 public void Add(K key, V value) 67 { 68 node = Add(key, value, node); 69 } 70 #endregion 71 72 #region 添加操作 73 ///74 /// 添加操作 75 /// 76 /// 77 /// 78 /// 79 ///80 public TreapNode Add(K key, V value, TreapNode tree) 81 { 82 if (tree == null) 83 tree = new TreapNode (key, value, null, null); 84 85 //左子树 86 if (key.CompareTo(tree.key) 0) 99 {100 tree.right = Add(key, value, tree.right);101 102 //根据小根堆性质，需要”右右情况旋转”103 if (tree.right.priority 119 /// 第一种：左左旋转（单旋转）120 /// 121 /// 122 /// 123 public TreapNode RotateLL(TreapNode node)124 {125 //top：需要作为顶级节点的元素126 var top = node.left;127 128 //先截断当前节点的左孩子129 node.left = top.right;130 131 //将当前节点作为temp的右孩子132 top.right = node;133 134 return top;135 }136 #endregion137 138 #region 第二种：右右旋转（单旋转）139 /// 140 /// 第二种：右右旋转（单旋转）141 /// 142 /// 143 ///144 public TreapNode RotateRR(TreapNode node)145 {146 //top：需要作为顶级节点的元素147 var top = node.right;148 149 //先截断当前节点的右孩子150 node.right = top.left;151 152 //将当前节点作为temp的右孩子153 top.left = node;154 155 return top;156 }157 #endregion158 159 #region 树的指定范围查找160 /// 161 /// 树的指定范围查找162 /// 163 /// 164 /// 165 ///166 public HashSet SearchRange(K min, K max)167 {168 HashSet hashSet = new HashSet ();169 170 hashSet = SearchRange(min, max, hashSet, node);171 172 return hashSet;173 }174 #endregion175 176 #region 树的指定范围查找177 /// 178 /// 树的指定范围查找179 /// 180 /// 181 /// 182 /// 183 ///184 public HashSet SearchRange(K min, K max, HashSet hashSet, TreapNode tree)185 {186 if (tree == null)187 return hashSet;188 189 //遍历左子树（寻找下界）190 if (min.CompareTo(tree.key) = 0)195 {196 //等于这种情况197 foreach (var item in tree.attach)198 hashSet.Add(item);199 }200 201 //遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）202 if (min.CompareTo(tree.key) > 0 || max.CompareTo(tree.key) > 0)203 SearchRange(min, max, hashSet, tree.right);204 205 return hashSet;206 }207 #endregion208 209 #region 找到当前树的最小节点210 /// 211 /// 找到当前树的最小节点212 /// 213 ///214 public TreapNode FindMin()215 {216 return FindMin(node);217 }218 #endregion219 220 #region 找到当前树的最小节点221 /// 222 /// 找到当前树的最小节点223 /// 224 /// 225 ///226 public TreapNode FindMin(TreapNode tree)227 {228 if (tree == null)229 return null;230 231 if (tree.left == null)232 return tree;233 234 return FindMin(tree.left);235 }236 #endregion237 238 #region 找到当前树的最大节点239 /// 240 /// 找到当前树的最大节点241 /// 242 ///243 public TreapNode FindMax()244 {245 return FindMin(node);246 }247 #endregion248 249 #region 找到当前树的最大节点250 /// 251 /// 找到当前树的最大节点252 /// 253 /// 254 ///255 public TreapNode FindMax(TreapNode tree)256 {257 if (tree == null)258 return null;259 260 if (tree.right == null)261 return tree;262 263 return FindMax(tree.right);264 }265 #endregion266 267 #region 删除当前树中的节点268 /// 269 /// 删除当前树中的节点270 /// 271 /// 272 ///273 public void Remove(K key, V value)274 {275 node = Remove(key, value, node);276 }277 #endregion278 279 #region 删除当前树中的节点280 /// 281 /// 删除当前树中的节点282 /// 283 /// 284 /// 285 ///286 public TreapNode Remove(K key, V value, TreapNode tree)287 {288 if (tree == null)289 return null;290 291 //左子树292 if (key.CompareTo(tree.key) 0)298 {299 tree.right = Remove(key, value, tree.right);300 }301 /*相等的情况*/302 if (key.CompareTo(tree.key) == 0)303 {304 //判断里面的HashSet是否有多值305 if (tree.attach.Count > 1)306 {307 //实现惰性删除308 tree.attach.Remove(value);309 }310 else311 {312 //有两个孩子的情况313 if (tree.left != null && tree.right != null)314 {315 //如果左孩子的优先级低就需要“左旋”316 if (tree.left.priority
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/1679/viewspace-2811521/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
