--- stl_tree.h 2007-02-07 17:49:15.000000000 -0200 +++ avl_tree.h 2007-02-07 16:58:40.000000000 -0200 @@ -1,4 +1,7 @@ -// RB tree implementation -*- C++ -*- +// AVL tree implementation -*- C++ -*- + +// Based on stl_tree.h from libstdc++. +// Changes by Daniel K. O. - 2007 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. // @@ -60,8 +63,8 @@ * You should not attempt to use it directly. */ -#ifndef _TREE_H -#define _TREE_H 1 +#ifndef _AVL_TREE_H +#define _AVL_TREE_H 1 #include #include @@ -69,13 +72,14 @@ #include #include -namespace std +namespace avl { - // Red-black tree class, designed for use in implementing STL + // Notes: + // AVL tree class, designed for use in implementing STL // associative containers (set, multiset, map, and multimap). The - // insertion and deletion algorithms are based on those in Cormen, - // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, - // 1990), except that + // insertion and deletion algorithms are based on Donald Knuth, + // "The Art of Computer Programming: Searching and Sorting Algorithms." + // except that // // (1) the header cell is maintained with links not only to the root // but also to the leftmost node of the tree, to enable constant @@ -87,14 +91,12 @@ // is relinked into its place, rather than copied, so that the only // iterators invalidated are those referring to the deleted node. - enum _avl_tree_color { _S_red = false, _S_black = true }; - struct _avl_tree_node_base { typedef _avl_tree_node_base* _Base_ptr; typedef const _avl_tree_node_base* _Const_Base_ptr; - _avl_tree_color _M_color; + signed char _M_bal_factor:2; _Base_ptr _M_parent; _Base_ptr _M_left; _Base_ptr _M_right; @@ -154,7 +156,7 @@ typedef _Tp& reference; typedef _Tp* pointer; - typedef bidirectional_iterator_tag iterator_category; + typedef std::bidirectional_iterator_tag iterator_category; typedef ptrdiff_t difference_type; typedef _avl_tree_iterator<_Tp> _Self; @@ -226,7 +228,7 @@ typedef _avl_tree_iterator<_Tp> iterator; - typedef bidirectional_iterator_tag iterator_category; + typedef std::bidirectional_iterator_tag iterator_category; typedef ptrdiff_t difference_type; typedef _avl_tree_const_iterator<_Tp> _Self; @@ -324,7 +326,7 @@ template > + typename _Compare, typename _Alloc = std::allocator<_Val> > class _avl_tree { typedef typename _Alloc::template rebind<_avl_tree_node<_Val> >::other @@ -379,7 +381,7 @@ _M_clone_node(_Const_Link_type __x) { _Link_type __tmp = _M_create_node(__x->_M_value_field); - __tmp->_M_color = __x->_M_color; + __tmp->_M_bal_factor = __x->_M_bal_factor; __tmp->_M_left = 0; __tmp->_M_right = 0; return __tmp; @@ -406,7 +408,7 @@ : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), _M_node_count(0) { - this->_M_header._M_color = _S_red; + this->_M_header._M_bal_factor = -2; // need this for _avl_tree_decrement this->_M_header._M_parent = 0; this->_M_header._M_left = &this->_M_header; this->_M_header._M_right = &this->_M_header; @@ -427,7 +429,7 @@ : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), _M_node_count(0) { - this->_M_header._M_color = _S_red; + this->_M_header._M_bal_factor = -2; // need this for _avl_tree_decrement this->_M_header._M_parent = 0; this->_M_header._M_left = &this->_M_header; this->_M_header._M_right = &this->_M_header; @@ -642,7 +644,7 @@ swap(_avl_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t); // Insert/erase. - pair + std::pair insert_unique(const value_type& __x); iterator @@ -718,15 +720,14 @@ const_iterator upper_bound(const key_type& __x) const; - pair + std::pair equal_range(const key_type& __x); - pair + std::pair equal_range(const key_type& __x) const; // Debugging. - bool - __rb_verify() const; + bool __avl_verify() const; }; template_M_parent = _M_end(); __t._M_root()->_M_parent = __t._M_end(); } - // No need to swap header's color as it does not change. + // No need to swap header's balance factor as it does not change. std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); } template - pair::iterator, bool> _avl_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: insert_unique(const _Val& __v) @@ -924,12 +925,12 @@ iterator __j = iterator(__y); if (__comp) if (__j == begin()) - return pair(_M_insert(__x, __y, __v), true); + return std::pair(_M_insert(__x, __y, __v), true); else --__j; if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) - return pair(_M_insert(__x, __y, __v), true); - return pair(__j, false); + return std::pair(_M_insert(__x, __y, __v), true); + return std::pair(__j, false); } template:: erase(const _Key& __x) { - pair __p = equal_range(__x); + std::pair __p = equal_range(__x); size_type __n = std::distance(__p.first, __p.second); erase(__p.first, __p.second); return __n; @@ -1353,7 +1354,7 @@ _avl_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: count(const _Key& __k) const { - pair __p = equal_range(__k); + std::pair __p = equal_range(__k); const size_type __n = std::distance(__p.first, __p.second); return __n; } @@ -1433,58 +1434,39 @@ template inline - pair::iterator, typename _avl_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator> _avl_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: equal_range(const _Key& __k) - { return pair(lower_bound(__k), upper_bound(__k)); } + { return std::pair(lower_bound(__k), upper_bound(__k)); } template inline - pair::const_iterator, typename _avl_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator> _avl_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: equal_range(const _Key& __k) const - { return pair(lower_bound(__k), + { return std::pair(lower_bound(__k), upper_bound(__k)); } - unsigned int - _avl_tree_black_count(const _avl_tree_node_base* __node, - const _avl_tree_node_base* __root); + bool + _avl_tree_check_balance(const _avl_tree_node_base* __root); template bool - _avl_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const + _avl_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__avl_verify() const { if (_M_impl._M_node_count == 0 || begin() == end()) return _M_impl._M_node_count == 0 && begin() == end() && this->_M_impl._M_header._M_left == _M_end() && this->_M_impl._M_header._M_right == _M_end(); - unsigned int __len = _avl_tree_black_count(_M_leftmost(), _M_root()); - for (const_iterator __it = begin(); __it != end(); ++__it) - { - _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); - _Const_Link_type __L = _S_left(__x); - _Const_Link_type __R = _S_right(__x); - - if (__x->_M_color == _S_red) - if ((__L && __L->_M_color == _S_red) - || (__R && __R->_M_color == _S_red)) - return false; - - if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) - return false; - if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) - return false; - - if (!__L && !__R && _avl_tree_black_count(__x, _M_root()) != __len) - return false; - } + if (!_avl_tree_check_balance(_M_root())) + return false; if (_M_leftmost() != _avl_tree_node_base::_S_minimum(_M_root())) return false; @@ -1492,6 +1474,7 @@ return false; return true; } -} // namespace std +} // namespace avl #endif +