8 - Binary Search Trees


8.1 - Binary Search Trees

  • Binary Tree = A herarchical structure consisting of a root element with two distinct binary trees (right and left).
  • Length = Number of edges in the path.
  • Depth = The length of the path from the root to the specified node.
  • Level = The set of nodes at a given depth.
  • Siblings = Nodes that share the same parent.
  • Leaf = A node without children.
  • Height = The number of nodes from the root node to the most deepest node.
  • Binary Search Tree (BST) = Items hich are lower than the current node is placed on the left subtree, items higher then the current node is palced on the right subtree.
  • A node is usually defined as follows:

    • class TreeNode<E> {
          protected E element;            //Current element
          protected TreeNode<E> left;     //Left subtree
          protected TreeNode<E> right;    //Right subtree
      
          public TreeNode(E e) {
              element = e;
          }
      }
      
  • Searching for an element is done by comparing the current element (which we are looking at) with the target element (for which you are looking for).

    • If the target element is smaller then the current element, go to the left subtree.
    • If the target element is bigger then the current element, go to the right subtree.
    • If the target element is equal to the current element, it has been found.
  • Inserting an element is done at the first parent which does not have any childs.

    • While finding the parent the tree needs to be followed by comparing the element we want to insert to the one we have selected as parent.
    • Moving down while keeping the rules of searching (see above) applied.
  • Removing an element is done by finding the element, and then if the node has a child reconnect that back to the tree.

    • If the element we want to remove has a left child (see image in next paragraph):
      • Replace the element to be removed with his most right (grand) child of his left subtree.
      • Make any children of that most right element, children of that most rights parent.
      • Example:
        • We want to remove 60, he has no parent :(.
        • He has child 55 and 100.
        • The most right (grand)child from the left tree of 60 is 59.
        • We replace 60 with 59.
        • Any childs of 59 we make childs of the parent of 59 (57)
    • If the element we want to remove has a right child (see image in next paragraph):
      • Connect the right child of the element to be removed to the parent of that element. At the position the element to be removed was.
      • Example:
        • We want to remove 57, his parent is 55.
        • He has child 59.
        • Replace 57 with 59, and delete 57.
    • If the element we want to remove has a left and a right child:
      • Only do the left child removal process. Right subtree stays attached the same.
    • If the element we want to remove has no childs (see image in next paragraph):
      • Just take it out already.
      • Example:
        • We want to remove 101, his parent is 107.
        • We delete 101.
  • You can use recusion to display binary trees.

  • Using a Huffman coding scheme. Codes for characters are constructed based on the occurrence of characters in the text using a binary tree. (pg 959)

8.2 - Tree Traversal

  • Tree Traversal = The process of visisiting each node in the tree exactly once.

  • InOrder = Left - Current - Right (45, 55, 57, 59, 60, 67, 100, 101, 107)

  • PostOrder = Left - Right - Current (45, 59, 57, 55, 67, 101, 107, 100, 60)

  • PreOrder / Depth-First = Current - Left - Right (60, 55, 45, 57, 59, 100, 67, 107, 101)

  • Breadth-Firist = Per level, top to bottom. (60, 55, 100, 45, 57, 67, 107,59, 101)

results matching ""

    No results matching ""