数据结构笔记：伸展树、B树、红黑树

概述

伸展树
B树
红黑树

小试牛刀

伸展树利用了实际问题中数据访问的何种特点
A. massiveness 大量性
B. locality 局部性
C. holisticity 整体性
D. diversity 多样性

伸展树：逐层伸展

局部性：

逐层伸展

最坏情况：

伸展树：双层伸展

子孙异侧：

子孙同侧：

折叠效果：

分摊性能：

最后一步：

伸展树：算法实现

查找算法：

template <typename T> BinNodePosi<T>& Splay<T>::search( const T& e ) { //在伸展树中查找e
   BinNodePosi<T> p = BST<T>::search( e ); //按BST标准算法查找
   _root = p ? splay(p) : _hot ? splay(_hot) : NULL;  //无论成功、失败、树空，被访问的节点将伸展至根
   return _root;
} //与其它BST不同，无论如何，_root都指向最后被访问的节点

插入算法：

template <typename T> BinNodePosi<T> Splay<T>::insert( const T& e ) { //将关键码e插入伸展树中
   if ( !_root ) { _size = 1; return _root = new BinNode<T>( e ); } //原树为空
   BinNodePosi<T> t = search( e );
   if ( e == t->data ) return t; //目标节点t若存在，伸展至根
   if ( t->data < e ) //在右侧嫁接
      { t->parent = _root = new BinNode<T>( e, NULL, t, t->rc ); t->rc = NULL; }
   else //在左侧嫁接
      { t->parent = _root = new BinNode<T>( e, NULL, t->lc, t ); t->lc = NULL; }
   _size++; t->updateHeightAbove(); return _root; //更新规模及高度，报告插入成功
} //无论e是否存在于原树中，返回时总有_root->data == e

删除算法：