12-11-2013
Binary search tree questions. Please help =)
I have some questions about certain placement of child nodes since I'm just learning BSTs and it's quite confusing even after reading some sources and doing some online insertion applets. Let's say I want to add nodes 5,7,3,4 to an empty basic BST.
Ok I understand that the left child must be less than the parent AND less than or equal to the right child from that same parent. I follow it until we add the 4 node. How do we determine that the insertion of 4 goes to the bottom right leaf position of 3 instead of the bottom left leaf position? Also, doing a AVL insertion of nodes 5,18,3,7,11 yielded some surprising position placements. Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why? Assuming that is the correct way, inserting 11 would switch the 11 and 18 spots, but wouldn't having 18 as the parent node, 7 as left child, and 11 as right child adhere to the principle of left child smaller than parent and smaller or equal to right child? I'm confused! I would appreciate any help. Thank you!
insert 7
insert 11
10 More Discussions You Might Find Interesting
1. Programming
Hi all,
I've got a problem, what function do i use to list the contents of all the directory tree (simular to "find")? Any other suggestions?
Thank you all (3 Replies)
Discussion started by: solvman
3 Replies
2. Shell Programming and Scripting
I almost have the entire script written. however the problem is how would i assign the global variable to terminate the process from the bottom up to ensure the child terminates so the parent can.
ex. I am proccess 1
I am proccess 2
etc
Here is the code
$ cat tree.c
... (3 Replies)
Discussion started by: slurpeyatari
3 Replies
3. Shell Programming and Scripting
I need to create a binary tree like structure of directories using shell script... does anyone know of any algorithm for this ?
i tried doing a recursive algorithm
function CreateDir
{
level=$1
dirname=$2
mkdir $dirname/sub1/
mkdir $dirname/sub2/
let level=level-1
... (2 Replies)
Discussion started by: macvijay1985
2 Replies
4. UNIX for Dummies Questions & Answers
Hi,
I am working on a program and kind of a stuck,nt getting it done.
"The program should take one command line arguments: number of hierarchy level. The
hierarchy of your program should of that level and each node have two child processes."
Can anyone give me the C code using fork() of this... (1 Reply)
Discussion started by: learneros
1 Replies
5. Shell Programming and Scripting
Hi,
I have a problem that I am sure someone will know the answer to. Currently I have a script which returns a binary output if it finds a certain search string (in this case relating to a DRBD cluster) as follows:
searchstring="cs:Connected st:Primary/Secondary ds:UpToDate/UpToDate"
&& echo... (3 Replies)
Discussion started by: almightybunghol
3 Replies
6. Programming
I have just been researching this topic and I was wondering what type of application might a binary tree be used for. For instance what type of application would be a good showcase for a binary tree that I could write as an example? (5 Replies)
Discussion started by: sepoto
5 Replies
7. Programming
I am writing code for a binary search tree search and when I compile it i am getting strange errors such as, " /tmp/ccJ4X8Xu.o: In function `btree::btree()':
project1.cpp:(.text+0x0): multiple definition of `btree::btree()' "
What does that mean exactly?
tree.h
#ifndef TREE_H
#define... (1 Reply)
Discussion started by: meredith1990
1 Replies
8. UNIX for Dummies Questions & Answers
Hello Everyone,
I need to find the file / directory with the maximum timestamp in a directory tree having many files / directories.
Could you please help.
Thanks,
H squared (3 Replies)
Discussion started by: H squared
3 Replies
9. UNIX for Dummies Questions & Answers
Hello again. I have two problems - is it possible to solve them?
1. I want to replace a few bytes after specific hex-string.
i.e.: I want to replace two bytes after AA AB AC:
AA AB AC 00 00 AA AA AA
so the expected result should be:
AA AB AC FF FF AA AA AA
2. I want to replace three bytes... (9 Replies)
Discussion started by: useretail
9 Replies
10. Web Development
Database Structure
Root Table
ID Root_ Node Level
1 A 0
2 B 1
3 C 1
Child Table
ID Left_Node Right_Node Root_Node Root_ID
1 B C A 1
... (1 Reply)
Discussion started by: Deepak Tiwari
1 Replies
LEARN ABOUT DEBIAN
forest::tree
Forest::Tree(3pm) User Contributed Perl Documentation Forest::Tree(3pm)
NAME
Forest::Tree - An n-ary tree
SYNOPSIS
use Forest::Tree;
my $t = Forest::Tree->new(
node => 1,
children => [
Forest::Tree->new(
node => 1.1,
children => [
Forest::Tree->new(node => 1.1.1),
Forest::Tree->new(node => 1.1.2),
Forest::Tree->new(node => 1.1.3),
]
),
Forest::Tree->new(node => 1.2),
Forest::Tree->new(
node => 1.3,
children => [
Forest::Tree->new(node => 1.3.1),
Forest::Tree->new(node => 1.3.2),
]
),
]
);
$t->traverse(sub {
my $t = shift;
print((' ' x $t->depth) . ($t->node || 'undef') . "
");
});
DESCRIPTION
This module is a basic n-ary tree, it provides most of the functionality of Tree::Simple, whatever is missing will be added eventually.
This class inherits from Forest::Tree::Pure>, but all shared methods and attributes are documented in both classes.
ATTRIBUTES
node
uid
parent
parent
_set_parent
has_parent
clear_parent
children
get_child_at ($index)
Return the child at this position. (zero-base index)
child_count
Returns the number of children this tree has
size
size
has_size
clear_size
height
height
has_height
clear_height
METHODS
is_root
True if the current tree has no parent
is_leaf
True if the current tree has no children
depth
Return the depth of this tree. Root has a depth of -1
add_child ($child)
add_children (@children)
Add a new child. The $child must be a "Forest::Tree"
insert_child_at ($index, $child)
Insert a child at this position. (zero-base index)
remove_child_at ($index)
Remove the child at this position. (zero-base index)
traverse (&func)
Takes a reference to a subroutine and traverses the tree applying this subroutine to every descendant.
siblings
Returns an array reference of all siblings (not including us)
to_pure_tree
Invokes "reconstruct_with_class" with Forest::Tree::Pure.
to_mutable_tree
Returns the invocant (without cloning).
clone
See "clone" in Forest::Tree::Pure.
This variant will not clone the parent, but return a clone of the subtree that is detached.
get_index_in_siblings
Returns the index of the tree in the list of children.
Equivalent to calling "$tree-"parent->get_child_index($tree)>.
Returns -1 if the node has no parent (the root node).
BUGS
All complex software has bugs lurking in it, and this module is no exception. If you find a bug please either email me, or add the bug to
cpan-RT.
AUTHOR
Stevan Little <stevan.little@iinteractive.com>
COPYRIGHT AND LICENSE
Copyright 2008-2010 Infinity Interactive, Inc.
<http://www.iinteractive.com>
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
perl v5.10.1 2010-09-27 Forest::Tree(3pm)