🦌鹿心雨的小窝🦌
🦌鹿心雨的小窝
coverPiccoverPic

【算法学习笔记 有序表 2】用 Rust 实现一个跳表

跳表rust算法与数据结构

🍳前言

继续是算法的有序表的学习笔记，这篇博客来实现一个跳表。😂虽然好像工作也用不上就是了，单纯想看看算法…

简单来说，跳表是一种具有多级随机生成索引的有序链表。跳表由多个有序链表组成，每个链表称为一层。最底层的链表包含所有节点，节点在加入时有概率加入高层的链表中，越高层的链表节点越稀疏，越低层越稠密。搜索时先从高层索引开始，找到右侧大于目标值的时候，再往下一层搜索。通过索引，跳表可以实现 O(logN)O(logN) 的时间复杂度下进行增删改查操作。同时它实现简单，没有类似平衡树复杂的调整操作。得益于这两点，跳表被广泛应用于各种场景中，例如 Redis、LevelDB。

🍟类型定义

和上次类似，除了实现基本的增删改查外，再实现序号和前驱后继的查询。

节点加入时，会获得一个随机的level作为节点的最高层数。为了实现多层的索引，跳表的每一个节点的后继指针这里使用一个数组来表示。

每一个跳表节点SkipListNode包含以下属性：

  1. key，用于排序的键值；
  2. level，节点索引的层数；
  3. count，插入该节点的数量；
  4. 'next`，每一层指向下一个节点的指针；
  5. span，每一层指针，跨越最底层节点的数量，左开右闭的区间，用于方便实现序号和前驱后继的查询。

对于跳表，为了做到 O(logN)O(logN) 的时间复杂度，跳表层数一般为数据量 2 为底（大概，具体看实现）的对数。

rust
  1. #[derive(Debug, Clone)]
  2. struct SkipListNode {
  3.     key: i32,
  4.     count: i32,
  5.     level: usize,
  6.     span: Vec<i32>,
  7.     next: Vec<OptionSkipListNodeRc>
  8. }
  10. type SkipListNodeRc = Rc<RefCell<SkipListNode>>;
  11. type OptionSkipListNodeRc = Option<
  12.     SkipListNodeRc
  13. >;
  15. struct SkipList {
  16.     head: SkipListNodeRc,
  17.     max_level: usize
  18. }
  20. impl SkipListNode {
  21.     fn new(key: i32, level: usize) -> Rc<RefCell<Self>> {
  22.         Rc::new(RefCell::new(Self {
  23.             key,
  24.             count: 1,
  25.             level,
  26.             next: vec![None; level + 1],
  27.             span: vec![0; level + 1],
  28.         }))
  29.     }
  30. }
  31. impl SkipList {
  32.     fn new(max_level: usize) -> Self {
  33.         SkipList { head: SkipListNode::new(i32::MIN, max_level), max_level }
  34.     }
  35. }

🌮搜索节点

搜索时先从高层索引开始，找到右侧大于目标值的时候，再往下一层搜索，直到到达最底层，右侧节点大于目标值或者不存在为止。如果节点和目标值相等就找到了。

rust
  1. fn find(mut node: SkipListNodeRc, level: usize, key: i32) -> OptionSkipListNodeRc {
  2.     loop {
  3.         let next = node.borrow().next[level].clone();
  4.         if let Some(next) = next {
  5.             if next.borrow().key < key {
  6.                 node = next;
  7.             } else {
  8.                 break;
  9.             }
  10.         } else {
  11.             break;
  12.         }
  13.     }
  14.     if level == 0 {
  15.         let next = node.borrow().next[level].clone();
  16.         if let Some(next) = next {
  17.             if next.borrow().key == key {
  18.                 return Some(next);
  19.             } else {
  20.                 return None;
  21.             }
  22.         } else {
  23.             return None;
  24.         }
  25.     }
  26.     return Self::find(node, level - 1, key)
  27. }

🍔加入节点

