21 #ifndef ELM_AVL_TREE_H
22 #define ELM_AVL_TREE_H
24 #include <elm/inhstruct/BinTree.h>
26 namespace elm {
namespace avl {
34 class Node:
public BinTree::Node {
40 #ifdef ELM_DEBUG_AVLTREE
41 virtual void dump(
void) = 0;
46 Node *insert(Node *cur, Node *node);
47 Node *remove(Node *cur, Node *node);
48 Node *removeGreatest(Node *
root, Node *&res);
49 Node *removeLeast(Node *
root, Node *&res);
50 Node *rotateSingleLeft(Node *node);
51 Node *rotateDoubleLeft(Node *node);
52 Node *rotateSingleRight(Node *node);
53 Node *rotateDoubleRight(Node *node);
55 Node *balanceLeft(Node *cur, Node*&
left);
56 Node *balanceRight(Node *cur, Node*&
left);
57 void clean(Node *node);
58 inline Node *_root(
void)
const {
return (Node *)
root(); };
59 inline int height(Node *node)
const {
return node ? node->h : 0; };
61 inline void computeHeight(Node *node) {
62 int hleft = height(node->_left()), hright = height(node->_right());
70 virtual int compare(Node *node1, Node *node2) = 0;
71 virtual void free(Node *node);
76 inline bool isEmpty(
void) {
return BinTree::isEmpty(); }
78 Node *
get(Node *node);
80 inline void visit(
Visitor *visitor) {
return BinTree::visit(visitor); }
84 void insert(Node *node);
85 void remove(Node *node);
89 #ifdef ELM_DEBUG_AVLTREE
90 void dump(Node *node = 0,
int level = 0);
96 #endif // ELM_AVL_TREE_H