`

算法设计和数据结构学习_5(BST&AVL&红黑树简单介绍)

阅读更多
原帖地址:http://www.cnblogs.com/tornadomeet/p/3141686.html

 


  前言:


  节主要是给出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笔记)


 


 


 


 

本文链接

分享到:
评论

相关推荐

    红黑树和AVL树的实现

    红黑树和AVL树是两种自平衡二叉查找树,它们在计算机科学中的数据结构领域扮演着重要的角色,主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡,从而确保搜索、插入和删除...

    用BST,红黑树,AVL树,朴素算法实现字典的查找

    在本项目中,我们主要探讨了四种不同的数据结构在实现字典查找中的应用:二叉搜索树(BST)、红黑树(Red-Black Tree)以及AVL树,还有朴素的线性查找算法。这些数据结构在计算机科学中扮演着至关重要的角色,特别是...

    数据结构算法与应用-C__语言描述

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。C语言因其高效、底层特性,常被用于实现数据结构和算法。本资料"数据结构算法与应用-C_语言描述"旨在深入探讨如何利用C语言来实现各种常用的...

    Avl_tree.rar_avl_avl java_avl tree_tree

    **avl树介绍** AVL树是一种自平衡二叉查找树(Binary Search Tree,BST),由G....尽管红黑树等其他自平衡二叉查找树在某些情况下表现更优,但AVL树因其严格的平衡性在特定应用场景下仍然具有价值。

    严蔚敏数据结构PPT_严蔚敏_algorithm_

    这份PPT材料是学习计算机科学与技术领域的基石,涵盖了数据结构的核心概念、设计与实现,以及相关的算法分析。 在数据结构领域,我们首先会接触到线性数据结构,如数组、链表和栈。数组是最基本的数据结构,提供...

    C++树形查找(搜索树,AVL树插入删除,红黑树插入流程),参考书籍(王道考研书记结构2023版)

    在IT领域,数据结构是计算机科学的基础之一,而树形数据结构在算法设计中扮演着重要角色。本文将深入探讨C++中与树形查找相关的知识点,包括搜索树、AVL树以及红黑树的插入操作,这些都是考研必备的知识点。 首先,...

    AVL_Tree.rar_avl tree_avl tree height_tree

    AVL树的平衡特性确保了查找效率的高效性,但相对于红黑树等其他自平衡树,AVL树的插入和删除操作可能会更复杂,因为需要更多的旋转操作。然而,在高度动态的数据集上,AVL树可能因为其严格平衡而提供更快的查找速度...

    bst_oldak9_bst实现_

    首先,平衡二叉树有多种类型,如AVL树和红黑树。AVL树是最早的自平衡二叉搜索树,它要求任何节点的两个子树的高度差不超过1,并且每个节点的两个子树都必须是平衡的。AVL树的主要操作包括插入、删除和查找,它们都...

    实用数据结构教程_Java语言描述.zip

    二叉树是最常见的树类型,包括二叉查找树(BST)、平衡二叉树(AVL、红黑树等)等,它们在搜索、排序等方面非常有效。 6. 图:图由节点(顶点)和连接节点的边组成,用于表示复杂的关联关系。Java中,可以使用邻接...

    数据结构经典算法(C语言实现)

    5. **树**:数据结构中的重要组成部分,例如二叉搜索树(BST)用于快速查找,AVL树和红黑树则为自平衡二叉搜索树,能保证操作的高效性。 6. **图**:用于表示对象之间的复杂关系,如邻接矩阵和邻接表是常见的图表示...

    算法设计__课程论文__基于树型结构的最少删除问题解法

    **最少删除问题详解** 在计算机科学中,"最少删除问题"是一个典型的算法问题,它涉及到序列处理和排序。...深入理解并掌握这种算法有助于提升对数据结构和算法设计的理解,对于学习和解决实际问题具有重要意义。

    红黑树、二叉搜索树的实现和性能比较

    在计算机科学中,数据结构是程序设计的基础,而红黑树和二叉搜索树是其中两种重要的自平衡二叉查找树。本文将深入探讨这两种数据结构的实现、操作以及性能比较,尤其关注它们在C语言环境下的实现和GCC编译器下的运行...

    数据结构算法 模型

    平衡树如AVL树和红黑树,确保了树的高度平衡,从而优化了查找效率。 图由顶点和连接顶点的边组成,可以表示复杂的关系网络,如社交网络、交通网络等。图算法如最短路径算法(Dijkstra's算法、Floyd-Warshall算法)...

    数据结构与算法分析C语言描述第2版源码

    这本书深入浅出地介绍了各种数据结构(如数组、链表、树、图)以及算法(排序、查找、图算法等)的设计与分析。源码文件包含了书中所有示例程序,供读者实践和学习。 1. 数据结构: - 数组:基本的数据组织形式,...

    数据结构与算法

    二叉查找树(BST)允许快速查找、插入和删除操作,而平衡二叉树如AVL树和红黑树则通过保持树的高度平衡来进一步提高性能。 堆栈是一种后进先出(LIFO)的数据结构,类似于现实生活中的叠盘。它主要用于函数调用、...

    数据结构与算法源代码(C语言)145个

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。C语言因其高效、底层特性,常被用于实现这些概念。以下将详细讲解标题和描述中提到的数据结构与算法的知识点,以及它们在C语言中的实现。 1....

    张铭版数据结构与算法代码

    可能会包含二叉搜索树(BST)、平衡二叉树(AVL或红黑树)、满二叉树和完全二叉树的概念及操作,如查找、插入、删除等。 4. **chap12_AdvTree(高级树结构)** - 这里可能涉及更复杂和特定类型的树,如B树、B+树、...

    bst.zip_bst_二叉查找树

    5. **平衡操作 (平衡二叉查找树)**: 为了优化查找性能,有些二叉查找树会采用自平衡策略,如AVL树和红黑树。这些树在插入和删除后会自动调整结构以保持平衡,确保最坏情况下的搜索时间复杂度为O(log n)。 以上是...

    数据结构算法总结_C++_orangejj4_

    7. **二叉树(Binary Tree)**:二叉树每个节点最多有两个子节点,分为二叉搜索树(BST)、平衡树(AVL、红黑树)等。二叉树的操作包括插入、删除、查找。 8. **图(Graph)**:图由顶点和边构成,可以表示多种关系...

Global site tag (gtag.js) - Google Analytics