加入节点分为两种情况。当需要加入的节点存在时，只需要给它count加 1，更新左侧各层节点的跨越的距离span就好了。

rust
  1. fn insert(&mut self, key: i32) {
  2.     if Self::find(self.head.clone(), self.max_level, key).is_some() {
  3.         Self::add_count(self.head.clone(), self.max_level, key);
  4.     } else {
  5.         // ...
  6.     }
  7. }
  8. fn add_count(mut node: SkipListNodeRc, level: usize, key: i32) {
  9.     loop {
  10.         let next = node.borrow().next[level].clone();
  11.         if let Some(next) = next {
  12.             if next.borrow().key < key {
  13.                 node = next;
  14.             } else {
  15.                 break;
  16.             }
  17.         } else {
  18.             break;
  19.         }
  20.     }
  21.     if level == 0 {
  22.         let next = node.borrow().next[level].clone();
  23.         if let Some(next) = next {
  24.             next.borrow_mut().count += 1;
  25.         }
  26.     } else {
  27.         Self::add_count(node.clone(), level - 1, key);
  28.     }
  29.     node.borrow_mut().span[level] += 1;
  30. }

当节点不存在时，需要搜索到最底层适合添加节点的地方，插入节点，然后通过搜索时记录的向右移动距离更新左侧节点的span。

ts
  1. fn get_level(&self) -> usize {
  2.     let mut n = 0;
  3.     while rand::random::<bool>() && n < self.max_level {
  4.         n += 1;
  5.     }
  6.     n
  7. }
  8. // ...
  9. fn insert(&mut self, key: i32) {
  10.     if Self::find(self.head.clone(), self.max_level, key).is_some() {
  11.         Self::add_count(self.head.clone(), self.max_level, key);
  12.     } else {
  13.         let node_level = self.get_level();
  14.         let new_node = SkipListNode::new(key, node_level);
  15.         Self::insert_node(self.head.clone(), self.max_level, new_node);
  16.     }
  17. }
  18. fn insert_node(mut node: SkipListNodeRc, level: usize, new_node: SkipListNodeRc) -> i32 {
  19.     let mut left_offset = 0;
  20.     loop {
  21.         let next = node.borrow().next[level].clone();
  22.         if let Some(next) = next {
  23.             if next.borrow().key < new_node.borrow().key {
  24.                 left_offset += node.borrow().span[level];
  25.                 node = next;
  26.             } else {
  27.                 break;
  28.             }
  29.         } else {
  30.             break;
  31.         }
  32.     }
  33.     if level == 0 {
  34.         {
  35.             let mut new_node_borrow = new_node.borrow_mut();
  36.             new_node_borrow.next[level] = node.borrow().next[level].clone();
  37.             new_node_borrow.span[level] = if new_node_borrow.next[level].is_some() { new_node_borrow.next[level].clone().unwrap().borrow().count } else { 0 };
  38.         }
  39.         {
  40.             let mut node_boorow = node.borrow_mut();
  41.             node_boorow.next[level] = Some(new_node.clone());
  42.             node_boorow.span[level] = new_node.borrow().count;
  43.         }
  44.         left_offset
  45.     } else {
  46.         let down_offset = Self::insert_node(node.clone(), level - 1, new_node.clone());
  47.         if level > new_node.borrow().level {
  48.             node.borrow_mut().span[level] += 1;
  49.         } else {
  50.             {
  51.                 let mut new_node_borrow = new_node.borrow_mut();
  52.                 new_node_borrow.next[level] = node.borrow().next[level].clone();
  53.                 new_node_borrow.span[level] = node.borrow().span[level] - down_offset;
  54.             }
  55.             {
  56.                 let mut node_borrow = node.borrow_mut();
  57.                 node_borrow.next[level] = Some(new_node.clone());
  58.                 node_borrow.span[level] = down_offset + new_node.borrow().count;
  59.             }
  60.         }
  61.         left_offset + down_offset
  62.     }
  63. }

🥗删除节点

和添加节点相似，如果节点count大于 1，则减少count，否则移除节点，然后更新左侧的span。

