- 浏览: 79173 次
文章分类
- 全部博客 (136)
- 我的技术资料收集 (98)
- 具体技术 (1)
- 的技术资料收集 (4)
- All Articles (1)
- 机器学习 Machine Learning (1)
- 网络编程 (1)
- java (2)
- ava (1)
- 零散技术 (1)
- C# (3)
- 技术资料收集 (1)
- CQRS (1)
- 数据库技术(MS SQL) (1)
- .Net微观世界 (1)
- Oracle SQL学习之路 (1)
- C/C++ (1)
- JS/JQ (1)
- Js封装的插件/实例/方法 (2)
- 敏捷个人 (2)
- Javascript (1)
- 程序设计---设计模式 (1)
- Bug (1)
- 未知分类 (1)
- 程序设计 (1)
- Sharepoint (1)
- Computer Graphic (1)
- IT产品 (1)
- [06]JS/jQuery (1)
- [07]Web开发 (1)
- .NET Solution (1)
- Android (3)
- 机器学习 (1)
- 系统框架设计 (1)
- Others (1)
- 算法 (1)
- 基于Oracle Logminer数据同步 (1)
- 网页设计 (1)
- 原创翻译 (1)
- EXTJS (1)
- Jqgrid (1)
- 云计算 (1)
最新评论
前言:
节主要是给出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.
算法设计和数据结构学习_4(《数据结构和问题求解》part4笔记)
发表评论
-
C#WebBrowser控件使用教程与技巧收集--苏飞收集 - sufeinet
2013-06-28 12:07 1016原帖地址:http://www.cnblogs.com/suf ... -
我要喷一个自认为很垃圾的网站架构 - 老赵【苏州】
2013-06-28 12:01 1082原帖地址:http://www.cnblogs.com/lao ... -
[翻译] Oracle Database 12c 新特性Multitenant - Cheney Shue
2013-06-28 11:43 589原帖地址:http://www.cnblogs.com/ese ... -
memcahd 命令操作详解 - 阿正-WEB
2013-06-28 11:37 430原帖地址:http://www.cnblogs.com/azh ... -
面向过程的代码符合大众的思维方式吗? - 史蒂芬.王
2013-06-27 10:28 552原帖地址:http://www.cnblogs.com/ste ... -
面向过程的代码符合大众的思维方式吗? - 史蒂芬.王
2013-06-27 10:28 524原帖地址:http://www.cnblogs.com/ste ... -
RPG游戏之组队测试 - zthua
2013-06-27 10:22 517原帖地址:http://www.cnblogs.com/zth ... -
IT人们给个建议 - SOUTHER
2013-06-26 14:06 486原帖地址:http://www.cnblogs.com/sou ... -
Java向前引用容易出错的地方 - 银河使者
2013-06-26 14:00 456原帖地址:http://www.cnblogs.com/nok ... -
使用Func<T1, T2, TResult> 委托返回匿名对象 - 灰身
2013-06-26 13:54 761原帖地址:http://www.cnblo ... -
【web前端面试题整理03】来看一点CSS相关的吧 - 叶小钗
2013-06-25 10:45 736原帖地址:http://www.cnblogs.com/yex ... -
Windows 8 动手实验系列教程 实验6:设置和首选项 - zigzagPath
2013-06-25 10:27 577原帖地址:http://www.cnblogs.com/zig ... -
闲聊可穿戴设备 - shawn.xie
2013-06-25 10:21 515原帖地址:http://www.cnblo ... -
CentOS下Mysql安装教程 - 小学徒V
2013-06-23 15:24 561原帖地址:http://www.cnblogs.com/xia ... -
vmware安装ubuntu12.04嵌套安装xen server(实现嵌套虚拟化) - skyme
2013-06-23 15:18 795原帖地址:http://www.cnblogs.com/sky ... -
之前专门为IE6、7开发的网站如何迁移到IE10及可能遇到的问题和相应解决方案汇总 - 海之澜
2013-06-23 15:12 901原帖地址:http://www.cnblogs.com/wuz ... -
Android学习笔记--解析XML之SAX - 承香墨影
2013-06-23 15:01 364原帖地址:http://www.cnblo ... -
SQL Server 性能优化之——T-SQL TVF和标量函数
2013-06-19 09:32 616原帖地址:http://www.cnblogs.com/Boy ... -
Nginx学习笔记(二) Nginx--connection&request
2013-06-19 09:26 605原帖地址:http://www.cnblogs.com/cod ... -
从郭美美霸气侧漏看项目管理之项目经理防身术
2013-06-19 09:20 461原帖地址:http://www.cnblogs.com/had ...
相关推荐
MFC界面,简要用几个数据结构实现了字典查找功能,可根据关键字查找
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...
数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出) (先进先出)...
这是一篇学习完邓俊辉老师的数据结构课程后,对课程中讲到的各种 数据结构 和 算法 的总结、回顾和归纳。 课程地址: 所有代码都是在: WINDOW系统下 VS2017 编写和运行的 数据结构 向量 向量的特点和构成 向量的常用...
数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出) (先进先出)...
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: ...然而,如果树的结构不平衡,最坏情况下时间复杂度可能退化为O(n),因此通常需要进行平衡操作(如红黑树、AVL树等)来保持树的平衡性。
教材上已经介绍过的动态查找数据结构包括:二叉搜索树(BST),平衡二叉树(AVL),红黑树(RBT),B-树。本题要求挑选一种已经学过的动态搜索树结构,设计并实现一个基于英语四级词汇的电子辞典软件。总体分析与...
由于过时 Java 小程序的激增令人沮丧,因此专门设计为 UPenn 的 CIS121 数据结构课程的工具。 此实现仅使用 Javascript 和 CSS(AngularJS、D3、CSS)运行。 为了绘制“漂亮”的树,我实现了 Reingold/Tilford 的...
算法和数据结构 数据结构 数组 堆栈和队列 数组出列 数组堆栈 链接堆栈 优先队列 随机队列 链表 二叉搜索树(平衡和不平衡) BST 红黑树 AVL树 跳过列表 堆 哈希值 冲突解决方法 链接 开放寻址 线性探测 多项式探测 ...
DSA Visualizer是一个Android应用程序,用于逐步地逐步可视化地学习和可视化数据结构和算法。 特征: 排序算法: 合并排序[完成] 快速排序[完成] BubbleSort [完成] InsertionSort [完成] SelectionSort [完成...
9)红黑树 59 2.栈 59 GoogLe+@http://dwz.cn/fada5 Csdn@http://dwz.cn/as2ik 1)括号配对 59 3.链表… 61 1)单向链表交点问题 61 2)链表内环的存在间题 62 3)链表逆置反向存储… 63 4)将两个排序...