0

So I am blind and using a screen reader. I managed to get an idea on the structure of a binary tree through this. Using the structure of the binary tree in the answer, I managed to understand binary search trees and binary heap and how to do insertion, search and other operations on them. However, when I begin studdiing 2-3 search trees I am completely confused on how it looks. Say the structure of a binary tree looks like this:

 //slashes are links
 root
/ \

left right

Using this representation, I got to understand to insert, delete and search recursively in this tree.

However, when it comes to trees with three nodes and two keys, I am completely lost. I absolutely don't know how this tree should be structured, but I think it looks like this.

 //slashes are links
 root
/ \ /

left mid right

I am not sure if this is correct. I kept reading on how to insert nodes to it but the explanations are always using images/graphics and it's extremely hard to imagine. Can anyone explain this further?

Community
  • 1
  • 1
lightning_missile
  • 2,821
  • 5
  • 30
  • 58

2 Answers2

1

There are many ways to represent it. Two I suggest you try are

  1. Instead of representing a node by its key, use a pair of keys, and show three links:
     d,q
    / | \
   a  g  z
  1. Use a horizontal link to show a "sister" node; when a node has a sister, it only has one child:
 d - q
 |  / \
 a  g  z
Doug Currie
  • 40,708
  • 1
  • 95
  • 119
1

It is a little more complicated for the 2-3 trees.

A node in the tree holds one or two key values, and two or three children nodes [respectively] except for the leaves.

So you can figure a node as a bubble with one or two values inside and two or three arrows pointing downward.

Using your notation it would be one of

    root
    /   \
left     right

or 

    root
    / | \
left mid right

And adding the keys, for instance

     [a]
    /   \
[b,c]     [d]

or 

     [a,b]
    /  |  \
[c] [d,e] [f,g]