ts
  1. fn remove(&mut self, key: i32) -> bool {
  2.     assert!(self.head.borrow().key != key || self.head.borrow().count != 1, "Cannot delete the head node!");
  3.     let node = Self::find(self.head.clone(), self.max_level, key);
  4.     match node {
  5.         None => false,
  6.         Some(x) => {
  7.             if x.borrow().count > 1 {
  8.                 Self::remove_count(self.head.clone(), self.max_level, key);
  9.             } else {
  10.                 Self::remove_node(self.head.clone(), self.max_level, x.clone());
  11.             }
  12.             true
  13.         }
  14.     }
  15. }
  16. fn remove_count(mut node: SkipListNodeRc, level: usize, key: i32) {
  17.     loop {
  18.         let next = node.borrow().next[level].clone();
  19.         if let Some(next) = next {
  20.             if next.borrow().key < key {
  21.                 node = next;
  22.             } else {
  23.                 break;
  24.             }
  25.         } else {
  26.             break;
  27.         }
  28.     }
  29.     if level == 0 {
  30.         let next = node.borrow().next[level].clone();
  31.         if let Some(next) = next {
  32.             next.borrow_mut().count -= 1;
  33.         }
  34.     } else {
  35.         Self::remove_count(node.clone(), level - 1, key);
  36.     }
  37.     node.borrow_mut().span[level] -= 1;
  38. }
  39. fn remove_node(mut node: SkipListNodeRc, level: usize, node_deleting: SkipListNodeRc) {
  40.     let node_deleting_key = node_deleting.borrow().key;
  41.     loop {
  42.         let next = node.borrow().next[level].clone();
  43.         if let Some(next) = next {
  44.             if next.borrow().key < node_deleting_key {
  45.                 node = next;
  46.             } else {
  47.                 break;
  48.             }
  49.         } else {
  50.             break;
  51.         }
  52.     }
  53.     if level > node_deleting.borrow().level {
  54.         node.borrow_mut().span[level] -= 1;
  55.     } else {
  56.         node.borrow_mut().next[level] = node_deleting.borrow().next[level].clone();
  57.         node.borrow_mut().span[level] += node_deleting.borrow().span[level] - 1;
  58.     }
  59.     if level > 0 {
  60.         Self::remove_node(node, level - 1, node_deleting);
  61.     }
  62. }

🥪排名的查询

rank函数获取传入的key在跳表中的排名，index函数获取传入排名在跳表中对应元素，这都可以通过跳表的span便捷计算遍历越过的节点数量来完成。

rust
  1. fn rank(&self, key: i32) -> i32 {
  2.     Self::rank_helper(self.head.clone(), self.max_level, key) + 1
  3. }
  4. fn rank_helper(mut node: SkipListNodeRc, level: usize, key: i32) -> i32 {
  5.     let mut left_offset = 0;
  6.     loop {
  7.         let next = node.borrow().next[level].clone();
  8.         if let Some(next) = next {
  9.             if next.borrow().key < key {
  10.                 left_offset += node.borrow().span[level];
  11.                 node = next;
  12.             } else {
  13.                 break;
  14.             }
  15.         } else {
  16.             break;
  17.         }
  18.     }
  19.     if level == 0 {
  20.         return left_offset;
  21.     } else {
  22.         return left_offset + Self::rank_helper(node, level - 1, key);
  23.     }
  24. }
  25. fn index(&self, idx: i32) -> i32 {
  26.     Self::index_helper(self.head.clone(), self.max_level, idx)
  27. }
  28. fn index_helper(mut node: SkipListNodeRc, level: usize, idx: i32) -> i32 {
  29.     if idx < 1 {
  30.         return i32::MIN
  31.     }
  32.     let mut acc = 0;
  33.     while node.clone().borrow().next[level].is_some() && acc < idx - node.borrow().span[level] {
  34.         acc += node.borrow().span[level];
  35.         let next_node = node.borrow().next[level].clone();
  36.         match next_node {
  37.             None => break,
  38.             Some(x) => {
  39.                 node = x;
  40.             }
  41.         }
  42.     }
  43.     if level == 0 {
  44.         let next_node = node.borrow().next[level].clone();
  45.         match next_node {
  46.             None => i32::MAX,
  47.             Some(x) => {
  48.                 x.borrow().key
  49.             }
  50.         }
  51.     } else {
  52.         Self::index_helper(node, level - 1, idx - acc)
  53.     }
  54. }

