跳转至

ads个人笔记

先只整理维护一份文件,如果内容太多了再做文件管理。我的目的主要是构建自己能用的管理系统,不需要摘抄别人的内容,别人写了直接引用链接即可

001. AVL Trees

  • BST的左右子树高低差大于1时就不再是AVL,否则就是。
  • Trouble Maker & Trouble Finder: maker就是插入导致AVL tree不平衡的点,Finder就是离maker最近的首次出现不平衡的点,不平衡可以被分为LL,RR,LR,RL四类

    • LR表示的是 Trouble Maker 在 Trouble Finder 的 L 孩子节点的 R 孩子树中,其余的类似。
  • 重新调平的方式可以参考换根视角

002. Splay Trees 伸展树

为使 AVL 保持平衡,我们需要维护从根节点到 Trouble Maker 这条路径上所有点的平衡因子。而 Splay 则不再维护这些信息,这意味着我们无法保证 Splay 树的状态都是平衡的,但是我们希望它尽可能平衡。具体讲可以再多加理解一下