顺序统计树

在计算机科学，顺序统计树是二叉搜索树的变种。除了插入、查询和删除，这种数据结构还支持以下两种操作：选择树中最小元素和对树中的元素进行排名（rank）。这两种操作的平均时间复杂度是O(log n)。当所用数据结构是平衡二叉树时，这是最坏复杂度。

简介二叉搜索树，是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉搜索树；没有键值相等的节点。二叉搜索树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉搜索树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。顺序统计树是二叉搜索树的一种变体，最大的特点是能对树中的元素进行排名和基于顺序统计量对树中的元素进行选择，即使用选择算法。对于树中的每个节点，需要额外维护以这个节点为根的子树大小（该节点下点的个数）。通过改进顺序统计树，能够实现其他数据结构（例如， 维护节点的高度能实现AVL树， 维护节点颜色能实现红黑树）。 直接使用节点大小的信息，也能实现加权平衡树。

选择算法在计算机科学中，选择算法是一种在列表或数组中找到第k个最小数字的算法；这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种：最小、最大和中位数。已知存在O(n)（最坏情况下为线性时间）的选择算法，还有对于结构化数据可能有次线性的表现的算法；在极端的情况下，对于已排序数据是O(1)。选择是一些更复杂问题的子问题，如最近邻和最短路径问题。 许多选择算法是由排序算法推广而来，反之，一些排序算法可由反复应用选择算法推导出来。最简单的选择算法是通过遍历列表找到最小（或最大）的元素，在此过程中跟踪当前的最小（或最大）值。这中算法与选择排序有关。相反地，最困难的选择算法是寻找中位数，这必然需要n/2的空间。 事实上，一个专门的中位选择算法可用来构造一个一般选择算法，例如中位数的中位数。已知最好的选择算法是快速选择（quickselect），它与快速排序有关。和快速排序类似，它有渐进最佳的复杂度，但是最坏情况的复杂度较差。不过这可以通过调整基准（pivot）的选择来优化。

通过对列表或数组的排序，然后选择所需的元素，选择算法可以规约为排序算法。这种方法对于选择单个元素是低效的，但需要从数组中做出很多选择时是高效的。在这种情况下，仅仅需要一个起初一个代价昂贵的排序，紧接着就是各种便宜的选择操作了 – 对于数组而言是 O(1)。尽管对于链表而言，即使排序后，选择操作也需要 O(n)，这是由于缺乏随机访问造成的。通常的，排序需要耗费 O(n log n) 的时间，其中n是列表的长度，尽管对于非比较算法而言可能更低一些，如基数排序和计数排序。

相比将整个列表或数组进行排序，还可以用偏排序来选择第k小或第k大的元素。第k小的（第 k 大的) 也就是偏排序后列表中最大的 (最小的) 那个 – 这在数组中会耗费 O(1) 来访问，在链表中会耗费 O(k)。

红黑查找树与加权平衡树红黑查找树就是一种平衡的二叉查找树。一棵二叉查找树如果满足下列性质，则称为红黑树：

(1)每个结点或是红色的，或是黑色的(增加一位表示颜色的存储位)；

(2)每个叶结点(空指针NIL)是黑色的；

(3)如果一个结点是红色的，则它的儿子应是黑色的；

(4)从任一给定结点到其子孙叶结点的每条简单路径上都具有相同个数的黑结点1。

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

加权平衡树是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左右子树的大小保持着某种内在联系。不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的有用数据，也就是说，可以得到一个大小为n的集合下的最大元素或者决定一个顺序结构下一个元素的索引。加权平衡树在函数程序语言社区下面非常受欢迎以及被用来实现MIT Scheme的集合和映射结构还有Haskell语言的实现。

