(BST&AVL&红黑树简单介绍)
前言：
节主要是给出BST，AVL和红黑树的C++代码，方便自己以后的查阅，其代码依旧是data structures and algorithm analysis in c++ (second edition)一书的作者所给，关于这3中二叉树在前面的博文算法设计和数据结构学习_4(《数据结构和问题求解》part4笔记)中已经有所介绍。这里不会去详细介绍它们的实现和规则，一是因为这方面的介绍性资料超非常多，另外这3种树的难点都在插入和删除部分，其规则本身并不多，但是要用文字和图形解释其实还蛮耗时的。所以，我们在看教程时，主要是要抓住这几种树的思想，然后对照对应的代码来看就ok了，能把代码看懂基本也就理解这些树的本质了。
BST& AVL树：
BST即二叉搜索树，它只需满足A节点左子树的值都小于A的值，右子树的值都大于A节点的值。其插入过程是依照它的属性值依次插入，删除过程分2种情况，如果是叶子节点，直接删除，如果是非叶子节点，则删除后将它的左子树中的最大节点填补，如果左子树为空，则用右子树中的最小节点填补。
AVL树的构造过程中有下面四种情况需要调整，有可能只需旋转一次，有可能需要旋转2次。
1. 单向右旋转（不平衡节点）平衡处理：
当在左子树上插入左节点，使平衡因子由1增加至2时。
2. 单向左旋转（不平衡节点）平衡处理：
当在右子树上插入右节点，使平衡因子由-1增加至-2时。
3. 双向旋转（先左旋转不平衡节点左孩子，然后右旋转不平衡节点）平衡处理：
当在左子树上插入右节点，使平衡因子有1增加到2时。
4. 双向旋转(先右旋转不平衡节点右孩子，然后左旋转不平衡节点)平衡处理：
当在右子树上插入左节点，使平衡因子由-1增加至-2时。
BST类实现的code如下(AVL类似)：
BinarySearchTree.h:
#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_ #include "Wrapper.h" template <class Comparable>
class BinarySearchTree; template <class Comparable>
class BinarySearchTreeWithRank; template <class Comparable>
class BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
int size; BinaryNode( const Comparable & theElement, BinaryNode *lt,
BinaryNode *rt, int sz = 1 )
: element( theElement ), left( lt ), right( rt ), size( sz ) { } friend class BinarySearchTree<Comparable>;
friend class BinarySearchTreeWithRank<Comparable>;
}; // BinarySearchTree class
//
// CONSTRUCTION: with no parameters or another BinarySearchTree.
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// void removeMin( ) --> Remove smallest item
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert, remove, and removeMin if warranted template <class Comparable>
class BinarySearchTree
{
public:
BinarySearchTree( );
BinarySearchTree( const BinarySearchTree & rhs );
virtual ~BinarySearchTree( ); Cref<Comparable> findMin( ) const;
Cref<Comparable> findMax( ) const;
Cref<Comparable> find( const Comparable & x ) const;
bool isEmpty( ) const; void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x );
void removeMin( ); const BinarySearchTree & operator=( const BinarySearchTree & rhs ); typedef BinaryNode<Comparable> Node; protected:
Node *root; Cref<Comparable> elementAt( Node *t ) const;
virtual void insert( const Comparable & x, Node * & t ) const;
virtual void remove( const Comparable & x, Node * & t ) const;
virtual void removeMin( Node * & t ) const;
Node * findMin( Node *t ) const;
Node * findMax( Node *t ) const;
Node * find( const Comparable & x, Node *t ) const;
void makeEmpty( Node * & t ) const;
Node * clone( Node *t ) const;
}; // BinarySearchTreeWithRank class.
//
// CONSTRUCTION: with no parameters or
// another BinarySearchTreeWithRank.
//
// ******************PUBLIC OPERATIONS*********************
// Comparable findKth( k )--> Return kth smallest item
// All other operations are inherited (but C++ requires
// some extra stuff). template <class Comparable>
class BinarySearchTreeWithRank : public BinarySearchTree<Comparable>
{
public:
Cref<Comparable> findKth( int k ) const; void insert( const Comparable & x )
{ BinarySearchTree<Comparable>::insert( x ); }
void remove( const Comparable & x )
{ BinarySearchTree<Comparable>::remove( x ); }
void removeMin( )
{ BinarySearchTree<Comparable>::removeMin( ); } typedef BinaryNode<Comparable> Node; private:
void insert( const Comparable & x, Node * & t ) const;
void remove( const Comparable & x, Node * & t ) const;
void removeMin( Node * & t ) const;
Node *findKth( int k, Node *t ) const; int treeSize( Node *t ) const
{ return t == NULL ? 0 : t->size; }
}; #include "BinarySearchTree.cpp"
#endif
BinarySearchTree.cpp:
#include "BinarySearchTree.h"
#include "Except.h" // Construct the tree.
template <class Comparable>
BinarySearchTree<Comparable>::BinarySearchTree( ) : root( NULL )
{
} // Copy constructor.
template <class Comparable>
BinarySearchTree<Comparable>::
BinarySearchTree( const BinarySearchTree<Comparable> & rhs ) : root( NULL )
{
*this = rhs;
} // Destructor for the tree.
template <class Comparable>
BinarySearchTree<Comparable>::~BinarySearchTree( )
{
makeEmpty( );
} // Insert x into the tree;
// Throws DuplicateItemException if x is already there.
template <class Comparable>
void BinarySearchTree<Comparable>::insert( const Comparable & x )
{
insert( x, root );
} // Remove x from the tree.
// Throws ItemNotFoundException if x is not in the tree.
template <class Comparable>
void BinarySearchTree<Comparable>::remove( const Comparable & x )
{
remove( x, root );
} // Remove minimum item from the tree.
// Throws UnderflowException if tree is empty.
template <class Comparable>
void BinarySearchTree<Comparable>::removeMin( )
{
removeMin( root );
} // Return the smallest item in the tree wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::findMin( ) const
{
return elementAt( findMin( root ) );
} // Return the largest item in the tree wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::findMax( ) const
{
return elementAt( findMax( root ) );
} // Find item x in the tree.
// Return the matching item wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::find( const Comparable & x ) const
{
return elementAt( find( x, root ) );
} // Make the tree logically empty.
template <class Comparable>
void BinarySearchTree<Comparable>::makeEmpty( )
{
makeEmpty( root );
} // Test if the tree is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool BinarySearchTree<Comparable>::isEmpty( ) const
{
return root == NULL;
} // Deep copy.
template <class Comparable>
const BinarySearchTree<Comparable> &
BinarySearchTree<Comparable>::
operator=( const BinarySearchTree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
} // Internal method to wrap the element field in node t inside a Cref object.
template <class Comparable>
Cref<Comparable> BinarySearchTree<Comparable>::elementAt( Node *t ) const
{
if( t == NULL )
return Cref<Comparable>( );
else
return Cref<Comparable>( t->element );
} // Internal method to insert into a subtree.
// x is the item to insert.
// t is the node that roots the tree.
// Set the new root.
// Throw DuplicateItemException if x is already in t.
template <class Comparable>
void BinarySearchTree<Comparable>::
insert( const Comparable & x, Node * & t ) const
{
if( t == NULL )
t = new Node( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
throw DuplicateItemException( );
} // Internal method to remove from a subtree.
// x is the item to remove.
// t is the node that roots the tree.
// Set the new root.
// Throw ItemNotFoundException is x is not in t.
template <class Comparable>
void BinarySearchTree<Comparable>::
remove( const Comparable & x, Node * & t ) const
{
if( t == NULL )
throw ItemNotFoundException( );
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
removeMin( t->right ); // Remove minimum
}
else
{
BinaryNode<Comparable> *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right; // Reroot t
delete oldNode; // delete old root
}
} // Internal method to remove minimum item from a subtree.
// t is the node that roots the tree.
// Set the new root.
// Throw UnderflowException if t is empty.
template <class Comparable>
void BinarySearchTree<Comparable>::removeMin( Node * & t ) const
{
if( t == NULL )
throw UnderflowException( );
else if( t->left != NULL )
removeMin( t->left );
else
{
Node *tmp = t;
t = t->right;
delete tmp;
}
} // Internal method to find the smallest item in a subtree t.
// Return node containing the smallest item.
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::findMin( Node *t ) const
{
if( t != NULL )
while( t->left != NULL )
t = t->left; return t;
} // Internal method to find the largest item in a subtree t.
// Return node containing the largest item.
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::findMax( Node *t ) const
{
if( t != NULL )
while( t->right != NULL )
t = t->right; return t;
} // Internal method to find an item in a subtree.
// x is item to search for.
// t is the node that roots the tree.
// Return node containing the matched item.
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::
find( const Comparable & x, Node *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return t; // Match return NULL; // Not found
} // Internal method to make subtree empty.
template <class Comparable>
void BinarySearchTree<Comparable>::makeEmpty( Node * & t ) const
{
if( t != NULL )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = NULL;
} // Internal method to clone subtree.
template <class Comparable>
BinaryNode<Comparable> * BinarySearchTree<Comparable>::clone( Node * t ) const
{
if( t == NULL )
return NULL;
else
return new Node( t->element, clone( t->left ), clone( t->right ), t->size );
} // Returns the kth smallest item in the tree.
// Throws ItemNotFoundException if k is out of range.
template <class Comparable>
Cref<Comparable> BinarySearchTreeWithRank<Comparable>::findKth( int k ) const
{
return elementAt( findKth( k, root ) );
} // Internal method to insert into a subtree.
// x is the item to insert.
// t is the node that roots the tree.
// Set the new root.
// Throw DuplicateItemException if x is already in t.
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::
insert( const Comparable & x, Node * & t ) const
{
if( t == NULL )
t = new Node( x, NULL, NULL, 0 );
else if( x < t->element )
insert( x, t->left );
else if( t->element < x )
insert( x, t->right );
else
throw DuplicateItemException( ); t->size++;
} // Internal method to remove from a subtree.
// x is the item to remove.
// t is the node that roots the tree.
// Set the new root.
// Throw ItemNotFoundException is x is not in t.
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::
remove( const Comparable & x, Node * & t ) const
{
if( t == NULL )
throw ItemNotFoundException( );
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
removeMin( t->right ); // Remove minimum
}
else
{
BinaryNode<Comparable> *oldNode = t;
t = ( t->left != NULL ) ? t->left : t->right; // Reroot t
delete oldNode; // delete old root
return;
} t->size--;
} // Internal method to remove minimum item from a subtree.
// t is the node that roots the tree.
// Set the new root.
// Throw UnderflowException if t is empty.
template <class Comparable>
void BinarySearchTreeWithRank<Comparable>::removeMin( Node * & t ) const
{
if( t == NULL )
throw UnderflowException( );
else if( t->left != NULL )
removeMin( t->left );
else
{
Node *tmp = t;
t = t->right;
delete tmp;
return;
} t->size--;
} // Internal method to find kth item in a subtree.
// k is the desired rank.
// t is the node that roots the tree.
template <class Comparable>
BinaryNode<Comparable> *
BinarySearchTreeWithRank<Comparable>::findKth( int k, Node * t ) const
{
if( t == NULL )
return NULL; int leftSize = treeSize( t->left ); if( k <= leftSize )
return findKth( k, t->left );
else if( k == leftSize + 1 )
return t;
else
return findKth( k - leftSize - 1, t->right );
}
红黑树：
3个连续的节点构成的树不可能是Red-Black树。
Log(n)基本上接近常量，比如说宇宙中原子的个数为10^69,取log后（10为底的情况）也只有69了，所以如果某个算法是log(n)的复杂度，那么这个算法是相当好的了。
静态查找表一般用数组实现，而动态查找表一般用树实现。查找表的实现还有键树，trie树，hash表等。
BST查找一定要从根节点开始，且BST的插入，查找算法一般都要用递归算法实现。可以从2-3树过渡到红黑树（红黑树的本质就是2-3-4树，比2-3树稍微复杂一点），2-3树是指每个节点的分支可以有2个或者3个。
红黑树中的红节点都对应于2-3-4树中大节点（指该节点内可能有2个或者3个数据）中的内部节点。
红黑树的查找性能和AVL相对，稍弱一点，但是实践表明，红黑树的插入过程中所需要进行的节点旋转次数比AVL树的要小。
2-3-4树是一颗B树，属于外部查找树。
红黑树的插入：
按照插入节点的值从红黑树的根节点依次往下插入。如果碰到其path上的节点左右节点都是红色的，则需要进行节点的颜色变换，颜色变换后如果出现了2个连续的红色节点，则需要进行旋转，旋转过程中当然也会有颜色变换。 直到找到需要插入的位置将其插入，因为插入的节点只能是红色的，所以又可能引起2个连续的红色节点，这时候仍然需要使用上面的规则进行调整。
红黑树的类实现code如下：
RedBlackTree.h:
#ifndef RED_BLACK_TREE_H_
#define RED_BLACK_TREE_H_ #include "Wrapper.h" // Red-black tree class.
//
// CONSTRUCTION: with negative infinity object
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws exceptions as warranted. template <class Comparable>
class RedBlackTree; template <class Comparable>
class RedBlackNode; template <class Comparable>
class RedBlackTree
{
public:
RedBlackTree( const Comparable & negInf );
RedBlackTree( const RedBlackTree & rhs );
~RedBlackTree( ); Cref<Comparable> findMin( ) const;
Cref<Comparable> findMax( ) const;
Cref<Comparable> find( const Comparable & x ) const;
bool isEmpty( ) const; void makeEmpty( );
void insert( const Comparable & x );
void remove( const Comparable & x ); enum { RED, BLACK }; const RedBlackTree & operator=( const RedBlackTree & rhs ); typedef RedBlackNode<Comparable> Node; private:
Node *header; // The tree header (contains negInf)
Node *nullNode; // Used in insert routine and its helpers (logically static)
Node *current;
Node *parent;
Node *grand;
Node *great; // Usual recursive stuff
void reclaimMemory( Node *t ) const;
RedBlackNode<Comparable> * clone( Node * t ) const; // Red-black tree manipulations
void handleReorient( const Comparable & item );
RedBlackNode<Comparable> * rotate( const Comparable & item,
Node *parent ) const;
void rotateWithLeftChild( Node * & k2 ) const;
void rotateWithRightChild( Node * & k1 ) const;
}; template <class Comparable>
class RedBlackNode
{
Comparable element;
RedBlackNode *left;
RedBlackNode *right;
int color; RedBlackNode( const Comparable & theElement = Comparable( ),
RedBlackNode *lt = NULL, RedBlackNode *rt = NULL,
int c = RedBlackTree<Comparable>::BLACK )
: element( theElement ), left( lt ), right( rt ), color( c ) { }
friend class RedBlackTree<Comparable>;
}; #include "RedBlackTree.cpp"
#endif
RedBlackTree.cpp:
#include "RedBlackTree.h"
#include "Except.h" // Construct the tree.
// negInf is a value less than or equal to all others.
template <class Comparable>
RedBlackTree<Comparable>::RedBlackTree( const Comparable & negInf )
{
nullNode = new Node;//空节点
nullNode->left = nullNode->right = nullNode;
header = new Node( negInf );//头节点，指向自己
header->left = header->right = nullNode;
} // Copy constructor.
template <class Comparable>
RedBlackTree<Comparable>::RedBlackTree( const RedBlackTree<Comparable> & rhs )
{
nullNode = new Node;
nullNode->left = nullNode->right = nullNode;
header = new Node( rhs.header->element );//只用rhs树中的头节点内容构造自己的头节点
header->left = header->right = nullNode;
*this = rhs;
} // Destroy the tree.
template <class Comparable>
RedBlackTree<Comparable>::~RedBlackTree( )
{
makeEmpty( );
delete nullNode;
delete header;
} // Insert item x into the tree.
// Throws DuplicateItemException if x is already present.
template <class Comparable>
void RedBlackTree<Comparable>::insert( const Comparable & x )
{
current = parent = grand = header;//一开始都定义为头节点
nullNode->element = x; while( current->element != x )//一般情况下刚调用该函数时这个whlie条件是满足的，因为此时的current->element为无穷小
{
great = grand; grand = parent; parent = current;//全部更新
current = x < current->element ? current->left : current->right; // Check if two red children; fix if so
if( current->left->color == RED && current->right->color == RED )//此时等价于2-3-4树中的4节点，因此需要将中间的节点往父节点方向上长
handleReorient( x );//往上生长节点，包括旋转和颜色变换
} // Insertion fails if already present
if( current != nullNode )
throw DuplicateItemException( );
current = new Node( x, nullNode, nullNode );//其实current永远是需要查找的下一个，有点先行的味道 // Attach to parent
if( x < parent->element )
parent->left = current;
else
parent->right = current;
handleReorient( x );
} // Remove item x from the tree.
// Not implemented in this version.
template <class Comparable>
void RedBlackTree<Comparable>::remove( const Comparable & x )
{
cout << "Sorry, remove unimplemented; " << x <<
" still present" << endl;
} // Find the smallest item the tree.
// Return the smallest item wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::findMin( ) const
{
if( isEmpty( ) )
return Cref<Comparable>( ); Node *itr = header->right; while( itr->left != nullNode )
itr = itr->left; return Cref<Comparable>( itr->element );
} // Find the largest item in the tree.
// Return the largest item wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::findMax( ) const
{
if( isEmpty( ) )
return Cref<Comparable>( ); Node *itr = header->right; while( itr->right != nullNode )
itr = itr->right; return Cref<Comparable>( itr->element );
} // Find item x in the tree.
// Return the matching item wrapped in a Cref object.
template <class Comparable>
Cref<Comparable> RedBlackTree<Comparable>::find( const Comparable & x ) const
{
nullNode->element = x;
Node *curr = header->right; for( ; ; )
{
if( x < curr->element )
curr = curr->left;
else if( curr->element < x )
curr = curr->right;
else if( curr != nullNode )
return Cref<Comparable>( curr->element );
else
return Cref<Comparable>( );
}
} // Make the tree logically empty.
template <class Comparable>
void RedBlackTree<Comparable>::makeEmpty( )
{
reclaimMemory( header->right );
header->right = nullNode;
} // Test if the tree is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool RedBlackTree<Comparable>::isEmpty( ) const
{
return header->right == nullNode;
} // Deep copy.
template <class Comparable>
const RedBlackTree<Comparable> &
RedBlackTree<Comparable>::operator=( const RedBlackTree<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
header->right = clone( rhs.header->right );
} return *this;
} // Internal method to clone subtree.
template <class Comparable>
RedBlackNode<Comparable> *
RedBlackTree<Comparable>::clone( Node * t ) const
{
if( t == t->left ) // Cannot test against nullNode!!!
return nullNode;
else
return new RedBlackNode<Comparable>( t->element, clone( t->left ),
clone( t->right ), t->color );
} // Internal routine that is called during an insertion
// if a node has two red children. Performs flip and rotations.
// item is the item being inserted.
template <class Comparable>
void RedBlackTree<Comparable>::handleReorient( const Comparable & item )
{
// Do the color flip
current->color = RED;
current->left->color = BLACK;//空节点也被认为是黑色的
current->right->color = BLACK; if( parent->color == RED ) // Have to rotate
{
grand->color = RED;
if( item < grand->element != item < parent->element )//这个条件表示item是grand的内子孙，因此需要2次调整
parent = rotate( item, grand ); // Start dbl rotate
current = rotate( item, great );
current->color = BLACK;
}
header->right->color = BLACK; // Make root black，head其实是根节点
} // Internal routine that performs a single or double rotation.
// Because the result is attached to the parent, there are four cases.
// Called by handleReorient.
// item is the item in handleReorient.
// parent is the parent of the root of the rotated subtree.
// Return the root of the rotated subtree.
template <class Comparable>
RedBlackNode<Comparable> *
RedBlackTree<Comparable>::rotate( const Comparable & item,
Node *theParent ) const
{
if( item < theParent->element )
{
item < theParent->left->element ?
rotateWithLeftChild( theParent->left ) : // LL
rotateWithRightChild( theParent->left ) ; // LR
return theParent->left;
}
else
{
item < theParent->right->element ?
rotateWithLeftChild( theParent->right ) : // RL
rotateWithRightChild( theParent->right ); // RR
return theParent->right;
}
} // Rotate binary tree node with left child.
template <class Comparable>
void RedBlackTree<Comparable>::
rotateWithLeftChild( Node * & k2 ) const
{
Node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;
} // Rotate binary tree node with right child.
template <class Comparable>
void RedBlackTree<Comparable>::
rotateWithRightChild( Node * & k1 ) const
{
Node *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
} // Internal method to reclaim internal nodes in subtree t.
template <class Comparable>
void RedBlackTree<Comparable>::reclaimMemory( Node *t ) const
{
if( t != t->left )
{
reclaimMemory( t->left );
reclaimMemory( t->right );
delete t;
}
}
参考资料：
data structures and algorithm analysis in c++ (second edition)，mark allen Weiss.
作者：tornadomeet 出处：http://www.cnblogs.com/tornadomeet 欢迎转载或分享，但请务必声明文章出处。