-
Notifications
You must be signed in to change notification settings - Fork 3
/
RBT.hh
71 lines (54 loc) · 1.64 KB
/
RBT.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//
// Copyright 2009-2017 M. Shulhan (ms@kilabit.info). All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
#ifndef _LIBVOS_RBT_HH
#define _LIBVOS_RBT_HH 1
#include "Locker.hh"
#include "TreeNode.hh"
#include "Buffer.hh"
namespace vos {
//
// `RBT` implement the Red-Black tree algorithm.
//
class RBT : public Locker {
public:
RBT(int (*fn_cmp)(Object*, Object*)
, void (fn_swap)(Object*, Object*) = NULL);
virtual ~RBT();
const char* chars();
void swap_node(TreeNode* x, TreeNode* y);
void swap_content(TreeNode* x, TreeNode* y);
const char* get_red_node_chars();
void set_root_unsafe(TreeNode* node);
TreeNode* get_root_unsafe();
TreeNode* get_root();
TreeNode* insert(TreeNode* node, int replace = 0);
TreeNode* remove(TreeNode* node);
TreeNode* find(Object* item);
int is_balance();
static const char* __cname;
private:
TreeNode* _root;
Buffer _red_nodes;
// Variable that count and save current black node in tree.
int _n_black;
// Variable that set to `1` if all path have the same number of black
// nodes, or `0` if one of the path is not equal.
int _n_black_valid;
int (*_fn_cmp)(Object*, Object*);
void (*_fn_swap)(Object*, Object*);
void _chars(Buffer* b, TreeNode* node, int level = 0, int n_black = 0);
void _delete(TreeNode* p);
int _check_balance(TreeNode* p, int nblack);
void _do_rebalance(TreeNode* x);
TreeNode* _removed_have_no_child(TreeNode* x);
TreeNode* _removed_have_both_childs(TreeNode* x);
TreeNode* _remove_unsafe(TreeNode* x);
RBT(const RBT&);
void operator=(const RBT&);
};
} // namespace::vos
#endif
// vi: ts=8 sw=8 tw=78