代码实现#include #include #include #include #include #include #include #include #include using namespace std;enum COLOR { RED, BLACK };struct Node { int key; COLOR color; Node* p; Node* left; Node* right; int size; Node(int k, COLOR c = RED, Node* parent = nullptr, Node* l = nullptr, Node* r = nullptr,int s = 1) :key(k), color(c), p(parent), left(l), right(r),size(s) {}};class Tree { friend ostream& operatorright; Node* p = n->p; if (p) { if (p->right == n) p->right = r; else p->left = r; } else root = r; r->p = p; n->right = r->left; if (n->right) n->right->p = n; r->left = n; n->p = r; //修改size值以维护 r->size = n->size; n->size = (n->left ? n->left->size : 0) + (n->right ? n->right->size: 0) + 1; } void rightR(Node* n) { if (!n || !n->left) { return; } Node* l = n->left; Node* p = n->p; if (p) { if (p->left == n) p->left = l; else p->right = l; } else root = l; l->p = p; n->left = l->right; if (n->left) n->left->p = n; l->right = n; n->p = l; //修改size值以维护 l->size = n->size; n->size = (n->left ? n->left->size : 0) + (n->right ? n->right->size : 0) + 1; } void keep(Node* tokeep) { while (tokeep->p && tokeep->p->color == RED) { if (tokeep->p->p->left == tokeep->p) {//其父为左孩子 Node* father = tokeep->p; Node* uncle = father->p->right; if (uncle && uncle->color == RED) { father->color = BLACK; uncle->color = BLACK; father->p->color = RED; tokeep = father->p; } else { if (tokeep == father->right) { leftR(father); tokeep = father; father = father->p; } father->color = BLACK; father->p->color = RED; rightR(father->p); } } else { Node* father = tokeep->p; Node* uncle = father->p->left; if (uncle && uncle->color == RED) { uncle->color = BLACK; father->color = BLACK; father->p->color = RED; tokeep = father->p; } else { if (tokeep == father->left) { rightR(father); tokeep = father; father = father->p; } father->color = BLACK; father->p->color = RED; leftR(father->p); } } } root->color = BLACK; } ostream& pr(ostream& o, Node* r) const { if (!r) return o; o left); o right); o left; } return res; } Node* getNext(Node* t) { if (t && t->right) { return getMin(t->right); } else { while (t && t->p && t->p->left == t) { t = t->p; } if (t && t->p) return t->p; else return nullptr; } } void dkeep(Node* x, Node* px) { while (x != root && (!x || x->color == BLACK)) { if (x == px->left) { Node* w = px->right; if (w->color == RED) { w->color = BLACK; px->color = RED; leftR(px); w = px->right; } if ((!w->left || w->left->color == BLACK) && (!w->right || w->right->color == BLACK)) { w->color = RED; x = px; px = px->p; } else { if (!w->right || w->right->color == BLACK) { w->color = RED; w->left->color = BLACK; rightR(w); w = px->right; } w->color = px->color; px->color = BLACK; w->right->color = BLACK; leftR(px); x = root; } } else { Node* w = px->left; if (w->color == RED) { w->color = BLACK; px->color = RED; rightR(px); w = px->left; } if ((!w->left || w->left->color == BLACK) && (!w->right || w->right->color == BLACK)) { w->color = RED; x = px; px = px->p; } else { if (!w->left || w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; leftR(w); w = px->left; } w->color = px->color; px->color = BLACK; w->left->color = BLACK; rightR(px); x = root; } } } x->color = BLACK; } void clear(Node* root) { if (!root) return; clear(root->right); clear(root->left); delete root; } int findith(Node* root,int i) const { int l = root->left ? root->left->size:0; int s = l + 1; if (s == i) return root->key; else if (s > i) return findith(root->left, i); else return findith(root->right, i - s); } int findth(Node* root, int key,int sum = 0) const { if (!root) return sum + 1; int l = (root->left ? root->left->size : 0)+1; if (root->key == key) return l +sum; if (root->key right, key, sum + l); else return findth(root->left, key, sum); }public: Tree(Node* r = nullptr) :root(r) {} void insert(int key) { Node* tr = root; Node* ti = nullptr; while (tr) { ++(tr->size); ti = tr; if (tr->key right; else tr = tr->left; } if (!ti) root = new Node(key, BLACK); else { Node* tokeep = new Node(key, RED, ti); if (ti->key right = tokeep; else ti->left = tokeep; keep(tokeep); } } bool find(int key) const { return getKey(key) != nullptr; } void remove(int key) { Node* r = getKey(key); int color; Node* x = nullptr; Node* px = nullptr; if (!r) return; color = r->color; if (!r->left && !r->right) { x = nullptr; px = r->p; if (!px) { root = nullptr;// free(r); delete r; return; } else { if (px->left == r) { px->left = x; } else { px->right = x; } } } else if (!r->left) { x = r->right; px = r->p; if (!px) { root = x; } else { if (px->right == r) { px->right = x; } else { px->left = x; } } x->p = px; } else if (!r->right) { x = r->left; px = r->p; if (!px) { root = x; } else { if (px->right == r) { px->right = x; } else { px->left = x; } } x->p = px; } else { Node* nr = getMin(r->right); //nr->left==nullptr color = nr->color; // nr->p != nullptr //修改size以维护size nr->size = r->size; x = nr->right; px = nr->p; if (px->left == nr) { px->left = x; } else { px->right = x; } if (x) { x->p = px; } if (px == r) px = nr; if (!r->p) { root = nr; } else if (r->p->left == r) { r->p->left = nr; } else { r->p->right = nr; } nr->p = r->p; nr->left = r->left; nr->left->p = nr; nr->right = r->right; if (nr->right) nr->right->p = nr; }// free(r); delete r; //修改以维护size值 Node* tmppx = px; while (tmppx) { --(tmppx->size); tmppx = tmppx->p; } if (color == BLACK) { dkeep(x, px); } } ostream& printsize(ostream& o) const{ mr(o,root)