🧇前驱后继查询

前驱后继的查询，就是找出小于目标值的最大节点或者大于目标值的最小节点。这个查询在跳表中非常方便，找到最底层小于目标值的最右节点，就是前驱，它右侧第二个节点就是后继。

rust
  1. fn pre(&self, key: i32) -> i32 {
  2.     Self::pre_helper(self.head.clone(), self.max_level, key)
  3. }
  4. fn pre_helper(node: SkipListNodeRc, level: usize, key: i32) -> i32 {
  5.     let mut cur_node = Some(node.clone());
  6.     while cur_node.is_some() {
  7.         match cur_node.clone() {
  8.             None => {
  9.                 break;
  10.             },
  11.             Some(x) => {
  12.                 if x.borrow().next[level].is_some() && x.borrow().next[level].clone().unwrap().borrow().key < key {
  13.                     cur_node = x.borrow().next[level].clone();
  14.                 } else {
  15.                     break;
  16.                 }
  17.             }
  18.         }
  19.     }
  20.     if level == 0 {
  21.         let key = cur_node.clone().unwrap().borrow().key;
  22.         if key == i32::MIN {
  23.             i32::MIN
  24.         } else {
  25.             key
  26.         }
  27.     } else {
  28.         Self::pre_helper(cur_node.clone().unwrap(), level - 1, key)
  29.     }
  30. }
  31. fn next(&self, key: i32) -> i32 {
  32.     Self::next_helper(self.head.clone(), self.max_level, key)
  33. }
  34. fn next_helper(node: SkipListNodeRc, level: usize, key: i32) -> i32 {
  35.     let mut cur_node = Some(node.clone());
  36.     while cur_node.is_some() {
  37.         match cur_node.clone() {
  38.             None => {
  39.                 break;
  40.             },
  41.             Some(x) => {
  42.                 if x.borrow().next[level].is_some() && x.borrow().next[level].clone().unwrap().borrow().key < key {
  43.                     cur_node = x.borrow().next[level].clone();
  44.                 } else {
  45.                     break;
  46.                 }
  47.             }
  48.         }
  49.     }
  50.     if level == 0 {
  51.         let next = cur_node.clone().unwrap().borrow().next[0].clone();
  52.         match next {
  53.             None => i32::MAX,
  54.             Some(x) => {
  55.                 if x.borrow().key > key {
  56.                     x.borrow().key
  57.                 } else {
  58.                     let next_next = x.borrow().next[0].clone();
  59.                     match next_next {
  60.                         None => i32::MAX,
  61.                         Some(x) => {
  62.                             x.borrow().key
  63.                         }
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     } else {
  69.         Self::next_helper(cur_node.clone().unwrap(), level - 1, key)
  70.     }
  71. }

🥚结语

这里是在复习（学习）算法和数据结构和 rust 的程序员，这个博客使用 rust 构建了一个链表，包含了完整的增加、删除、查找，和排名、前驱后继的查询功能。

这篇博客用 rust 实现了一个 AVL 树，并且实现了对排序、前驱后继节点查询的操作。

参考：
【算法讲解149【扩展】有序表专题2-跳表】 https://www.bilibili.com/video/BV1HZ1jYMEt3/?share_source=copy_web&vd_source=a06db201a5f7fab5fe54f12bff164f84

上一篇：【算法学习笔记 有序表 1】用 Rust 实现了一个 AVL 树
0 条评论未登录用户
Ctrl or + Enter 评论
粤ICP备2023133136号
🌸 Run