Thread: Weight Balanced Tree - Implementation

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    22

    Weight Balanced Tree - Implementation

    Weight-balanced tree
    From Wikipedia, the free encyclopedia

    Weight Balanced Tree or a Weight Balanced Binary Tree

    Weight Balanced Binary Tree is a binary tree where the most probable item is the root item. The left sub tree consists of items less than the root items ranking, not its probability.
    http://en.wikipedia.org/wiki/Weight-balanced_tree

    Well,

    I have to implement this tree, with insertion, search and delete functions. My tree should work only with int values.

    But I didn't understand very well this tree, I have some questions about how this tree works.

    Questions
    1) How this tree deals with repeated values?

    2) How it does the sort of the nodes? Wich are the conditions of the comparison? The weight or the value of the node?

    Since now, I thanks to all of you that read this thread.
    Any doubts about my problem let me know...

    []'s
    Paulo Vitor Lima

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Weight Balanced Binary Tree is a binary tree where the most probable item is the root item.
    >The left sub tree consists of items less than the root items ranking, not its probability.
    Yea, that's not a weight balanced tree according to the classical definition. It's more like a priority queue than a balanced binary search tree.

    >1) How this tree deals with repeated values?
    Repeated values are typically inserted on top of each other in the tree so that you can treat them as a stack. It depends on how the insertion algorithm is written though.

    >2) How it does the sort of the nodes?
    Some kind of arbitrary probability. It looks like the article is assuming some kind of occurrence frequency, such as in common words.

    >Wich are the conditions of the comparison? The weight or the value of the node?
    The weight of the value determines the location of a node.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Double to Int conversion warning
    By wiznant in forum C Programming
    Replies: 15
    Last Post: 09-19-2005, 09:25 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM