C++

Forum

 
Is there anyways to make this less complex?

dob00000 (2)
I have to delete a node in Binary Search Tree. But somehow my testcase take too much space to run. Can I make it less complex?
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include <iostream>
  struct node
{
    int info;
    node* left, * right;
};
typedef node* Tree;
node* getNode(int x)
{
	node* p = new node;
	if (p != NULL)
	{
		p->info = x;
		p->left = NULL;
		p->right = NULL;
	}
	return p;
}
void insertNode(Tree &T,int x)
{
    if(T)
    {
        if(T->info==x)
        {
            return;
        }
        else if((T->info)>x)
        {
            insertNode(T->left, x);
        }
        else
        {
			insertNode(T->right, x);
		}
    }
    else
    {
        T=getNode(x);
    }
}
void inputTree(Tree &T)
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        insertNode(T,x);
    }
}
void searchStandfor(node *&q, node *&p)
{
    if(q->left!=NULL) searchStandfor(q->left,p);
        else
        {
            p->info=q->info;
            p=q;
            q=q->right;
        } 

}
void delete1root(Tree &T)
{
    node *p=T;
    if(T->left==NULL)
    {
        T=T->right;
    }
    else
    {
        if(T->right==NULL) 
        {
            T=T->left;
        }
        else
        {
        searchStandfor(T->right,p);
        }
    }
    delete(p);
}
void deleteRoot(Tree &T, int m)
{
    for(int i=0; i<m; i++)
    {
        if(T==NULL) return;
        else delete1root(T);
    }
}
void NLR(Tree T)
{
    if (T!=NULL)
    {
        cout << T->info << " ";
        NLR(T->left);
        NLR(T->right);
    }
}
kbw (9488)
getNode() becomes simpler when you realise that new Node will never return nullptr.

It become simpler still if struct node has a constructor.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct node
{
    node(int value, node* lnode = nullptr, node* rnode = nullptr) :
        info(value), left(lnode), right(rnode) {
    }
    int info;
    node* left, * right;
};

node* getNode(int x)
{
    return node* p = new node(x);
}


I'll add more if I have time.
Last edited on
jonnin (11437)
if your test case is failing, you may have a bug.
can you explain more about what is going wrong? Its hard to believe your test case is running you out of memory legit (it could be if you have a runaway recursion).

the code can be cleaned a little here and there, but its not that complicated and its fairly to the point (and, given that you are newish, fairly well written assuming there are things you don't know yet like methods for structs instead of stand alone functions). Note that less code is not always simpler -- shrinking code to make it smaller often makes it hard to read or weird.
Last edited on
seeplus (6591)
Deleting a node in a binary search tree is not trivial. There are several different situations to deal with to maintain the correct tree relationships after a node deletion. As a first refactor, then perhaps:

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
#include <iostream>

struct node {
	int info {};
	node* left {}, * right {};

	node(int i) : info(i) {}
};

using Tree = node*;

Tree getNode(int x) {
	return new node(x);
}

void insertNode(Tree& T, int x) {
	if (T) {
		if (T->info != x)
			insertNode(T->info > x ? T->left : T->right, x);
	} else
		T = getNode(x);
}

void inputTree(Tree& T) {
	size_t n {};

	std::cout << "How many nodes: ";
	std::cin >> n;

	std::cout << "Enter " << n << " items: ";

	for (size_t i {}; i < n; i++) {
		int x {};

		std::cin >> x;
		insertNode(T, x);
	}
}

Tree search(const Tree& q, int x) {
	return  q ? (q->info == x ? q : (x > q->info ? search(q->right, x) : search(q->left, x))) : nullptr;
}

Tree minValueNode(Tree node) {
	auto current { node };

	while (current && current->left)
		current = current->left;

	return current;
}

Tree deleteNode(const Tree& root, int key) {
	if (root) {
		if (key < root->info)
			root->left = deleteNode(root->left, key);
		else if (key > root->info)
			root->right = deleteNode(root->right, key);
		else {
			if (!root->left && !root->right)
				return nullptr;

			else if (!root->left) {
				const auto temp { root->right };

				delete root;
				return temp;
			} else if (!root->right) {
				const auto temp { root->left };

				delete root;
				return temp;
			}

			const auto temp { minValueNode(root->right) };

			root->info = temp->info;
			root->right = deleteNode(root->right, temp->info);
		}
	}
	return root;
}

void inorder(const Tree T) {
	if (T) {
		inorder(T->left);
		std::cout << T->info << " ";
		inorder(T->right);
	}
}

int main() {
	Tree t {};

	inputTree(t);
	inorder(t);
	std::cout << '\n';

	for (int x {}; std::cout << "Find: " && std::cin >> x; )
		std::cout << (search(t, x) ? "Found\n" : "Not found\n") << '\n';

	std::cin.clear();

	for (int x {}; std::cout << "Delete: " && std::cin >> x; ) {
		inorder(t = deleteNode(t, x));
		std::cout << '\n';
	}
}



How many nodes: 5
Enter 5 items: 3 2 4 5 1
1 2 3 4 5
Find: 3
Found

Find: 0
Not found

Find: ^Z
Delete: 6
1 2 3 4 5
Delete: 3
1 2 4 5
Delete: 5
1 2 4
Delete: 0
1 2 4
Delete: ^Z

Last edited on
Topic archived. No new replies allowed.